CPP(十二)——常见容器内存布局#

1
#include <map>
2
#include <iostream>
3
#include <algorithm>
4
int main()
5
{
6
#include <map>
7

8
    std::map<std::string, int> scores;
9
    scores["alice"] = 95; // 插入/更新
10
    scores["bob"] = 88;
11
    scores["mj"] = 67;
12
    scores["miejianguo"] = 55;
13

14
    std::cout << scores["alice"]; // 读取：95
15
    auto it = scores.find("bob"); // 查找
16
    if (it != scores.end())
17
    { /* 找到了 */
18
        for (const auto &[name, score] : scores)
19
        {
20
            std::cout << name << ": " << score << "\n";
21
        }
22
    }
23
}

1
v51.__pair1_.__value_.__left_ = nullptr;
2
v51.__pair3_.__value_ = 0;
3
v51.__begin_node_ = &v51.__pair1_.__value_;

1
scores["alice"] = 95;
2
scores["bob"] = 88;
3
scores["mj"] = 67;
4
scores["miejianguo"] = 55;

1
strcpy((char *)&v50.__r_.__value_.__l.0, "\nalice");

1
v3 = std::__tree<...>::__find_equal<std::string>(
2
        this: &v51,        // 这个 map
3
        __parent: &v52,    // 输出参数：找到/应插入位置的父节点
4
        __v: &v50);        // 要找的 key = "\nalice"
5
v4 = *v3;                  // v4 = 该位置上的节点指针（若 key 已存在则非空）
6

7
ps：完整的类型v3 = std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string>,true>,std::allocator<std::__value_type<std::string,int>>>::__find_equal<std::string>(
8

9
很长，不过我们只需要把他当作map<string,int>即可。

1
if ( *v3 == nullptr )//在map里没找到对应的键，就开始创建一个节点。
2
  {
3
    v5 = operator new(a1: 0x40u);//operator new(0x40) 表示申请 0x40 = 64 字节内存，作为一个红黑树节点。
4
    data = v50.__r_.__value_.__l.__data_; //拿到键值
5
    *(_DWORD *)(v5 + 56) = 0;
6
    v7 = *(_OWORD *)v50.__r_.__value_.__l.gap0;
7
    memset(&v50, 0, sizeof(v50));
8
    v4 = (std::__tree_node_base<void *> *)v5;
9
    *(_QWORD *)(v5 + 48) = data;
10
    v8 = v52;
11
    *(_OWORD *)(v5 + 32) = v7;
12
    *(_QWORD *)v5 = 0;
13
    *(_QWORD *)(v5 + 8) = 0;
14
    *(_QWORD *)(v5 + 16) = v8;
15
    //把新创建的节点塞到树上
16
    *v3 = (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > >::__node_base_pointer)v5;
17

18
    //更新 __begin_node_：必要时更新最小节点入口。
19
    if ( v51.__begin_node_->__left_ != nullptr )
20
      v51.__begin_node_ = v51.__begin_node_->__left_;
21
    std::__tree_balance_after_insert[abi:v170000]<std::__tree_node_base<void *> *>(
22
      __root: v51.__pair1_.__value_.__left_,
23
      __x: *v3);//__tree_balance_after_insert：插入后进行红黑树平衡。
24
    ++v51.__pair3_.__value_;//节点数量加一。
25
  }
26
//__tree_balance_after_insert 是识别红黑树插入的重要特征。 它内部通常会处理节点颜色、父节点、叔叔节点，以及左旋、右旋等操作。
27
注意，不是每次插入都一定发生旋转。新节点插入后，可能只需要变色，也可能需要旋转和变色。

1
00000000 struct __cppobj std::__tree_node<std::__value_type<std::string,int>,void *> : std::__tree_node_base<void *> // sizeof=0x40
2
00000000 {
3
00000020     std::__tree_node<std::__value_type<std::string,int>,void *>::__node_value_type __value_;
4
00000040 };

1
00000000 struct std::__tree_end_node<...> // sizeof=0x8
2
00000000     pointer __left_;   // +0x00
3

4
00000000 struct __tree_node_base<void*> : __end_node_type // sizeof=0x20
5
00000000     <继承自 __tree_end_node>    // +0x00 ~ +0x07，8 字节
6
00000008     pointer __right_;           // +0x08
7
00000010     __parent_pointer __parent_; // +0x10
8
00000018     bool __is_black_;           // +0x18
9
00000019-1F  padding

1
v9 = v50.__r_.__value_.__s.0;
2
  *(_DWORD *)&v4[1].__is_black_ = 95;
3

4
v4[1]              // ① 数组下标（等价 *(v4 + 1)）
5
v4[1].__is_black_  // ② 取结构体成员（等价 (*(v4+1)).__is_black_）
6
& v4[1].__is_black_// ③ 取该成员的地址 → 得到指针
7
(_DWORD *) ...     // ④ 把指针强制转成“指向 4 字节整数”的指针
8
* (_DWORD *) ...   // ⑤ 解引用 → 一个可写的 4 字节整数左值
9
= 95;              // ⑥ 赋值
10

11
v4 类型是 __tree_node_base<void*> *，sizeof(*v4) = 0x20。
12

13
v4[1] = (char*)v4 + 0x20。
14

15
.__is_black_ 在基类里偏移 +0x18。
16

17
所以地址 = (char*)v4 + 0x20 + 0x18 = (char*)v4 + 0x38 = +56。

1
v50.__r_.__value_.__s.0 = (std::string::__short::$5662C175DA7CC34792E979125A88A1DA)6;
2
  *(_DWORD *)&v50.__r_.__value_.__l.gap0[1] = 6451042;//6451042就是bob
3
  v37.__ptr_ = std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string>,true>,std::allocator<std::__value_type<std::string,int>>>::find<std::string>(
4
                 this: &v51,
5
                 __v: &v50).__ptr_;//查到结果的指针。
6
  if ( (*(_BYTE *)&v50.__r_.__value_.__s.0 & 1) != 0 )
7

8

9
  if (&v51.__pair1_ != v37.__ptr_) //相当于if (it != scores.end())

1
begin_node = v51.__begin_node_;//相当于 auto it = scores.begin();
2
    if ( (std::__compressed_pair<std::__tree_end_node<std::__tree_node_base<void *> *>> *)v51.__begin_node_ != &v51.__pair1_ )
3
    {
4
      do
5
      {
6
        left_low = LOBYTE(begin_node[4].__left_);
7
        v40 = (left_low & 1) == 0;
8
        v41 = left_low >> 1;
9
        if ( v40 )
10
          left = (char *)&begin_node[4].__left_ + 1;
11
        else
12
          left = (const char *)begin_node[6].__left_;
13
        if ( v40 )
14
          v43 = v41;
15
        else
16
          v43 = (size_t)begin_node[5].__left_;
17
         //上面在处理字符串的sso
18
        v44 = std::__put_character_sequence[abi:v170000]<char,std::char_traits<char>>(
19
                __os: (std::ostream *)&std::cout,
20
                __str: left,
21
                __len: v43);
22
        v45 = std::__put_character_sequence[abi:v170000]<char,std::char_traits<char>>(__os: v44, __str: ": ", __len: 2u);
23
        v46 = (std::ostream *)std::ostream::operator<<(a1: v45, a2: LODWORD(begin_node[7].__left_));
24
        std::__put_character_sequence[abi:v170000]<char,std::char_traits<char>>(__os: v46, __str: "\n", __len: 1u);
25
          //输出。
26
        p_left = &begin_node[1].__left_->__left_;
27
        if ( p_left != nullptr )
28
        {
29
          do
30
          {
31
            v48 = (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > > *)p_left;
32
            p_left = (_QWORD *)*p_left;
33
          }
34
          while ( p_left != nullptr );
35
        }
36
        else
37
        {
38
          do
39
          {
40
            v48 = (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > > *)begin_node[2].__left_;
41
            v40 = v48->__begin_node_ == begin_node;
42
            begin_node = (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > >::__iter_pointer)v48;
43
          }
44
          while ( !v40 );
45
        }
46
        begin_node = (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > >::__iter_pointer)v48;
47
      }
48
      while ( v48 != (std::__tree<std::__value_type<std::string,int>,std::__map_value_compare<std::string,std::__value_type<std::string,int>,std::less<std::string >,true>,std::allocator<std::__value_type<std::string,int> > > *)&v51.__pair1_ );
49
    }
50
  }
