存档

C++17 新特性:结构化绑定

2024/03/29 971

结构化绑定定义及用法

所谓"结构化绑定", 即将指定的名称绑定到初始化器的子对象或元素上。比如有如下结构体:

那么有如下写法,直接把该结构体的成员绑定到新的变量名上:

结构化绑定支持的方式:

auto 前后可以使用 const alignas& 修饰。

结构化绑定可以用在 数组(array)、类元组(tuple-like)和成员变量上(data members)。

这么做的好处是使得代码结构更清晰,简洁易读。

继续阅读

C++20 Ranges

2024/01/28 861

Ranges 是C++20 提供的一套对范围的统一抽象和操作库。ranges 指可迭代的序列,它可以包括任何能够提供迭代器的数据结构, 如 vector, list, etc. 引入 ranges 可以使迭代的处理更简洁直观灵活。

我们知道 STL algorithms 利用迭代器对数据进行操作。比如我们需要对一个 vector 进行排序, 需要将排序的范围的迭代器做为参数传递给 sort() 方法:

这种写法很灵活。但更多的时候,我们是想对整个 vector 进行排序,传入迭代器反而是多余的操作了。引入 Ranges 即可简化这一操作。

在 ranges 库中,默认是对整个范围进行操作。当然,也可以像原来一样,使用迭代器来指定范围:

这是一种简化操作的方式。但 ranges 更重要的优势在于,它允许你以函数式编程的方式来操作 STL algorithm 。

继续阅读

C++ 内存对齐

2021/01/08 3,529

如下两个结构体 A B ,他们的实例的大小相同吗?

两个 char 共占两个字节, 一个 int 占4个字节, 所以两个结构体都是 6个字节。但事实并非如此,在大部分计算机中,他们都不会只占 6 个字节。这涉及到 内存对齐
需知,计算机访问内存的方式,并不是一个字节一个字节访问的,而是以字长(word size)为单位来进行访问的。32位计算机的字长为 4 字节, 64位计算机的字节为 8 字节。而所谓内存对齐, 就是将变量调整至字长的倍数的位置存放,以方便计算机访问
上面两个结构体在内存中的布局最有可能是这个样子的:(这里说 最有可能 是因为具体的布局要视计算机而定)


我们使用一段代码来验证:

结果如下:

A 中,c_1 i 共占一个字,c_2 占一个字。这种将多个变量放入一个字中的动作,叫作 packing 。 而组成一个字时,补充不足的部分,叫 padding
如何知道某种类型的变量要对齐到哪个位置呢?它取决于一个类型的 alignment 如 int 类型的alignment 为4, 那么int 类型变量的地址必定为 4 的倍数。

继续阅读

Chromium 的 Cookie 机制

2019/09/06 5,470

Cookie 指某些网站为了辨别用户身份而储存在用户本地终端(Client Side)上的数据,它是一种古老的技术, 由网景公司的前雇员卢·蒙特利在1993年3月发明。
Cookie 格式是一系列键值对, 以 ; 组合,如下

当然, Cookie还有更多的内容,如创建时间,过期时间等,对应的域等等。一般而言,为了安全只允许页面访问该域下的Cookie.
根据 Cookie 的时效性可以将 Cookie 分为两类,一种是会话型Cookie (Session Cookie), 只保存于内存中, 当浏览器退出的时候,即清除这些 Cookie. 第二种是持续型 Cookie (Persistent Cookie),也就是当浏览器退出的时候仍然保留的Cookie.
Chromium 中Cookie操作的类结构如下所示: 

其中 CookieStore 是主要的导出接口,CookieMonster 是重要的实现接口,它相当于是 Cookie 的管理器。它有几个作用:一是实现 CookieMonster 中的接口,二是报告前者的事件,如 Cookie 更新信息等,三是 Cookie对象(即 CanonicalCookie) 的集合。
PersistentCookieStore 持久化类,SQLitePersistentCookieStore 是持久化的具体实现,负责实际的存储动作。
Chrome 的 Cookie使用 Sqlite存储,是位于 %AppData%\Local\Google\Chrome\User Data\Default 目录下的 Cookies 文件。

