CODEWITHSUNDEEP
c++stl
Cramer
Cramer

Reputation: 1795

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

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)

Upvotes: 5

Views: 2481

Answers (1)

Matthieu M.
Matthieu M.

Reputation: 299760

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);
}

Upvotes: 8

Related Questions