51

52
把最后一部分简化下：寻找中序遍历的下一个节点。
53
p_left = &begin_node[1].__left_->__left_;//p_left = node->right->left;   // 右子树的左孩子
54

55
if (p_left != nullptr)
56
{
57
    do
58
    {
59
        v48 = ... p_left;
60
        p_left = (_QWORD *)*p_left;
61
    }
62
    while (p_left != nullptr);
63
}
64
else
65
{
66
    do
67
    {
68
        v48 = ... begin_node[2].__left_;
69
        v40 = v48->__begin_node_ == begin_node;
70
        begin_node = ... v48;
71
    }
72
    while (!v40);
73
}

1
#include <unordered_map>
2
#include <unordered_set>
3
#include <string>
4
int main()
5
{
6
    std::unordered_map<std::string, int> u;
7
    u["alice"] = 95;
8
    u["bob"] = 88;
9

10
    auto it = u.find("alice"); // 平均 O(1)
11
    u.count("alice");          // 0 或 1
12

13
    std::unordered_set<int> s = {3, 1, 2};
14
    s.insert(5);
15
    s.erase(3);
16
}

1
 u.__p3_.__value_ = 1.0;
2
  strcpy((char *)&v15, "\nalice");
3
  memset(&u, 0, 32);
4
  v13.__base_.__value_ = (std::string *)&v15;

1
v18.__node_ = __emplace_unique_key_args(
2
    this: &u,
3
    __k: (const std::string *)&v15,
4
    ...
5
).first;
6

7
LODWORD(v18.__node_[5].__next_) = 95;//对相应的键进行赋值。
8

9
//这里的内存布局我们稍后来看，为什么会在这里赋值。

