豌豆

C++ 内存对齐

2021/01/08 2,061

如下两个结构体 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 4,229

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 3,199

一链表倒置

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

题目一 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 3,019

例题一 : 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 7,719

提示：本文中的 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 12,716

对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++11/14 新特性 (多线程)

2017/03/28 6,105

在 C++11 之前，C++ 标准并没有提供统一的并发编程标准，也没有提供语言级别的支持。这导致我们在编写可移植的多线程程序时很不方便，往往需要面向不同的平台进行不同的实现，或者引入一些第三方平台，如Boost,pthread_win32 等。从C++11开始，对并发编程进行了语言级别的支持，使用使用C++进行并发编程方便了很多。这里介绍C++11并发编程的相关特性。

1 线程

1.1 线程的创建

std::thread 的构造函数如下：

template< class Function, class... Args > 
explicit thread( Function&& f, Args&&... args );

1 2	template< class Function, class... Args > explicit thread( Function&& f, Args&&... args );

我们只需要提供线程函数或函数对象，即可以创建线程，并可以同时指定线程函数的参数。

#include <iostream>
#include <thread>
using namespace std;

void func(const string& str){
    cout<<str<<endl;
}

class FuncCls{
public:
    void operator()(){
        cout<<"Funcls called"<<endl;
    }
};

int main(void){
    thread t1(func,"Hello World");
    FuncCls fcls;
    thread t2(fcls);

    if(t1.joinable()){
        t1.join();
    }
    t2.join();
    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

25

26

#include <iostream>

#include <thread>

using namespace std;

void func(const string& str){

cout<<str<<endl;

}

class FuncCls{

public:

void operator()(){

cout<<"Funcls called"<<endl;

}

};

int main(void){

thread t1(func,"Hello World");

FuncCls fcls;

thread t2(fcls);

if(t1.joinable()){

t1.join();

}

t2.join();

return 0;

}

join函数将会阻塞线程，直到线程函数执行完毕，主线程才会接着执行。如果线程函数有返回值，返回值将被忽略。在使用线程对象的过程中，我们需要注意线程对象的生命周期。如果线程对象先于线程函数结束，那么将会出现不可预料的错误。可以通过线程阻塞的方式来等待线程函数执行完(join)，或让线程在后台执行。如果不希望线程被阻塞，可以调用线程的 detach() 函数，将线程与线程对象分离。但需要注意的是，detach 之后的线程无法再使用join来进行阻塞了，即detach之后的线程，我们无法控制了。当我们不确定一个线程是否可以join时，可以先使用 thead::joinable() 来进行判断。

另外，我们还可以通过 std::bind, lambda 来创建线程(其实就是使用函数对象创建线程)。

线程不可以被复制，但是可以被移动:
继续阅读

Coding c++, c++11, mutex, thread, 多线程

C++11/14 新特性(function/bind 可调用对象包装器与绑定器)

2017/02/28 5,553

1 可调用对象

在 C++ 中，可调用对象一般是指：

一个函数指针
一个重载 () 操作符的类对句(仿函数)
一个可被转换为函数指针的类对象
一个类成员函数指针

#include <iostream>

void func(void)
{
    std::cout<<"func(void) called"<<std::endl;
}

struct Foo
{
    void operator()(void)
    {
        std::cout<<"Foo::()(void) called"<<std::endl;
    }
};

struct Bar
{
    using ft_t = void(*)(void);
    static void func(void)
    {
        std::cout<<"Bar::func(void) called"<<std::endl;
    }

    operator ft_t(void)
    {
        return func;
    }
};

struct A
{
    int m_a;
    void mem_func(void)
    {
        std::cout<<"A:memfunc(void) called and m_a="<<m_a<<std::endl;
    }
};


int main() {
    //1.函数指针
    void(* func_ptr)(void) = &func;
    func_ptr();

    //2.仿函数
    Foo foo;
    foo();

    //3.可被转换为函数指针的类对象
    Bar bar;
    bar();

    //4.类成员函数指针或类成员指针
    void (A::*mem_func_ptr)(void) = &A::mem_func;
    int A::*mem_obj_ptr = &A::m_a;
    A aa;
    (aa.*mem_obj_ptr) = 123;
    (aa.*mem_func_ptr)();

    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

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

#include <iostream>

void func(void)

{

std::cout<<"func(void) called"<<std::endl;

}

struct Foo

{

void operator()(void)

{

std::cout<<"Foo::()(void) called"<<std::endl;

}

};

struct Bar

{

using ft_t = void(*)(void);

static void func(void)

{

std::cout<<"Bar::func(void) called"<<std::endl;

}

operator ft_t(void)

{

return func;

}

};

struct A

{

int m_a;

void mem_func(void)

{

std::cout<<"A:memfunc(void) called and m_a="<<m_a<<std::endl;

}

};

int main() {

//1.函数指针

void(* func_ptr)(void) = &func;

func_ptr();

//2.仿函数

Foo foo;

foo();

//3.可被转换为函数指针的类对象

Bar bar;

bar();

//4.类成员函数指针或类成员指针

void (A::*mem_func_ptr)(void) = &A::mem_func;

int A::*mem_obj_ptr = &A::m_a;

A aa;

(aa.*mem_obj_ptr) = 123;

(aa.*mem_func_ptr)();

return 0;

}

上例中的这些对象(func_ptr,foo,bar,mem_func_ptr,mem_obj_ptr) 均可称之为 “可调用对象”。相应的，其类型可被称作“可调用类型”。注意这里只有成员函数有成员函数指针而没有函数类型或函数引用类型，这是因为函数类型并不能直接用于定义对象，而函数引用或以看做一个 const 的函数指针。可调用对象具有比较统一的调用形式，即使用括号操作(除成员函数指针)，而定义的方法各不一样。这样我们在试图使用统一的方式保存，或传递一个可调用对象时，会十分烦琐。

2 std::function 可调用对象包装器

std::function 是一个类模板，它可以容纳除了类成员(函数)指针之外的所有可调用对象。通过指定它的模板参数，它可以用统一的方式处理函数、函数对象、函数指针，并允许保存和延迟调用它们。
继续阅读

Coding c++, c++11

豌豆

存档

C++ 内存对齐

Chromium 的 Cookie 机制

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

一链表倒置

题目一 Reverse Linked List

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

例题一 : Triangle

解法一：

在 Qt 中使用 TreeView

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

1. using 声明

C++11/14 新特性 (多线程)

1 线程

1.1 线程的创建

C++11/14 新特性(function/bind 可调用对象包装器与绑定器)

1 可调用对象

2 std::function 可调用对象包装器

页面

近期文章

归档

分类

链接

存档

一 链表倒置

题目 一 Reverse Linked List

例题 一 : Triangle

解法一：

1. using 声明

1 线程

1.1 线程的创建

1 可调用对象

2 std::function 可调用对象包装器

页面

近期文章

归档

分类

标签

链接

一链表倒置

题目一 Reverse Linked List

例题一 : Triangle