Layout of std:deque (libstdc++)

Layout

  • The meta element on the stack consumes 10 words (80 Byte on x64, 40 Byte on x86).
  • Each chunk on the heap has a size of 512 Byte1 if sizeof(val) <= 256 Byte, else sizeof(val).
  • The number of the chunks and those the size of the map depends on the amount of values.

1 gcc/libstdc++-v3/include/bits/stl_deque.h

Example

#include <deque>

int main()
{
    std::deque<int> deq = { 1, 2, 3, 4, 5 };
    return 0;
}

$ 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 /x deq
$1 = {...
  _M_impl = {...
             _M_map = 0x55555556c2b0,
             _M_map_size = 0x8,
             _M_start = {_M_cur = 0x55555556c300,
                         _M_first = 0x55555556c300,
                         _M_last = 0x55555556c500,
                         _M_node = 0x55555556c2c8}, 
             _M_finish = {_M_cur = 0x55555556c314,
                          _M_first = 0x55555556c300,
                          _M_last = 0x55555556c500,
                          _M_node = 0x55555556c2c8}} ...}
(gdb) p sizeof(deq)
$1 = 80
(gdb) x/8g deq._M_impl._M_map
0x55555556c2b0:	0x0000000000000000 0x0000000000000000
0x55555556c2c0:	0x0000000000000000 0x000055555556c300
0x55555556c2d0:	0x0000000000000000 0x0000000000000000
0x55555556c2e0:	0x0000000000000000 0x0000000000000000
(gdb) x/5w 0x000055555556c300
0x55555556c300:	0x00000001	0x00000002	0x00000003	0x00000004
0x55555556c310:	0x00000005