1
__emplace_unique_key_args

1
if ( (value & 1) != 0 )
2
    operator delete(a1: v15.__table_.__p1_.__value_.__next_);
3
  LOBYTE(v15.__table_.__bucket_list_.__ptr_.__value_) = 6;
4
  *(_DWORD *)((char *)&v15.__table_.__bucket_list_.__ptr_.__value_ + 1) = 6451042;
5
  v13.__base_.__value_ = (std::string *)&v15;

1
if ( (v4 & 1) != 0 )
2
    operator delete(a1: v15.__table_.__p1_.__value_.__next_);
3
  strcpy((char *)&v15, "\nalice");
4
  std::__hash_table<std::__hash_value_type<std::string,int>,std::__unordered_map_hasher<std::string,std::__hash_value_type<std::string,int>,std::hash<std::string>,std::equal_to<std::string>,true>,std::__unordered_map_equal<std::string,std::__hash_value_type<std::string,int>,std::equal_to<std::string>,std::hash<std::string>,true>,std::allocator<std::__hash_value_type<std::string,int>>>::find<std::string>(
5
    this: &u,
6
    __k: (const std::string *)&v15);
7
  if ( ((__int64)v15.__table_.__bucket_list_.__ptr_.__value_ & 1) != 0 )
8
    operator delete(a1: v15.__table_.__p1_.__value_.__next_);

1
v5 = 0;
2
v13.__base_.__value_ = (std::string *)0x100000003LL;  // 两个 int 打包：低32=3, 高32=1
3
v14 = 2;                                              // 第三个 int = 2
4
memset(&v15, 0, 32);
5
v15.__table_.__p3_.__value_ = 1.0;                    // load factor
6

7
do {
8
    __emplace_unique_key_args<int,int const&>(
9
        &v15.__table_,
10
        __k: (int*)((char*)&v13 + v5),   // 第 v5/4 个 int
11
        __args: 同);
12
    v5 += 4;
13
} while (v5 != 12);                       // 3 个 int，12 字节

1
next = v15.__table_.__p1_.__value_.__next_;    // 链表头（所有节点串成单链表）
2
while (next) {
3
    v7 = next->__next_;
4
    operator delete(next);                      // 释放节点
5
    next = v7;
6
}
7
v8 = v15.__table_.__bucket_list_.__ptr_.__value_;
8
v15.__table_.__bucket_list_.__ptr_.__value_ = nullptr;
9
if (v8) operator delete(v8);                    // 释放 bucket 数组

1
v9 = u.__p1_.__value_.__next_;
2
while (v9) {
3
    v12 = v9->__next_;
4
    if (((__int64)v9[2].__next_ & 1) != 0)      // 节点里 string key 是长串 → 释放堆
5
        operator delete(v9[4].__next_);
6
    operator delete(v9);                         // 释放节点
7
    v9 = v12;
8
}
9
v10 = u.__bucket_list_.__ptr_.__value_;
10
u.__bucket_list_.__ptr_.__value_ = nullptr;
11
if (v10) operator delete(v10);                   // 释放 bucket 数组

1
std::__hash_table<int, ...>          // sizeof = 0x28
2
std::__hash_table<std::__hash_value_type<std::string,int>, ...> // sizeof = 0x28
3
两个结构体都是0x28
4
区别最大的点就是存储类型，一个是int，另一个是pair。

1
struct __hash_node_base<...> {          // 基类，+0x00
2
    __next_pointer __next_;             // +0x00  链指针（8 字节）
3
};
4

5
struct __hash_node<int,void*> : __hash_node_base<...> {  // sizeof=0x18
6
    size_t __hash_;                     // +0x08  缓存 hash（8 字节）
7
    int    __value_;                    // +0x10  存的 int（4 字节）
8
    // +0x14..0x17 padding（对齐到 8）
9
};
10
合并成下面
11
struct __hash_node<int> {        // 堆上，单独分配
12
    __next_pointer __next_;      // +0   链到下一个节点
13
    size_t         __hash_;      // +8   缓存的 hash 值
14
    int            __value_;     // +16  ←  insert 的 int 在这
15
};
16

17
std::__hash_table<int, hash<int>, equal_to<int>, alloc<int>> // sizeof=0x28
18
+0x00  __bucket_list_                    // 16 字节：哈希桶数组管理信息
19
//哈希核心思路就是hash = hash_function(key)  index = hash % bucket_count;
20
+0x10  __p1_   <__hash_node_base<...>>   // 8 字节：全局单链表头（所有节点串起来）
21
+0x18  __p2_   <unsigned long, hash<int>>// 16 字节：元素个数 size + 哈希函数
22
+0x20  __p3_   <float, equal_to<int>>    // 8 字节：max_load_factor + 空相等比较器
23
+0x24..0x27 padding

1
struct __hash_node_base {
2
    __next_pointer __next_;   // +0x10：全局单链表头
3
};

1
next = v15.__table_.__p1_.__value_.__next_;   // 取链表头
2
while (next) { v7 = next->__next_; delete(next); next = v7; }