Cpp

map memory layout

Source

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <map>
#include <iostream>

void func(std::map<int, int> const &mapping) {
    for (auto &data : mapping) {
        std::cout << data.first << data.second << "\n";
    }
}

int main () {
    std::map<int, int> mapping{{1,2},{2,3},{3,4},{4,5},
        					 {9,10},{10,11},{11,12},{12,13}};

    func(mapping);

    std::cout << "Program end\n";
    return 0;
}

Debug

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
> g++ -O1 map.cpp -o map
> gdb map

(gdb) br func
Breakpoint 1 at 0x12c9
(gdb) run

(gdb) x /16gx $rdi
0x7fffffffda20: 0x00007ffff7fbcee0      0x00007fff00000000
0x7fffffffda30: 0x000055555556af40      0x000055555556aeb0
0x7fffffffda40: 0x000055555556b000      0x0000000000000008
0x7fffffffda50: 0x0000000200000001      0x0000000300000002
0x7fffffffda60: 0x0000000400000003      0x0000000500000004
0x7fffffffda70: 0x0000000a00000009      0x0000000b0000000a
0x7fffffffda80: 0x0000000c0000000b      0x0000000d0000000c
0x7fffffffda90: 0x00007ffff7dc2fc8      0xc87494bbadcfcc00

Layout

Node节点布局

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
(gdb) x /6gx 0x000055555556aeb0  # begin
0x55555556aeb0: 0x0000000000000001      0x000055555556aee0 # 父节点
0x55555556aec0: 0x0000000000000000      0x0000000000000000
0x55555556aed0: 0x0000000200000001      0x0000000000000031
(gdb) x /6gx 0x000055555556b000 # end
0x55555556b000: 0x0000000000000000      0x000055555556afd0 # 父节点
0x55555556b010: 0x0000000000000000      0x0000000000000000
0x55555556b020: 0x0000000d0000000c      0x000000000000efe1
(gdb) x /6gx 0x000055555556aee0
0x55555556aee0: 0x0000000000000000      0x000055555556af40
0x55555556aef0: 0x000055555556aeb0      0x000055555556af10
0x55555556af00: 0x0000000300000002      0x0000000000000031

(gdb) x /6gx 0x000055555556af40 #红黑树根节点 - 例外
0x55555556af40: 0x0000000000000001      0x00007fffffffda28 # 指向map结构体
0x55555556af50: 0x000055555556aee0      0x000055555556afa0
0x55555556af60: 0x0000000500000004      0x0000000000000031
1. 红黑标志 
	enum _Rb_tree_color { _S_red = false, _S_black = true };
2. 父节点
3. 左树节点
4. 右树节点
5. std::pair数据: 先first数据, 后second数据(big-endian (BE) or little-endian (LE) 影响数据布局)

Map 结构体的memory Layout(_Rb_tree_header)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(gdb) x /16gx $rdi
0x7fffffffda20: 0x00007ffff7fbcee0      0x00007fff00000000
0x7fffffffda30: 0x000055555556af40      0x000055555556aeb0
0x7fffffffda40: 0x000055555556b000      0x0000000000000008
0x7fffffffda50: 0x0000000200000001      0x0000000300000002
0x7fffffffda60: 0x0000000400000003      0x0000000500000004
0x7fffffffda70: 0x0000000a00000009      0x0000000b0000000a
0x7fffffffda80: 0x0000000c0000000b      0x0000000d0000000c
0x7fffffffda90: 0x00007ffff7dc2fc8      0xc87494bbadcfcc00
1. 1rd addr: 不需要关心
2. 2rd addr: 红黑标志
3. 3rd addr: 二叉树的根节点
4. 4rd addr: 二叉树的begin
5. 5rd addr: 二叉树的end
6. 6rd addr: 当前数据数量
   后面是初始化列表的数据, 可以看到结构体初始化的数据(垃圾数据, 后续操作不会修改其内容)
Share