Understanding memory allocation

Question

I am trying to understand how memory is allocated by the std::list data structure. I made a small test program

#include <cstdio>
#include <vector>
#include <iostream>
#include <string>
#include <list>

class MyClass
{
public:

 MyClass();
~MyClass(){}

private:
std::list<unsigned char> numlist;
};

MyClass::MyClass()
{
numlist.push_back(1);
}

int main()
{ 

 MyClass c; // instantiate
}

I ran the above snippet in valgrind

$valgrind --leak-check=full ./indepth 
==32330== HEAP SUMMARY:
==32330==     in use at exit: 0 bytes in 0 blocks
==32330==   total heap usage: 1 allocs, 1 frees, 24 bytes allocated

Please help me to understand why 24 bytes were allocated here.

Answer 1

Without knowing more about the particular compiler and it's options, it's hard to give a definitive answer. But the call to push_back will allocate a node for the list element that it creates, and that node will have two pointers (one for the next node and one for the previous), and an int that holds the stored value. To get details on the sizes of those parts, run this program:

#include <iostream>

int main() {
    std::cout << sizeof(int*) << ", " << sizeof(unsigned char) << '\n';
    return 0;
}

That will tell you how big a pointer is and how big an int is.

Answer 2

The exact size of every element in an std::list depends on the STL implementation, but normally it is implemented as double linked list, that means that every node (which represents the elements) requires at least 3 data members (previous node, next node, to implement the double link list, and the data).

In gcc implementation, the file std_list.h class _List_node contains the definition of this node. 2 pointers (2 * 4 bytes in 32bits or 2 * 8 bytes in 64bits) plus sizeof(data).

Additional to that, the list may have to maintain some other internal info like the size (since C++11 is mandated by the standard that std::list::size() is O(1)).

Notes:

STL implementation = Standard Library implementation (the implementation of the C++ Standard Library that came with the compiler or is configured to be used by the compiler)

• in the case of gcc is libstdc++
• in case of clang could be libc++ (the clang implementation) or libstdc++ (the gcc implementation)
• in case of VC++, their internal implementation (by Dinkumware).

There's other STL implementation like STLPort, etc... And these details are implementation dependent. The only way to be sure is looking the code of the specific version of the STL implementation and the exact size could change any time.