What is the size of each element in std::list?

Question

std::list uses linked lists in its implementation, how large are each of the elements in the list (minus payload)?

By testing, using mingw (not mingw-64) on a windows 7 machine each element takes up 24 bytes for each element of an int.

A pointer to the left and a pointer to the right is only 4+4=8 bytes though! and an int is only 4 bytes (as determined by sizeof(void*) and sizeof(int)), so I'm curious, wheres the extra space going?

(test involved making many elements, seeing the size of the program, making more elements and again seeing the size of the program, taking the difference)

Check the source or fire it up in your debugger and print it. — jthill
Yet another way: use a memory handler to track the memory used by your program. Then create a new list<T>. Save the memory allocated. Append a T to the list. The delta in used memory will equal sizeof(list_node) + sizeof(T), so subtract sizeof(T) from the delta to yield sizeof(list_node). — Wug
according to gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a00577.html it's just 2 pointers and the payload. BUT if it were compiled into a library using a 64bit compiler the pointers would be 8 bytes, and 4 bytes padding to round it out to 24 would sound about right. That's my guess anyway. Should I kill the question? — Cramer
Make sure you are testing in Release mode. The extra space could be safety features that are only present in Debug mode. — john

Matthieu M. Matthieu M. · Accepted Answer · 2013-04-11T06:38:02

When having memory question about STL containers... remember that all memory they obtain come from the allocator you pass (which defaults to std::allocator).

So, just instrumenting the allocator shall answer most questions. The live demo is at liveworkspace, the output is presented here for std::list<int, MyAllocator>:

allocation of 1 elements of 24 bytes each at 0x1bfe0c0
deallocation of 1 elements of 24 bytes each at 0x1bfe0c0

So, 24 bytes in this case, which on a 64 bits platform is to be expected: two pointers for next and previous, the 4 bytes payload and 4 bytes of padding.

The full code listing is:

#include <iostream>
#include <limits>
#include <list>
#include <memory>

template <typename T>
struct MyAllocator {
   typedef T value_type;
   typedef T* pointer;
   typedef T& reference;
   typedef T const* const_pointer;
   typedef T const& const_reference;
   typedef std::size_t size_type;
   typedef std::ptrdiff_t difference_type;

   template <typename U>
   struct rebind {
      typedef MyAllocator<U> other;
   };

   MyAllocator() = default;
   MyAllocator(MyAllocator&&) = default;
   MyAllocator(MyAllocator const&) = default;
   MyAllocator& operator=(MyAllocator&&) = default;
   MyAllocator& operator=(MyAllocator const&) = default;

   template <typename U>
   MyAllocator(MyAllocator<U> const&) {}

   pointer address(reference x) const { return &x; }
   const_pointer address(const_reference x) const { return &x; }

   pointer allocate(size_type n, void const* = 0) {
      pointer p = reinterpret_cast<pointer>(malloc(n * sizeof(value_type)));
      std::cout << "allocation of " << n << " elements of " << sizeof(value_type) << " bytes each at " << (void const*)p << "\n";
      return p;
   }

   void deallocate(pointer p, size_type n) {
      std::cout << "deallocation of " <<n << " elements of " << sizeof(value_type) << " bytes each at " << (void const*)p << "\n";
      free(p);
   }

   size_type max_size() const throw() { return std::numeric_limits<size_type>::max() / sizeof(value_type); }

   template <typename U, typename... Args>
   void construct(U* p, Args&&... args) { ::new ((void*)p) U (std::forward<Args>(args)...); }

   template <typename U>
   void destroy(U* p) { p->~U(); }
};

template <typename T>
using MyList = std::list<T, MyAllocator<T>>;

int main() {
   MyList<int> l;
   l.push_back(1);
}

What is the size of each element in std::list?

1 Answers