STL basic container: is string, vector, list, deque, set, map_string[] ordered?_cy941228’s blog

class=”markdown_views prism-atom-one-dark”>

Basic containers in STL are: string, vector, list, deque, set, map

set and map are unordered storage elements, which can only be accessed through the interface it provides

set: collection, used to judge whether an element is in a group, less used
map: mapping, equivalent to a dictionary, mapping one value to another value, if you want to create a dictionary, use it’s alright

string, vector, list, deque, set are ordered containers
1.string

string is the implementation of basic_string, and it is stored continuously in memory. In order to improve efficiency, there will be reserved memory, such as string s= “abcd”, then the space used by s may be 255, when string is inserted into s again When adding content, memory will not be allocated again. It will not apply for memory again until the content is > 255, thus improving its performance.
When the content is > 255, string will first allocate a new memory, and then copy the content over , and then copy the previous content.

The operation on string, if it is added to the end, generally does not need to allocate memory, so the performance is the fastest;
If it is an operation on the middle or the beginning, such as adding elements there or deleting elements, or It is a replacement element, and memory copying is required at this time, and performance will be reduced.

If the element is deleted, the string will generally not release the memory it has allocated, in order to be more efficient for the next use.

Because string has pre-reserved memory, if it is used in large quantities, there will be memory waste, which needs to be considered. There is also the need to consider not releasing too much memory when deleting elements.

The memory in string is allocated in the heap, so the length of the string can be very large, while char[] is allocated in the stack, and the length is limited by the maximum stack length that can be used.

If you know the maximum length of the string to be used, you can use ordinary char[] instead of using string.
string is used when the length of the string is unknown or changes greatly.

If the string has undergone multiple additions and deletions, the current size is much smaller than the maximum size. If you want to reduce the size of the string, you can use:
string s = “abcdefg”;
string y( s); //Because when allocating memory again, y will only allocate memory larger than the content in s, so the waste will not be great
s.swap(y); //Reduce the memory used by s

If you have enough memory, you don’t need to consider this

capacity is a function to check the memory currently used
You can try to see the return value of capacity after assigning a string of strings, and the return value after other operations

2.vector

vector is a dynamic array. It also allocates memory in the heap, the elements are stored continuously, and there is reserved memory. If the size is reduced, the memory will not be released. If the new value > the current size, the memory will be allocated again
Yes The last element operation is the fastest (adding and deleting at the end is the fastest). At this time, there is generally no need to move the memory, only when the reserved memory is not enough.
Adding and deleting elements at the middle and the beginning requires moving memory. If it is a structure or a class, then the construction and destruction operations will be performed while moving, so the performance is not high (it is better to put the pointer of the structure or class into the vector instead of the structure or class itself, so as to avoid the error when moving construction and destruction).
In terms of access, access to any element is O(1), that is, constant, so vector is often used to store content that requires frequent random access, and does not need to frequently add or delete intermediate elements.

In comparison, you can see that the properties of vector are similar to string, and you can also use capacity to see the currently reserved memory, and use swap to reduce the memory it uses.

Summary
Please use vector for frequent random access

3.list

The list is a linked list, the elements are also stored in the heap, and each element is placed in a piece of memory
The list has no habit of space reservation, so every allocation of an element will be allocated from the memory, and every deletion of an element will Release the memory it occupies, which is different from the above, so be optimistic

The performance of adding and deleting elements in the list is very high, there is no need to move memory, and of course there is no need to construct and destroy each element, so it is often used as a random operation container.
But access to the list It is the fastest to access the elements at the beginning and the end
Accessing other elements is O(n), so if you need frequent random access, it is better to use other ones

Summary
If you like to add and delete large objects frequently, then please use list
The object to be saved is not large, and the construction and destruction operations are not complicated, then you can use vector instead of
listIt is completely the lowest performance method. In this case, it is better to use vector, because the pointer has no construction and destruction, and does not take up a lot of memory

4.deque

The double-ended queue is also stored in the heap. Its storage form is as follows:

[Stack 1]
…
[Stack 2]
…
[Stack 3]

Each heap saves several elements, and there are pointers between the heap and the heap. It looks like a combination of list and vector, but it is true.
deque allows you to quickly add in front.��, it cannot store elements directly, its mechanism of storing elements is to call another sequential container to achieve, that is, the adapter can be regarded as “it stores a container, and this container stores all elements”.

The three adapters provided in the STL can be implemented by a sequence container. By default, stack and queue are implemented based on deque container, and priority_queue is implemented based on vector container. Of course, you can also specify a specific implementation container when creating an adapter. When creating an adapter, specifying a specific sequence container on the second parameter can override the default implementation of the adapter.

Due to the characteristics of adapters, an adapter cannot be implemented by any sequential container.

The characteristic of the stack stack is last-in-first-out, so its associated basic container can be any kind of sequential container, because these container type structures can provide stack operation requirements, and they all provide push_back, pop_back and back operations ;

The characteristic of the queue queue is first-in-first-out, and the adapter requires its associated basic container to provide pop_front operation, so it cannot be established on the vector container;

The priority queue priority_queue adapter requires random access and therefore cannot be built on a list container.