继续阅读

算法学习:(单)链表问题

2018/06/17 4,388

一 链表倒置

链表倒置是链表的基本操作之一。

题目 一 Reverse Linked List

LeetCode 206 Reverse Linked List

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

题目提示可以用 迭代 或 递归 两种方法来解。

  • 迭代方法
    如图: 两个指针 head p 分别指向 表头,欲倒置的元素. 为了使下一个欲倒置的元素不会  掉, 还需要一个指针 tmp 来保护它

    1. p->next 指向 head
    2. head->next 指向 tmp
    3. head = p, p = tmp, tmp 保护下一个欲倒置的元素

    代码:

  • 递归方法
    思想和上面一样,只不过代码的写法不同:

    递归的方法代码简洁高效,在很多链表题目中都会用到它,所以特别重要。例如下一题

继续阅读

算法学习:动态规划问题的一般解法

2018/06/12 4,144

例题 一 : Triangle

LeetCode 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析:

设三角形共有 $N$ 行, $r$ 为三角形的行, $c$ 为三角形的列。从点 $P(r,c)$ 出发,每向下走一步有两个点$P_1(r+1,c), P_2(r+1, c+1)$ 可以选择 ,如果每次都选值小的点$min(P1, P2)$,则最后得到的点的值之和即是最优解。令 $M(r,c)$ 为从 $P(r,c)$ 开始到下面的列的各条路径中,最佳路径的数字之和。

解法一:

这是一个典型的递归问题。

$$M(r,c) = \begin{cases}  P(r,c), & \text{if r = N }\\  min(M(r+1,c), M(r+1,c+1)) + P(r,c),& \text{others}\\ \end{cases}$$

由此写出代码:

代码没有问题,在 "Run Code" 时可以得出正确的结果。但是 "Submit" 却会给出 "Time Limit Exceeded",超时!

如果我们推算这个解法的时间复杂度的话,可以得到 $O(2^n)$ .这不超时就有鬼了。我们需要改进这个算法。

继续阅读

在 Qt 中使用 TreeView

2018/05/11 9,061

提示:本文中的 Demo 已 push 到 github,可忽略本文直接到 我的github 中查看代码。

Qt 提供了 QuickControl TreeView 。但是比较奇葩的是该控件不能直接使用,而需要用户自己扩展实现。
官方给出了一个示例如下:

它声明了一个 TreeView控件,该控件有 2 列,分别为 Name 和 Permissions,还有一个名为 fileSystemModel 的 model 。对用户来说,这里的 model 是一个关键性的对象,它需要用户使用 C++ 实现 ,并注册到 qml 中供 TreeView 使用。按官方的说法, model 是一个 为 tree view 提供数据的属性,它包含了 tree view 将要展示的数据
用户的 model 必须继承于 QAbstractItemModel
该类是一个抽象类,在运行中,treeview 从该类中获取用户数据,再在UI上展示。该类有如下纯虚函数,必须在子类中实现:

继续阅读

using 关键字在 C++ 中的几种用法

2018/03/13 15,365

对C++中 using关键字的几种用法的总结:

1. using 声明

using 声明 (using declaration) 是将命名空间中单个名字注入到当前作用域的机制,使得在当前作用域下访问另一个作用域下的成员时无需使用限定符 ::

using 声明将其它 namespace 的成员引入本命名空间的 当前作用域 (包括其嵌套作用域)  。一个 using 声明一次只引入一个命名空间成员,它使得无论程序中使用哪些名字,都非常准确。
利用 using 声明,可以改变派生类对父类成员的访问控制:

尽管 Derived 对 base 是私有继承,但通过 using 声明,我们还是可以在 Derived 中访问其成员,且后续的继承同样不受 private 限定的影响。

继续阅读