豌豆

结构化绑定定义及用法

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

struct Student {
  int age;
  std::string name;
};

1

2

3

4

struct Student {

int age;

std::string name;

};

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

Student st{18, "Tom"};
auto [a, n] = st;  //auto a=n.age, auto n=s.name

1 2	Student st{18, "Tom"}; auto [a, n] = st; //auto a=n.age, auto n=s.name

结构化绑定支持的方式：

auto [ident-list] = expression;
auto [ident-list] {expression};
auto [ident-list](expression);

1

2

3

auto [ident-list] = expression;

auto [ident-list] {expression};

auto [ident-list](expression);

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

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

int tm[3] = {1949, 10, 1};
auto [y, m, d] = tm;
std::cout << m << "/" << d << "/" << y << std::endl;

std::map<int, std::string> mp = {{1, "Name"}, {2, "Age"}};
for (const auto& [k, v] : mp) {
  std::cout << k << ": " << v << std::endl;
}

auto [it, rst] = mp.insert({1, "Type"});
if (!rst) {
  std::cout << "Insert Error" << std::endl;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

int tm[3] = {1949, 10, 1};

auto [y, m, d] = tm;

std::cout << m << "/" << d << "/" << y << std::endl;

std::map<int, std::string> mp = {{1, "Name"}, {2, "Age"}};

for (const auto& [k, v] : mp) {

std::cout << k << ": " << v << std::endl;

}

auto [it, rst] = mp.insert({1, "Type"});

if (!rst) {

std::cout << "Insert Error" << std::endl;

}

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

继续阅读

Coding c++, c++17

C++20 Ranges

2024/01/28 904

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

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

std::vector v = {1,6,4,2,8};
std::sort(v.begin(), v.end());
std::sort(v.begin(), v.end(), std::greater());

1

2

3

std::vector v = {1,6,4,2,8};

std::sort(v.begin(), v.end());

std::sort(v.begin(), v.end(), std::greater());

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

std::ranges::sort(v);
std::ranges::sort(v,std::greater());

1 2	std::ranges::sort(v); std::ranges::sort(v,std::greater());

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

std::ranges::sort(v.begin(), v.end());

1	std::ranges::sort(v.begin(), v.end());

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

继续阅读

Coding c++, c++20

C++ 内存对齐

2021/01/08 3,557

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

struct A{
  char c_1;
  int i;
  char c2; 
};

struct B{
  char c_1;
  char c_2;
  int i;
};

1

2

3

4

5

6

7

8

9

10

11

struct A{

char c_1;

int i;

char c2;

};

struct B{

char c_1;

char c_2;

int i;

};

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

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

void showmem(unsigned char* p, uint32_t sz){
  int len = sizeof(int*);
  cout<<"\t";
  for(int i = 0; i<len; i++){
    cout<<i<<"\t";
  }
  cout<<endl;

  for(int i = 0; i<=len; i++){
    cout<<"-------|";  
  }
  cout<<endl;

  unsigned char* t = p;
  uint32_t i = 0;
  char msg[8];
  while(i < sz){
    sprintf(msg, "%02d", i); 
    cout<<msg<<"|\t";
    for(int j = 0; j< len && (i+j)<sz; j++){
      sprintf(msg, "%04d", *(uint8_t*)(t+j));
      cout<<msg<<"\t";
    }   
    cout<<endl;
    i += len;
    t += len;
  }
}

////
  //...
  A a{'a', 2, 'b'};
  B b{'a', 'b', 2};

  cout<<"A:"<<endl;
  showmem((unsigned char*)&a, sizeof(a));
  cout<<endl;

  cout<<"B:"<<endl;
  showmem((unsigned char*)&b, sizeof(b));
  cout<<endl;

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

void showmem(unsigned char* p, uint32_t sz){

int len = sizeof(int*);

cout<<"\t";

for(int i = 0; i<len; i++){

cout<<i<<"\t";

}

cout<<endl;

for(int i = 0; i<=len; i++){

cout<<"-------|";

}

cout<<endl;

unsigned char* t = p;

uint32_t i = 0;

char msg[8];

while(i < sz){

sprintf(msg, "%02d", i);

cout<<msg<<"|\t";

for(int j = 0; j< len && (i+j)<sz; j++){

sprintf(msg, "%04d", *(uint8_t*)(t+j));

cout<<msg<<"\t";

}

cout<<endl;

i += len;

t += len;

}

////

//...

A a{'a', 2, 'b'};

B b{'a', 'b', 2};

cout<<"A:"<<endl;

showmem((unsigned char*)&a, sizeof(a));

cout<<endl;

cout<<"B:"<<endl;

showmem((unsigned char*)&b, sizeof(b));

cout<<endl;

结果如下：

A:
        0       1      2       3        4       5       6       7	
-------|-------|-------|-------|-------|-------|-------|-------|-------|
00|	0097	0000	0000	0000	0002	0000	0000	0000	
08|	0098	0000	0000	0000	

B:
        0       1       2       3       4       5       6       7	
-------|-------|-------|-------|-------|-------|-------|-------|-------|
00|	0097	0098	0000	0000	0002	0000	0000	0000

1

2

3

4

5

6

7

8

9

10

A:

0 1 2 3 4 5 6 7

-------|-------|-------|-------|-------|-------|-------|-------|-------|

00| 0097 0000 0000 0000 0002 0000 0000 0000

08| 0098 0000 0000 0000

B:

0 1 2 3 4 5 6 7

-------|-------|-------|-------|-------|-------|-------|-------|-------|

00| 0097 0098 0000 0000 0002 0000 0000 0000

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

继续阅读

Coding

Chromium 的 Cookie 机制

2019/09/06 5,520

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

TBLkisOn=0; GeoIP=US:CA:Los_Angeles:34.05:-118.26:v4; mwPhp7Seed=9d0

1	TBLkisOn=0; GeoIP=US:CA:Los_Angeles:34.05:-118.26:v4; mwPhp7Seed=9d0

当然， 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 文件。

继续阅读

Coding chromium

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

2018/06/17 4,427

一链表倒置

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

题目一 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 来保护它

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

代码：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head) return NULL;
        if(!head->next) return head;

        ListNode *p,*tmp;
        p = head->next;
        tmp = p->next;
        head->next = NULL;

        while(p1){
            p->next = head;
            head = p;
            p = tmp;
            if(tmp)
                tmp = tmp->next;
        }

        return head;
    }
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution {

public:

ListNode* reverseList(ListNode* head) {

if(!head) return NULL;

if(!head->next) return head;

ListNode *p,*tmp;

p = head->next;

tmp = p->next;

head->next = NULL;

while(p1){

p->next = head;

head = p;

p = tmp;

if(tmp)

tmp = tmp->next;

}

return head;

}

};

