C++, can you tell me something about the functions of vectors and maps?

(1)vector has automatic expansion operation, and each expansion is accompanied by the operation of "configuring new space/moving old data/releasing old space", so it has a certain time cost. ?

(2)vector provides reserved interfaces. If you can get a general idea of the number of elements, you can allocate appropriate space from the beginning. ?

(3) The storage space of vectors is continuous. For the operation of inserting elements, inserting at the end of the vector is an appropriate choice. Maintain a continuous linear space, so vector supports random access. ?

(4) When the vector of (4) dynamically increases its size, it will not reserve a new space after the original space (there is no guarantee that there is still configuration space after the original space), but allocate a larger space twice the original size, then copy the original content, and then start to construct new elements after the original content, and release the original space. Therefore, once any operation on the vector results in spatial reconfiguration, all iterators pointing to the original vector will fail.

2, the difference between vector and array

A vector is very similar to an array. The only difference between the two is the flexibility of space use. Array is a static space and cannot be changed once it is configured. Vector is a dynamic space. With the increase of elements, its internal mechanism will expand the space to accommodate new elements. Therefore, the use of vectors is of great help to the rational use and flexibility of memory.

The data structure adopted is simple: linear continuous space. In order to reduce the speed cost of space configuration, the actual configuration size of vector may be larger than the client's demand for possible expansion in the future, which is the concept of capacity. When adding a new element, if the capacity is insufficient, expand it to 2 times (if the original size is 0, configure it as 1), and if the capacity of 2 times is still insufficient, expand it to a large enough capacity.

2. List function

(1) Compared with the continuous linear space of vectors, lists are much more complicated. ?

(2) Its advantage is that every time an element is inserted or deleted, an element space will be allocated or released. Therefore, the list is absolutely accurate in the use of space, and it is not wasted at all. ?

(3) For element insertion or element removal at any position, list is always a constant time. ?

(4)list is not only a bidirectional linked list, but also a cyclic bidirectional linked list. It only needs one pointer to represent the whole linked list completely. ?

(5) Neither insert operation nor join operation will cause the original list iterator to fail, which is not true in vector. Because the insertion of vector may lead to memory reconfiguration, which will cause all original iterators to fail. Even for the element deletion operation of the list, only the iterator pointing to the deleted element is invalid, and other iterators erase not affected. ?

(6)list can no longer use ordinary pointers as iterators like vector, because its nodes cannot guarantee continuity in the storage space. List provides a two-way iterator.

slist

The difference between slist and list:

(1)STL list is a two-way linked list, while slist is a one-way linked list. ?

(2) The iterator of STLList is a bidirectional iterator, while the iterator of slist is a unidirectional forward iterator. ?

(3) One-way linked list takes up less space and some operations are faster. ?

(4) They have a common feature: operations such as insert, erase and splice will not lead to the failure of crude oil iterator. After the removal operation, the iterator pointing to the removed element is bound to fail. ?

(5) Because the single linked list can only iterate forward, it does not provide many operations. Even if it does, it is a very inefficient operation, and it needs to be traversed from the starting node.

It is unwise to use insert or erase operation function in other places except the area near the beginning of slist, which is a big disadvantage of slist compared with list. ?

(6)slist iterator is a one-way forward iterator, so besides the basic operation of iterator, only operator++ operation is realized.

deque

Differences between 1, deque and vector

(1)vector is a continuous linear space that is opened in one direction, and users can only insert and delete it at the end of the vector (insertion at pos is also allowed, but because the underlying implementation of the vector is an array, too many non-queue end positions will have performance consumption). Deque is a continuous linear space with two-way openings, which allows insertion and deletion at both ends of the head and tail.

(2)deque allows you to insert or delete elements in the header in a constant time.

(3) Dirk has no concept of capacity. It is composed of piecewise continuous spatial dynamics, and new spaces can be added and connected at any time. There is no need to provide the so-called space reservation function.

(4)deque's biggest task is to maintain the illusion of overall continuity in the quantitative continuous space of these fragments, and provide random access interfaces. It avoids the cycle of "reconfiguration, copying and publishing" at the expense of complex iterator architecture.

(5) As a piecewise continuous linear space, there must be central control, and in order to maintain the illusion of overall continuity, the design of data structure and the operation of iterator forward and backward are quite complicated. Deque has more code components than vector or list. Therefore, we should choose vector instead of deque as much as possible.

2. Dirk's central controller

Deque uses a so-called map (note that it is not a map container of STL) as the master. The so-called map here is a small continuous space, in which each element (called a node here) is a pointer to another (larger) continuous linear space, called a buffer. Buffer is deque's main storage space. SGI STL allows us to specify the size of the buffer. The default value of 0 means that a buffer of 5 12 bytes will be used.

Summary:

