Understanding of STL container

This article is only for stl The bottom implementation, advantages and disadvantages of the container are briefly analyzed , It will not explain the interface functions inside the container in detail . I just want to know the advantages and disadvantages of various containers , When you need to use containers, choose a more appropriate container to use .

1.array：

Store specific types of data in a linear arrangement . In fact, it is similar to an ordinary array , It also supports random access and is efficient 、 Fixed storage size , But there are some more similar iterator access 、 Get advanced functions such as containers .

characteristic ：

1. The length of the container is fixed , You cannot add or delete elements , Only the value of the element can be changed .

2. Continuous storage space , You can randomly access the values of elements .

3. Value has no sort , Arrange only according to the order in which the containers are inserted .

2.vector:

and array The container is a bit similar , But it can be expanded , Therefore, it supports adding and deleting elements .

characteristic ：

1. Support adding and deleting elements , When vector When you run out of memory space , Capacity expansion will be carried out .

2. Inserting and deleting elements at the tail is very efficient , It is inefficient to insert and delete elements in non tail . Such as ： When inserting elements , You need to move all the elements after the inserted element one bit back , Then insert the element .（ Delete the same principle ）

3. Continuous storage space , You can randomly access the values of elements .

4. Value has no sort , Arrange only according to the order in which the containers are inserted .

3.deque

and vector The container is similar to , But inserting elements at the beginning and end is very fast .

1. Support adding and deleting elements .

2. Inserting elements at the beginning and end is very efficient , The efficiency of inserting elements in other parts is very low .

3. Not continuous storage space .

4. Values are out of order .

PS： If there is no need to insert a large number of header elements , Suggest or use vector The container is quite good .

4.list

In the form of a two-way linked list , It is very convenient to insert and delete elements in the middle , But to access the middle elements, you can only access them sequentially from the head or tail .

characteristic ：

1. Inserting and deleting elements is extremely efficient .

2. Access the value of the element , It can only be accessed one by one through the chain head and chain tail .

3. Not continuous storage space .

4. Values are out of order .

5.set

Belongs to the associated container , Fast search of value through red black tree , And the efficiency of adding and deleting values is also very high .

1. Search efficiency is very high , Although not comparable vector The efficiency of this random access to element values , But find the value of the binary tree ,log2 The search efficiency is also very, very high , The number of stored elements per high 1 times , The number of searches only increases 1 Time .

2. Adding and deleting values is also very efficient , He doesn't look like vector This continuous memory container is like this （ Add an element , The elements behind it have to move back ）, It's more like list This form of linked list , The leaf node points to the parent node through a pointer , To modify the hierarchy, just change the pointer , Of course , You also need to rotate the red and black tree in a certain way , Finally, the insertion of nodes can be completed and their order can be maintained .

3. Not continuous storage space .

4. Values are ordered and unique .

6.map

Belongs to the associated container , and set equally , The implementation principle is also to use red black tree , but map It uses <key, value> This key value pair , Inside the red and black tree through key To sort .

1. Directly through key To get value It's still very efficient （ Be similar to set Principle ）, But if not key, Want to find the corresponding value, You can only traverse map 了 .

2. The efficiency of adding and deleting values is also very high （ Be similar to set Principle ）

3. Non contiguous storage space .

4.key Orderly and unique .

5.value Disordered and not unique .