递归方法
思想和上面一样，只不过代码的写法不同：

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }

        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution {

public:

ListNode* reverseList(ListNode* head) {

if(!head || !head->next){

return head;

}

ListNode* p = reverseList(head->next);

head->next->next = head;

head->next = NULL;

return p;

}

};

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

继续阅读

Coding algorithm, leetcode, 算法, 链表

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

2018/06/12 4,189

例题一 : 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}$$

由此写出代码：

class Solution {
public:
    int getMinPathSum(vector<vector<int>>& triangle, int r, int c){
        if(r == triangle.size() - 1) return triangle[r][c];

        int x = getMinPathSum(triangle, r+1, c);
        int y = getMinPathSum(triangle, r+1, c+1);

        x = x<y ? x: y;

        return triangle[r][c] + x;
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        return getMinPathSum(triangle, 0,0);
    }
};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution {

public:

int getMinPathSum(vector<vector<int>>& triangle, int r, int c){

if(r == triangle.size() - 1) return triangle[r][c];

int x = getMinPathSum(triangle, r+1, c);

int y = getMinPathSum(triangle, r+1, c+1);

x = x<y ? x: y;

return triangle[r][c] + x;

}

int minimumTotal(vector<vector<int>>& triangle) {

return getMinPathSum(triangle, 0,0);

}

};

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

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

继续阅读

Coding algorithm, leetcode, 动态规划, 算法

在 Qt 中使用 TreeView

2018/05/11 9,111

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

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

TreeView {
    TableViewColumn {
        title: "Name"
        role: "fileName"
        width: 300
    }
    TableViewColumn {
        title: "Permissions"
        role: "filePermissions"
        width: 100
    }
    model: fileSystemModel
}

1

2

3

4

5

6

7

8

9

10

11

12

13

TreeView {

TableViewColumn {

title: "Name"

role: "fileName"

width: 300

}

TableViewColumn {

title: "Permissions"

role: "filePermissions"

width: 100

}

model: fileSystemModel

}

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

virtual int    columnCount(const QModelIndex &parent = QModelIndex()) const = 0;
virtual QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const = 0;
virtual QModelIndex    index(int row, int column, const QModelIndex &parent = QModelIndex()) const = 0;
virtual QModelIndex    parent(const QModelIndex &index) const = 0;
virtual int    rowCount(const QModelIndex &parent = QModelIndex()) const = 0;

1

2

3

4

5

virtual int columnCount(const QModelIndex &parent = QModelIndex()) const = 0;

virtual QVariant data(const QModelIndex &index, int role = Qt::DisplayRole) const = 0;

virtual QModelIndex index(int row, int column, const QModelIndex &parent = QModelIndex()) const = 0;

virtual QModelIndex parent(const QModelIndex &index) const = 0;

virtual int rowCount(const QModelIndex &parent = QModelIndex()) const = 0;

继续阅读

Coding qml, qt

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

2018/03/13 15,434

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

1. using 声明

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

// ...
{
    using std::map
    map<int, std::string> the_map; //ok
}
map<int, std::string> the_map2;  //error

1

2

3

4

5

6

// ...

{

using std::map

map<int, std::string> the_map; //ok

}

map<int, std::string> the_map2; //error

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

class Base{
protected:
    int bn1;
    int bn2;
};

class Derived: private Base{
public:
    using Base::bn1;
};

class DerivedAgain: public Derived{
};

int main(){
    Derived d;
    DerivedAgain da; 
    d.bn1 = 1;
    d.bn2 = 2; //error, 'bn2' is a private member of 'Base'
    da.bn1 = 3;  //ok
    std::cout<<d.bn1<<std::endl;

    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Base{

protected:

int bn1;

int bn2;

};

class Derived: private Base{

public:

using Base::bn1;

};

class DerivedAgain: public Derived{

};

int main(){

Derived d;

DerivedAgain da;

d.bn1 = 1;

d.bn2 = 2; //error, 'bn2' is a private member of 'Base'

da.bn1 = 3; //ok

std::cout<<d.bn1<<std::endl;

return 0;

}

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

继续阅读

Coding c++, c++11

豌豆

存档

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

结构化绑定定义及用法

C++20 Ranges

C++ 内存对齐

Chromium 的 Cookie 机制

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

一链表倒置

题目一 Reverse Linked List

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

例题一 : Triangle

解法一：

在 Qt 中使用 TreeView

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

1. using 声明

页面

近期文章

归档

分类目录

链接

存档

结构化绑定定义及用法

一 链表倒置

题目 一 Reverse Linked List

例题 一 : Triangle

解法一：

1. using 声明

页面

近期文章

归档

分类目录

标签

链接

一链表倒置

题目一 Reverse Linked List

例题一 : Triangle