Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How does std::list allocate nodes vs. elements

How does std::list allocate the nodes in which it keeps the next/prev pointers and the T element it contains?

I think that standard allocators can only be used to allocate memory for one type (because std::allocator::allocate allocates memory in increments of sizeof(T)). So it seems impossible to allocate the list node and the contained object in a single allocation, which means that the nodes have to be allocated with whatever the implementation decides, and the nodes store pointers to the objects instead of the objects themselves, and this implies two levels of indirection to get from a pointer to a list node to the object it contains, which seems inefficient. Is this the case?

like image 273
asdf Avatar asked Jul 26 '14 19:07

asdf


People also ask

Does STD list allocate on heap?

Yes, it does use new indirectly via its Allocator parameter. You can write a custom allocator that uses your heap, and instantiate list s with it.

Is std:: list contiguous?

All the data in a vector is contiguous where the std::list allocates separately memory for each element.

What are the member functions associated with std :: allocator ()?

Member functions associated with std::allocator() : address: It is used for obtaining the address of an object although it is removed in C++20. construct: It is used to construct an object.It is also removed in C++20. destroy: It is used to destruct an object in allocated storage.It is also removed in C++20.


1 Answers

The allocator has a member template class, rebind, which is responsible for allocating other types. The page for std::allocator here actually has an example of the exact thing you are asking. I will quote it here:

until C++11

std::list<T, A> allocates nodes of some internal type Node<T>, using the allocator A::rebind<Node<T>>::other

since C++11

std::list<T, A> allocates nodes of some internal type Node<T>, using the allocator std::allocator_traits<A>::rebind_alloc<Node<T>>, which is implemented in terms of A::rebind<Node<T>>::other if A is an std::allocator

like image 62
Benjamin Lindley Avatar answered Oct 19 '22 07:10

Benjamin Lindley