Source code
#include <set>
int main()
{
std::set<int> s = { 2, 4, 1, 5, 3 };
return 0;
}
Analysis
$ g++ --version
g++ (Ubuntu 13.2.0-4ubuntu3) 13.2.0
$ g++ main.cpp -g
$ gdb a.out
(gdb) b 6
(gdb) r
(gdb) disable pretty-printer
(gdb) p s
$1 = {
_M_t = {
_M_impl = { ...
<std::_Rb_tree_header> = {
_M_header = {
_M_color = std::_S_red,
_M_parent = 0x55555556c2b0,
_M_left = 0x55555556c310,
_M_right = 0x55555556c340},
_M_node_count = 5}, ...}}}
(gdb) p sizeof(s)
$2 = 48
(gdb) x/6xg &s
0x7fffffffde00: 0x0000000000000000 0x0000000000000000
0x7fffffffde10: 0x000055555556c2b0 0x000055555556c310
0x7fffffffde20: 0x000055555556c340 0x0000000000000005
(gdb) p *s._M_t._M_impl._M_header._M_parent
$3 = {
_M_color = std::_S_black,
_M_parent = 0x7fffffffde08,
_M_left = 0x55555556c310,
_M_right = 0x55555556c2e0}
(gdb) p *s._M_t._M_impl._M_header._M_parent._M_left
$4 = {
_M_color = std::_S_black,
_M_parent = 0x55555556c2b0,
_M_left = 0x0,
_M_right = 0x0}
(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right
$5 = {
_M_color = std::_S_black,
_M_parent = 0x55555556c2b0,
_M_left = 0x55555556c370,
_M_right = 0x55555556c340}
(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right._M_left
$6 = {
_M_color = std::_S_red,
_M_parent = 0x55555556c2e0,
_M_left = 0x0,
_M_right = 0x0}
(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right._M_right
$7 = {
_M_color = std::_S_red,
_M_parent = 0x55555556c2e0,
_M_left = 0x0,
_M_right = 0x0}
GDB is trying to hide the keys from us. 🙁 We don’t let him. 🙂
(gdb) x/5xg s._M_t._M_impl._M_header._M_parent 0x55555556c2b0: 0x0000000000000001 0x00007fffffffde08 0x55555556c2c0: 0x000055555556c310 0x000055555556c2e0 0x55555556c2d0: 0x0000000000000002 (gdb) x/5xg s._M_t._M_impl._M_header._M_parent._M_left 0x55555556c310: 0x0000000000000001 0x000055555556c2b0 0x55555556c320: 0x0000000000000000 0x0000000000000000 0x55555556c330: 0x0000000000000001 (gdb) x/5xg s._M_t._M_impl._M_header._M_parent._M_right 0x55555556c2e0: 0x0000000000000001 0x000055555556c2b0 0x55555556c2f0: 0x000055555556c370 0x000055555556c340 0x55555556c300: 0x0000000000000004 (gdb) x/5xg s._M_t._M_impl._M_header._M_parent._M_right._M_left 0x55555556c370: 0x0000000000000000 0x000055555556c2e0 0x55555556c380: 0x0000000000000000 0x0000000000000000 0x55555556c390: 0x0000000000000003 (gdb) x/5xg s._M_t._M_impl._M_header._M_parent._M_right._M_right 0x55555556c340: 0x0000000000000000 0x000055555556c2e0 0x55555556c350: 0x0000000000000000 0x0000000000000000 0x55555556c360: 0x0000000000000005
Layout
(key = 2)
s._M_parent ------------> c2b0
(root) (key = 1) || (key = 4)
s._M_left -----> c310 -----||----- c2e0
(most left) 0 0 (key = 3) || (key = 5)
c370 ---||--- c340 <---|
0 0 0 0 |
s._M_right ----------------------------------------|
(most right)