(1)map is a block continuous space in which each element is a pointer to a buffer. ?

(2) It is further found that map is actually a T**, that is to say, it is a pointer, and what it refers to is also a pointer, pointing to a space of T type.

3. Dirk's Iterator

Dirk is a piecewise continuous space. The task of maintaining the illusion of "overall continuity" falls on two operators of iterator: operator++ and operator-.

What structure should deque's iterator have:?

(1) It must be able to indicate the position of piecewise continuous space (i.e. buffer).

(2) It must be able to judge whether it is on the edge of its buffer. If it is, once it moves forward or backward, it must jump to the next or previous buffer. In order to jump correctly, Dirk must always master the control center (map).

Therefore, it is necessary to define in the iterator: the pointer of the current element, the start pointer of the buffer where the current element is located, the tail pointer of the buffer where the current element is located, and the pointer to the address of the buffer in the map.

Deque is not as efficient as vector, so sometimes when sorting Deque, you need to move elements into vector first, then sort them, and then move them back.

4.deque's construction and memory management

Because deque's design idea is connected through cache blocks, its memory management will be more complicated. When inserting, we should consider whether to jump into the cache, whether to create a new map node (like vector, it is actually to redistribute a space to the map and delete the original space), and whether the inserted element moves forward or backward (who moves less). When deleting an element, consider whether to move the previous element backward to cover the position where the element needs to be deleted, or move the last element forward to cover it (no matter who moves it small). After moving, the redundant elements should be destructed and the redundant buffer should be released.

Step 4 stack

Stack is a first-in and last-out data structure with only one exit. Allows you to add elements, delete elements and get the topmost elements. Traversal behavior is not allowed.

Source code of SGI STL

The stack does not provide access functions or iterators.

Step 5 queue up

Queue is a first-in first-out data structure. There are two exits that allow you to add, delete, add from the bottom and get the top elements. Traversal behavior is not allowed.

Deque is a two-way queue, while queue is a one-way queue.

Deque is a two-way open data structure. If deque is used as the bottom structure, and its bottom outlet and front inlet are closed, a queue can be easily formed. Therefore, SGI STL defaults to deque as the underlying structure of the queue.

Queues do not provide traversal functions or iterators.

Maps and multi-maps

Features of the map:?

(1) All elements are automatically sorted according to key values. ?

(2)2) All elements of the map are paired, the first value is the key value and the second is the real value. ?

(3)map does not allow two elements to have the same key value. ?

(4) You can change the real value of elements through the iterator of map, but you can't change the key value, which will violate the arrangement rules of elements. ?

(5) After the client inserts or deletes the mapping, the previous iterator is still valid. Of course, iterators that delete elements are an exception. ?

Its underlying mechanism is r B- tree. Almost all operations are just the operation behavior of calling RB-tree.

Multimap and map are almost the same, the only difference is that Multimap allows duplicate key values. Therefore, the mapping uses the insert_unique () of the underlying RB tree to implement the insertion, while the multi-mapping insertion uses the insert_equal () of the RB tree instead of the insert_unique ().

HashTable

1 and hash table overview

Hashtable can access and delete any famous item. The purpose of this structure is to provide basic operations with constant time, which does not depend on the randomness of inserted elements, but is based on statistical data.

Hash function: responsible for mapping elements to "indexes with acceptable size". In short, it is to map large numbers into decimals.

Problems caused by using hash function: There may be different elements mapped to the same location (same index). This is the problem of collision or conflict. Methods to solve conflict problems: linear detection, secondary detection, separation of links, etc. The hash method used in stl hash table is open chain method.

(1) Linear detection: When the hash function calculates the insertion position of an element, the location space is no longer available. What should I do? The easiest way is to look down one by one in order until you find an available space.

Two assumptions are needed: a. The table is large enough. B. Each element can be independent.

Linear detection will cause the problem of primary clustering: the growth rate of average insertion cost is much higher than that of load factor.

(2) Secondary detection: mainly used to solve the main group problem. The equation to solve the collision is f (I) = I 2. If the hash function calculates that the location of the new element is H, and the location has actually been used, then try H+ 1 2, H+2 2, H+3 2, H+4 2, ..., H+I 2 in turn, unlike the linear detection attempt of H+ 1.

Secondary detection can eliminate the main clustering, but it may lead to secondary clustering: if the positions of the two elements calculated by the hash function are the same, the positions detected during insertion are also the same, resulting in some waste. Methods of eliminating subgroups, such as double hashing.

(3) Open chain: This practice is to maintain a list in each table element. The hash function assigns us a list, and then we perform operations such as inserting, searching and deleting elements on the list. If the list is short enough, the speed is still fast enough.

Using the open chain method, the loading factor of the table will be greater than 1. SGI STL hash table adopts open chain method.

For more information about c++, please visit my blog: Web Link.