CODEWITHSUNDEEP
c++memorystlcontainers
dance dance
dance dance

Reputation: 93

Memory Allocation in STL C++

I am a little confused about memory reallocation in STL C++. For example, I know if I declare a vector, and keep pushing back elements into it, the vector will at some point need a reallocation of memory space and copy all the existing elements into it. For linked lists no reallocation is needed, because the elements are not stored consecutively in the stack and each element uses a pointer to point to the next element.

My question is, what's the situation for other STL in C++ ? for example, string, map,unordered_map? Do they need reallocation ?

Upvotes: 6

Views: 4823

Answers (2)

Rushikesh
Rushikesh

Reputation: 173

Almost all STL containers memory is allocated on heap, even for a vector. A plain array and std::array template are the only once probably that have memory on stack.

If your questions is about continuous memory allocation (whether on stack or heap), then, probably, plain array, std::array, std::vector have got continuous memory. Almost all other containers such as list, deque, map, set etc. do not have memory allocated continuously.

Upvotes: 1

Matteo Italia
Matteo Italia

Reputation: 126957

(disclaimer: all the concrete data structures specified here may not be required by the standard, but they are useful to remember to help link the rules to something concrete)

std::string ~= std::vector; it's a dynamic array, if you keep pushing elements at its end, at some time it will reallocate your elements.

std::list: each element is a new linked list node, so no reallocation ever takes place, wherever you may insert the new element.

std::deque: it's typically made of several pages of elements; when a page is full, a new one is allocated and added to the list of pages; for this reason, no reallocation of your elements ever takes place, and your elements never get moved if you keep pushing stuff at the beginning or at the end.

std::map/std::multimap/std::set/std::multiset: typically a binary tree, each element is allocated on its own; no reallocations are ever performed.

std::unordered_map/std::unordered_multimap/std::unordered_set/std::unordered_multiset: a hash table; when the table is full enough, rehashing and reallocation occurs.

Upvotes: 12

Related Questions