{"id":17168,"date":"2024-03-19T20:48:22","date_gmt":"2024-03-19T20:48:22","guid":{"rendered":"http:\/\/www.max-sperling.bplaced.net\/?p=17168"},"modified":"2024-03-20T10:19:10","modified_gmt":"2024-03-20T10:19:10","slug":"layout-of-stdset-libstdc","status":"publish","type":"post","link":"http:\/\/www.max-sperling.bplaced.net\/?p=17168","title":{"rendered":"Layout of std:set (libstdc++)"},"content":{"rendered":"<p><strong>Source code<\/strong><\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;set&gt;\r\n\r\nint main()\r\n{\r\n    std::set&lt;int&gt; s = { 2, 4, 1, 5, 3 };\r\n    return 0;\r\n}\r\n<\/pre>\n<hr>\n<p><strong>Analysis<\/strong><\/p>\n<pre>\r\n$ g++ --version\r\ng++ (Ubuntu 13.2.0-4ubuntu3) 13.2.0\r\n$ g++ main.cpp -g\r\n$ gdb a.out\r\n(gdb) b 6\r\n(gdb) r\r\n(gdb) disable pretty-printer\r\n(gdb) p s\r\n$1 = {\r\n    _M_t = {\r\n        _M_impl = { ...\r\n            &lt;std::_Rb_tree_header&gt; = {\r\n                _M_header = {\r\n                    _M_color = std::_S_red,\r\n                    _M_parent = 0x55555556c2b0,\r\n                    _M_left = 0x55555556c310, \r\n                    _M_right = 0x55555556c340},\r\n                _M_node_count = 5}, ...}}}\r\n(gdb) p sizeof(s)\r\n$2 = 48\r\n(gdb) x\/6xg &s\r\n0x7fffffffde00:\t0x0000000000000000 0x0000000000000000\r\n0x7fffffffde10:\t0x000055555556c2b0 0x000055555556c310\r\n0x7fffffffde20:\t0x000055555556c340 0x0000000000000005\r\n(gdb) p *s._M_t._M_impl._M_header._M_parent\r\n$3 = {\r\n    _M_color = std::_S_black,\r\n    _M_parent = 0x7fffffffde08,\r\n    _M_left = 0x55555556c310,\r\n    _M_right = 0x55555556c2e0}\r\n(gdb) p *s._M_t._M_impl._M_header._M_parent._M_left\r\n$4 = {\r\n    _M_color = std::_S_black,\r\n    _M_parent = 0x55555556c2b0,\r\n    _M_left = 0x0,\r\n    _M_right = 0x0}\r\n(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right\r\n$5 = {\r\n    _M_color = std::_S_black,\r\n    _M_parent = 0x55555556c2b0,\r\n    _M_left = 0x55555556c370,\r\n    _M_right = 0x55555556c340}\r\n(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right._M_left\r\n$6 = {\r\n    _M_color = std::_S_red,\r\n    _M_parent = 0x55555556c2e0,\r\n    _M_left = 0x0,\r\n    _M_right = 0x0}\r\n(gdb) p *s._M_t._M_impl._M_header._M_parent._M_right._M_right\r\n$7 = {\r\n    _M_color = std::_S_red,\r\n    _M_parent = 0x55555556c2e0,\r\n    _M_left = 0x0,\r\n    _M_right = 0x0}\r\n<\/pre>\n<p>GDB is trying to hide the keys from us. \ud83d\ude41 We don&#8217;t let him. \ud83d\ude42<\/p>\n<pre>\r\n(gdb) x\/5xg s._M_t._M_impl._M_header._M_parent\r\n0x55555556c2b0:\t0x0000000000000001 0x00007fffffffde08\r\n0x55555556c2c0:\t0x000055555556c310 0x000055555556c2e0\r\n0x55555556c2d0:\t0x0000000000000002\r\n(gdb) x\/5xg s._M_t._M_impl._M_header._M_parent._M_left\r\n0x55555556c310:\t0x0000000000000001 0x000055555556c2b0\r\n0x55555556c320:\t0x0000000000000000 0x0000000000000000\r\n0x55555556c330:\t0x0000000000000001\r\n(gdb) x\/5xg s._M_t._M_impl._M_header._M_parent._M_right\r\n0x55555556c2e0:\t0x0000000000000001 0x000055555556c2b0\r\n0x55555556c2f0:\t0x000055555556c370 0x000055555556c340\r\n0x55555556c300:\t0x0000000000000004\r\n(gdb) x\/5xg s._M_t._M_impl._M_header._M_parent._M_right._M_left\r\n0x55555556c370:\t0x0000000000000000 0x000055555556c2e0\r\n0x55555556c380:\t0x0000000000000000 0x0000000000000000\r\n0x55555556c390:\t0x0000000000000003\r\n(gdb) x\/5xg s._M_t._M_impl._M_header._M_parent._M_right._M_right\r\n0x55555556c340:\t0x0000000000000000 0x000055555556c2e0\r\n0x55555556c350:\t0x0000000000000000 0x0000000000000000\r\n0x55555556c360:\t0x0000000000000005\r\n<\/pre>\n<hr>\n<p><strong>Layout<\/strong><\/p>\n<pre>\r\n                       (key = 2)\r\ns._M_parent ------------> c2b0\r\n (root)        (key = 1)   ||   (key = 4)\r\ns._M_left -----> c310 -----||----- c2e0\r\n (most left)     0  0    (key = 3)  ||  (key = 5)\r\n                            c370 ---||--- c340 <---|\r\n                            0  0          0  0     |\r\ns._M_right ----------------------------------------|\r\n (most right)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Source code Analysis $ g++ &#8211;version g++ (Ubuntu 13.2.0-4ubuntu3) 13.2.0 $ g++ main.cpp -g $ gdb a.out (gdb) b 6<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[80,28],"tags":[],"_links":{"self":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17168"}],"collection":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17168"}],"version-history":[{"count":27,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17168\/revisions"}],"predecessor-version":[{"id":17195,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17168\/revisions\/17195"}],"wp:attachment":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17168"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17168"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17168"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}