Memory Allocation in STL C ++

Question

I am a bit confused about the reallocation of memory in STL C ++. For example, I know if I declare a vector and continue to insert elements back into it, the vector at some point should redistribute the memory space and copy all existing elements into it. For linked lists, redistribution is not required because the items are not stored sequentially on the stack, and each item uses a pointer to point to the next item.

My question is: what is the situation for other STLs in C ++? e.g. string , map , unordered_map ? Is redistribution necessary?

Answer 1

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

std::string ~ = std::vector ; it is a dynamic array, if you continue to click elements at its end, after some time it will redistribute your elements.

std::list : each element is a new linked node list, so redistribution never happens wherever you insert a new element.

std::deque : it usually consists of several pages of elements; when the page is full, a new one is added and added to the list of pages; for this reason, redistribution of your elements never happens, and your elements never move if you keep clicking on the material at the beginning or at the end.

std::map / std::multimap / std::set / std::multiset : this is usually a binary tree, each element is allocated on its own; redistributions are never performed.

std::unordered_map / std::unordered_multimap / std::unordered_set / std::unordered_multiset : hash table; when the table is filled enough, renaming and redistribution occurs.

Answer 2

Almost all STL container memory is allocated on the heap, even for a vector. The simple array and the std :: array pattern are the only ones possibly having memory on the stack.

If your questions are about continuous memory allocation (whether on the stack or on the heap), then maybe the regular std :: array, std :: vector array got continuous memory. In almost all other containers, such as list, deque, map, set, etc., memory is not allocated continuously.