{"id":17000,"date":"2024-03-07T15:25:07","date_gmt":"2024-03-07T15:25:07","guid":{"rendered":"http:\/\/www.max-sperling.bplaced.net\/?p=17000"},"modified":"2024-03-27T16:24:09","modified_gmt":"2024-03-27T16:24:09","slug":"typical-memory-layout-of-stdunordered_set","status":"publish","type":"post","link":"http:\/\/www.max-sperling.bplaced.net\/?p=17000","title":{"rendered":"Layout of std::unordered_set (libstdc++)"},"content":{"rendered":"<p><strong>Layout<\/strong><\/p>\n<p><img decoding=\"async\" src=\"http:\/\/www.max-sperling.bplaced.net\/wp-content\/uploads\/2017\/06\/Unordered_set.png\" class=\"aligncenter\" \/><\/p>\n<ul>\n<li>The meta element on the stack consumes 7 words (56 Byte on x64, 28 Byte on x86).<\/li>\n<li>Each node on the heap has a size of 1 word (pointer to next node) and sizeof(val).<\/li>\n<li>The number and size of the buckets depends on the amount of values and collisions.<\/li>\n<\/ul>\n<hr>\n<p><strong>Rehashing<\/strong><\/p>\n<p>Rehashing happens when, before adding one item, the following condition is true:<\/p>\n<pre>\r\n(_M_element_count + 1) > (_M_bucket_count * (double)_M_max_load_factor)\r\n<\/pre>\n<p>Source: <a href=\"https:\/\/github.com\/gcc-mirror\/gcc\/blob\/c891d8dc23e1a46ad9f3e757d09e57b500d40044\/libstdc%2B%2B-v3\/src\/c%2B%2B11\/hashtable_c%2B%2B0x.cc#L101\">gcc\/libstdc++-v3\/src\/c++11\/hashtable_c++0x.cc<\/a><\/p>\n<hr>\n<p><strong>Example<\/strong><\/p>\n<pre class=\"brush: cpp; title: main.cpp; notranslate\" title=\"main.cpp\">\r\n#include &lt;unordered_set&gt;\r\n\r\nint main()\r\n{\r\n    std::unordered_set&lt;int&gt; uset = { 1, 2, 3, 4, 5 };\r\n    return 0;\r\n}\r\n<\/pre>\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 \/x uset\r\n$1 = {\r\n  _M_h = {...\r\n          _M_buckets = 0x55555556e2d0,\r\n          _M_bucket_count = 0xd, \r\n          _M_before_begin = {_M_nxt = 0x55555556e3a0},\r\n          _M_element_count = 0x5,\r\n          _M_rehash_policy = {static _S_growth_factor = 0x2,\r\n                              _M_max_load_factor = 0x3f800000,\r\n                              _M_next_resize = 0xd}, \r\n          _M_single_bucket = 0x0}}\r\n(gdb) p sizeof(uset)\r\n$2 = 56\r\n(gdb) x\/7xg &uset\r\n0x7fffffffddf0:\t0x000055555556e2d0 0x000000000000000d\r\n0x7fffffffde00:\t0x000055555556e3a0 0x0000000000000005\r\n0x7fffffffde10:\t0x000000003f800000 0x000000000000000d\r\n0x7fffffffde20:\t0x0000000000000000\r\n(gdb) x\/13xg uset._M_h._M_buckets\r\n0x55555556e2d0:\t0x0000000000000000 0x000055555556e340\r\n0x55555556e2e0:\t0x000055555556e360 0x000055555556e380\r\n0x55555556e2f0:\t0x000055555556e3a0 0x00007fffffffde00\r\n0x55555556e300:\t0x0000000000000000 0x0000000000000000\r\n0x55555556e310:\t0x0000000000000000 0x0000000000000000\r\n0x55555556e320:\t0x0000000000000000 0x0000000000000000\r\n0x55555556e330:\t0x0000000000000000\r\n(gdb) x\/2xg 0x000055555556e3a0\r\n0x55555556e3a0:\t0x000055555556e380 0x0000000000000005\r\n(gdb) x\/2xg 0x000055555556e380\r\n0x55555556e380:\t0x000055555556e360 0x0000000000000004\r\n(gdb) x\/2xg 0x000055555556e360\r\n0x55555556e360:\t0x000055555556e340 0x0000000000000003\r\n(gdb) x\/2xg 0x000055555556e340\r\n0x55555556e340:\t0x000055555556e2b0 0x0000000000000002\r\n(gdb) x\/2xg 0x000055555556e2b0\r\n0x55555556e2b0:\t0x0000000000000000 0x0000000000000001\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Layout The meta element on the stack consumes 7 words (56 Byte on x64, 28 Byte on x86). Each node<\/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\/17000"}],"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=17000"}],"version-history":[{"count":14,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17000\/revisions"}],"predecessor-version":[{"id":17293,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17000\/revisions\/17293"}],"wp:attachment":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17000"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17000"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17000"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}