豌豆

结构化绑定定义及用法

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

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

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

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);

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;
}

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

继续阅读

函数重载（Function Overloading）允许在同一个作用域内定义多个功能类似但参数不同的函数。这些函数可以有相同的名字，但必须有不同的参数列表（参数的数量、类型或顺序不同）。编译器通过参数列表来决定调用哪个函数。

大部分语言并不支持返回值类型的重载。包括C++。

// OK
std::string to_string(int i);
std::string to_string(bool b);

std::string si = to_string(42);
std::string sb = to_string(true);

// ERROR
int from_string(std::string_view s);
bool from_string(std::string_view s);

int i = from_string("42");
bool b = from_string("false");

C++ 11 的一个新特性，使我们可以实现一个 接近 函数返回值重载的功能。即 [自定义转换函数][https://en.cppreference.com/w/cpp/language/cast_operator] 。来看下面的例子：

struct to_string_t
{
    std::string_view s;  //string_view from c++17

    operator int() const; 
    operator bool() const;
};

int i = to_string_t{"42"};  //  operator int() const; 
bool b = to_string_t{"true"};  //  operator bool() const;

需要注意，编译器需要知道转换的目标类型。如 auto i = to_string_t{"42"} ，编译器不知道应该调用哪个重载。
让我们回到开始：如何将 to_string_t 作为返回值，似乎就可以完成 函数返回值重载 的功能:

继续阅读

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());

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

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

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

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

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

继续阅读

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

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;

结果如下：

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 的倍数。

继续阅读

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

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 文件。

继续阅读

一 链表倒置

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

题目 一 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 保护下一个欲倒置的元素

  代码：

  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;
      }
  };

  

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

继续阅读

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

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

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

继续阅读

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

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

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;

继续阅读