In depth parsing of common containers in the C++ STL

STL is a very important template in C/C++ development, and the various containers defined in it are also very convenient for us to use. Below, we talk about some commonly used containers. We will not cover the basic operations of containers here, but will discuss the characteristics of each container. Common containers in STL include: sequential containers (vector, deque, list), associated containers (map, set), container adapters (queue, stac).

1. Sequential containers

(1) the vector
Vector is a dynamic array with continuous storage space in memory and fast random access. With continuous storage space, it is slow in terms of insert and delete operations. Vector has multiple constructors. The default constructor is to construct a memory space with an initial length of 0, and the allocated memory space grows dynamically as a multiple of 2, that is, the memory space grows according to 20,21,22,23... Growth, in the process of the push_back, if discover the allocated memory space is insufficient, the redistribution of a continuous memory space, and its size is 2 times the current continuous space, then the elements in the original space is copied to the new space, performance consumption is larger, especially when the element is the internal data (not the internal data structure and copy constructor often quite complex). Another common problem with vector is the clear operation. The clear function only clears the size of the vector to zero, but the elements in the vector are not eliminated in memory, so in the process of using the vector, it will be found that the memory consumption will be more and more, resulting in memory leak, and now the method often used is swap function to solve:

vector<int> V;
V.push_back(1); 
V.push_back(2);
V.push_back(1); 
V.push_back(2);
vector<int>().swap(V); 
//Or v. wap (vector<Int> ());

Using swap function, and temporary object exchange, make the memory of V object is temporary object memory, and the memory of temporary object memory is V object memory. After the swap, the temporary object disappears, freeing memory.

(2) a deque
Deque is similar to vector in that it supports fast random access. The biggest difference between the two is that vector can only insert data at the end, while deque supports double-end insertion. The memory spatial distribution of deque is a continuous distribution of small pieces, which are connected by a linked list and actually contain a pointer to a map. The reallocation of deque space is faster than that of vector. After reallocation, the original elements do not need to be copied.

(3) the list
List is a bidirectional linked list, so its memory space can be discontinuous and data can be accessed through Pointers, which makes the random storage of list very inefficient, so list does not provide overloading of the [] operator. But a list is good enough to support inserts and deletions anywhere, simply by moving the appropriate pointer.

(4) in the actual use, how to choose which of the three containers, should be based on your needs, generally should follow the following principles:
1) if you need efficient random access, regardless of insert and delete efficiency, use vector
2) if you need a lot of inserts and deletions and don't care about instant access, use list
3) if you need instant access and are concerned with the insertion and deletion of data at both ends, use deque

2. Associating containers

(1) the map
Map is an associative container that maps the corresponding value with a unique keyword, that is, it has key-value function. Map internally builds a red-black tree (a self-balancing binary tree), which has the function of automatic sorting of data, so all data inside the map is in order and organized in the form of binary tree.

Here is the template for the map:
The template < Class Key, class T, class Compare= less < The Key > The class Allocator = Allocator < The pair < Const Key, T > > > The class map;

From the template we can see that the map is constructed in a certain order. Map inserts and deletes more efficiently than other sequence containers because, for the associated container, there is no need to copy and move the memory, just move the pointer. Since each data in the map corresponds to a node in the red-black tree, which takes up 16 bytes when not saving your data, a parent pointer, left and right child pointer, and an enumeration value (marked red-black), one of the drawbacks of the map is that it takes up memory space.

(2) the set
Set is also a kind of associative container. Like map, it is implemented with the red and black tree at the bottom. When inserting and deleting operations, it can only move the pointer, without involving the movement and copy of memory. The elements in a set are unique and are sorted in ascending order by default. So in set, you can't change the values of the elements directly, because that would throw them out of order. To change the values of the elements, you have to delete the old elements and then insert the new ones. Any operation functions that do not provide direct access to elements can only be accessed indirectly through iterators.

Set template prototype:
The template < The class Key, class Compare = class < The Key > The Alloc = STL_DEFAULT_ALLOCATOR (Key) > The class set;

Set supports operations on sets such as intersection (set_intersection), difference (set_difference), union (set_union), and symmetry difference (set_symmetric_difference).

3. Container adapter

(1) the queue
Queue is a queue, which implements first-in, first-out function. Queue is not a standard STL container, but is based on a standard STL container. Queue is encapsulated on the basis of deque. The reason for choosing deque over vector is that deque frees up space when deleting elements and does not need to copy all elements when reapplying for space.

Its template is:
The template < TYPENAME _Sequence = "deque < The _TP "typeneam _TP, > > The class queue.

(2) stack
Stack is an implementation of the advanced and later functionality, and like queue, it also encapsulates the deque internally, which is why it's called a container adapter (just a guess). Instead of directly maintaining the template class of the controlled sequence itself, it stores the container object to do all the work for it. The source code principle and implementation of stack are the same as queue.