版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1344538
先看一个例子:
1 #include <map>
2
3 int main()
4 {
5 std::map<int,int> iMap;
6
7 iMap[5] = 6;
8 iMap[8] = 20;
9 iMap[2] = 80;
10
11 return 0;
12 }
看一下汇编:
(gdb) disassemble main
Dump of assembler code for function main:
0x080486e4 <+0>: push %ebp
0x080486e5 <+1>: mov %esp,%ebp
0x080486e7 <+3>: and $0xfffffff0,%esp
0x080486ea <+6>: push %esi
0x080486eb <+7>: push %ebx
0x080486ec <+8>: sub $0x48,%esp
0x080486ef <+11>: lea 0x1c(%esp),%eax
0x080486f3 <+15>: mov %eax,(%esp)
0x080486f6 <+18>: call 0x80487b6 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEEC2Ev>
0x080486fb <+23>: movl $0x5,0x34(%esp)
0x08048703 <+31>: lea 0x34(%esp),%eax
0x08048707 <+35>: mov %eax,0x4(%esp)
0x0804870b <+39>: lea 0x1c(%esp),%eax
0x0804870f <+43>: mov %eax,(%esp)
0x08048712 <+46>: call 0x8048830 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEEixERS3_>
0x08048717 <+51>: movl $0x6,(%eax)
0x0804871d <+57>: movl $0x8,0x38(%esp)
0x08048725 <+65>: lea 0x38(%esp),%eax
0x08048729 <+69>: mov %eax,0x4(%esp)
0x0804872d <+73>: lea 0x1c(%esp),%eax
0x08048731 <+77>: mov %eax,(%esp)
0x08048734 <+80>: call 0x8048830 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEEixERS3_>
0x08048739 <+85>: movl $0x14,(%eax)
0x0804873f <+91>: movl $0x2,0x3c(%esp)
0x08048747 <+99>: lea 0x3c(%esp),%eax
0x0804874b <+103>: mov %eax,0x4(%esp)
0x0804874f <+107>: lea 0x1c(%esp),%eax
0x08048753 <+111>: mov %eax,(%esp)
0x08048756 <+114>: call 0x8048830 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEEixERS3_>
0x0804875b <+119>: movl $0x50,(%eax)
0x08048761 <+125>: mov $0x0,%ebx
0x08048766 <+130>: lea 0x1c(%esp),%eax
0x0804876a <+134>: mov %eax,(%esp)
0x0804876d <+137>: call 0x80487a2 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEED2Ev>
0x08048772 <+142>: mov %ebx,%eax
0x08048774 <+144>: add $0x48,%esp
0x08048777 <+147>: pop %ebx
0x08048778 <+148>: pop %esi
0x08048779 <+149>: mov %ebp,%esp
0x0804877b <+151>: pop %ebp
0x0804877c <+152>: ret
0x0804877d <+153>: mov %edx,%ebx
0x0804877f <+155>: mov %eax,%esi
0x08048781 <+157>: lea 0x1c(%esp),%eax
0x08048785 <+161>: mov %eax,(%esp)
0x08048788 <+164>: call 0x80487a2 <_ZNSt3mapIiiSt4lessIiESaISt4pairIKiiEEED2Ev>
0x0804878d <+169>: mov %esi,%eax
0x0804878f <+171>: mov %ebx,%edx
0x08048791 <+173>: mov %eax,(%esp)
0x08048794 <+176>: call 0x804861c <_Unwind_Resume@plt>
End of assembler dump.
由0x080486f6可以看到,esp+0x1c是map的this指针.
在0x080486f6, 0x08048712,0x08048734, 0x08048756, 0x0804876d 打断点:
(gdb) b *0x080486f6
Breakpoint 1 at 0x80486f6
(gdb) b *0x08048712
Breakpoint 2 at 0x8048712
(gdb) b *0x08048734
Breakpoint 3 at 0x8048734
(gdb) b *0x08048756
Breakpoint 4 at 0x8048756
(gdb) b *0x0804876d
Breakpoint 5 at 0x804876d
先看一下map在调用构造函数前后的变化:
(gdb) r
Starting program: /home/xuzhina/code/s3/xuzhina_dump_c07_s3
Breakpoint 1, 0x080486f6 in main ()
(gdb) x /8x $esp+0x1c
0xbffff2bc: 0x08048568 0x008702b8 0x0804b3c4 0xbffff2f8
0xbffff2cc: 0x08049659 0x028ea550 0x08048412 0x00000000
(gdb) ni
0x080486fb in main ()
(gdb) x /8x $esp+0x1c
0xbffff2bc: 0x08048568 0x00000000 0x00000000 0xbffff2c0
0xbffff2cc: 0xbffff2c0 0x00000000 0x08048412 0x00000000
参照bits/stl_map.h, bits/stl_tree.h里面的_Rb_tree_node_base, _Rb_tree_node, _Rb_tree, _Rb_tree_impl, map
的定义可知,头节点被初始化为
{
_M_key_compare = 0x08048568,
_M_color = 0x00000000,
_M_parent = 0x00000000,
_M_left = 0xbffff2c0,
_M_right = 0xbffff2c0,
_M_node_count = 0x00000000,
}
再看一下,当map放入第一个元素时,会变成什么样.
(gdb) c
Continuing.
Breakpoint 2, 0x08048712 in main ()
(gdb) ni
0x08048717 in main ()
(gdb) ni
0x0804871d in main ()
(gdb) x /8x $esp+0x1c
0xbffff2bc: 0x08048568 0x00000000 0x0804c008 0x0804c008
0xbffff2cc: 0x0804c008 0x00000001 0x00000005 0x00000000
(gdb) x /8x 0x0804c008
0x804c008: 0x00000001 0xbffff2c0 0x00000000 0x00000000
0x804c018: 0x00000005 0x00000006 0x00000000 0x00020fe1
可以看到头节点和第一个节点的值如下:
头节点 | 第一个节点 |
---|---|
{ _M_key_compare = 0x08048568, _M_color = 0x00000000, _M_parent = 0x0804c008, _M_left = 0x0804c008, _M_right = 0x0804c008, _M_node_count = 0x00000001, } | { _M_color = 0x00000001, _M_parent = 0xbffff2c0, _M_left = 0x00000000, _M_right = 0x00000000, _M_value_field.first = 0x00000005, _M_value_field.second =0x00000006 } |
继续进行探究,可以得出一堆这样的数据
(gdb) x /8x $esp+0x1c
0xbffff2bc: 0x08048568 0x00000000 0x0804c008 0x0804c048
0xbffff2cc: 0x0804c028 0x00000003 0x00000005 0x00000008
(gdb) x /8x 0x0804c008
0x804c008: 0x00000001 0xbffff2c0 0x0804c048 0x0804c028
0x804c018: 0x00000005 0x00000006 0x00000000 0x00000021
(gdb) x /8x 0x0804c048
0x804c048: 0x00000000 0x0804c008 0x00000000 0x00000000
0x804c058: 0x00000002 0x00000050 0x00000000 0x00020fa1
(gdb) x /8x 0x0804c028
0x804c028: 0x00000000 0x0804c008 0x00000000 0x00000000
0x804c038: 0x00000008 0x00000014 0x00000000 0x00000021
用图来表示则如下
由上面可以得出map的特征:
1. map对象有五个成员_M_node_count标明map有多少个元素,三个指针分别指向树中最左的节点,树的根节点,树的最右节点,_M_color表明是红树还是黑树,_M_key_compare指向比较函数
2. 树的根节点的_M_parent指向头节点
3. 每一个节点的值都紧跟着_M_right