Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c++

stl

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)

like image 804
Cramer Avatar asked Apr 11 '13 04:04

Cramer


People also ask

How do I find the size of a list in C++?

CPP. size() function is used to return the size of the list container or the number of elements in the list container. Syntax : listname.

What is std size?

A: It means standard, one size fits all. You can adjust the back a bit if too small.

What does .size do in C++?

size() function is used to return the size of the set container or the number of elements in the set container. Return Value: It returns the number of elements in the set container.

What is std::list in C++?

(since C++17) std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported. It is usually implemented as a doubly-linked list.


1 Answers

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);
}
like image 51
Matthieu M. Avatar answered Oct 18 '22 05:10

Matthieu M.