[STL source code analysis] container (to be supplemented)

Containers

The first 4 Chapter Sequential containers

According to the arrangement characteristics of the data in the container , Containers can be divided into sequential containers and associative containers ：

• Sequential containers ： All the elements in it can be ordered , But not necessarily orderly , Data is stored in a sequence
• Associative containers ： data key-value Key value pairs are stored
  

list And slist The difference between ？

• list： Double linked list ,list It's a bidirectional iterator
• slist： One way linked list ,slist Is one-way Forward Iterator

set、map、multiset、multimap The difference between ？
​ - set： duplicate removal 、 Orderly 、 Data is unique , The bottom is RBTree（ because RBTree So it's orderly ）

• map： No repetition 、 Orderly 、 The bottom is RBTree
• multiset： Allow repetition 、 Orderly 、 The bottom is RBTree
• multimap： It can be inserted repeatedly 、 Orderly 、 The bottom is RBTree

hashtable、hash_set、hash_map、hash_multiset、hash_multimap The difference between ？

• hashtable： Hashtable
• hash_set： Characteristics and set Exactly the same , The only difference is that its underlying mechanism is hashtable, So it's out of order
• hash_map： Characteristics and map Exactly the same , The only difference is that its underlying mechanism is hashtable, So it's out of order
• hash_multiset： Characteristics and multiset Exactly the same , The only difference is that its underlying mechanism is hashtable, So it's out of order
• hash_multimap： Characteristics and multimap Exactly the same , The only difference is that its underlying mechanism is hashtable, So it's out of order

4.2.1 vector summary

array And vector The difference between

• array： Static array
• vector： Variable length array ,vector The core of is the automatic capacity expansion mechanism , The process of capacity expansion consists of three steps —— Configure new space 、 Data mobility 、 Free up the old space .

4.2.2 vector Definition summary

4.2.3 vector The iterator

vector The iterator of needs to meet operator++、operator–、operator*、operator->、operator+、operator+=、operator-= Wait for the operation , And support random access , therefore vector What is offered is Random Access Iterators.

4.2.4 vector Data structure of

It mainly maintains the following three iterators ：

1. start： Represents the head of the space currently in use
2. finish： Represents the end of the currently used space , Be careful ,finish Pointing to The next position of the last element
3. end_of_storage： Represents the end of the currently available space

When the capacity is insufficient ,vector Will be expanded to the current Twice as big , If it's not enough , Expand to a large enough capacity .

4.2.5 vector Structure and memory management of ：constructor,push_back

Expand and insert insert_aux() Source code ：

STL standard ： After insertion , The sentinel iterator should point to where it is inserted .

4.2.6 vector Element operation of ：pop_back,erase,clear,insert

Delete operation summary （ Copy - Move - Release ）：

1. The node after the interval will be deleted Copy Come to the front ;
2. Move finish The iterator points to the end of the current data
3. destory Release Space

Delete source code ：

Insert source code ：

among , __STL_TRY Is a macro , And the following catch form try-catch block To catch exceptions .

The insertion operation is mainly to clarify 1. The number of elements after the insertion point is less than or equal to the number of new elements and 2. The number of elements after the insertion point is greater than the number of new elements These two special cases , Its core idea is to put position The space after that is free , So move the original element to achieve this goal .

The number of elements after the insertion point is greater than the number of new elements ：

1. First of all, will finish Move forward n Elements to finish after （ Change at the same time finish The direction of , This step is decided The number of elements after the insertion point must be greater than the number of new elements , Otherwise, go beyond the left position 了 ）
2. take position To the original finish-n The elements between them are in turn from the original finish Insert... Forward （ The aim is to free up position After n A place ）
3. stay position Then insert this n Elements to complete the operation

The number of elements after the insertion point is less than or equal to the number of new elements ：

1. First, in the finish Insert after " The number of new elements minus the number of elements after the insertion point " Elements （ Move at the same time finish, This step is decided The number of elements after the insertion point must be less than the number of new elements , Otherwise, the negative value will be subtracted ）
2. And then move position To the original finish Position all elements of this interval To current finish after
3. Then fill the vacated section with all the elements to be inserted to complete the insertion operation

4.3.1 list summary

list（ Double linked list ） advantage ： Insert 、 Delete 、 Element movement is O(1) Of

4.3.2 list The node of

list The nodes of are bidirectional , therefore list Containers It's actually a two-way linked list

template<class T>
struct __list_node {
    
	typedef void* void_pointer;
	void_pointer prev; //  Pointer to the precursor node 
	void_pointer next; //  Pointer to the next node 
	T data; //  Store the data 
}

4.3.3 list The iterator

Think about it ：list Energy and harmony vector Using a normal pointer as an iterator ？

Actually, it's not possible , therefore list Not necessarily a continuous space , So be right ++ And so on , because list It's a two-way list , So the iterator must be able to traverse in both directions , So the type of iterator is Bidirectional Iterator, An iterator that can move in both directions .

list Iterator design for ：

among , Focus on overloading operator-> Writing ：

pointer operator->() const {
     return &(operator*()); }

important ！

-> The overloading of this symbol is special , Its overloaded functions cannot be written casually , It should keep its basic meaning ： Make member visits , actually , The implementation of member access is based on native pointers -> Operator . therefore , If point Is a custom class （ Not native pointers ）, that point-> After being overloaded operator->() function , If at this time operator->() It returns a pointer , Then call... On the returned pointer ->, That is, by default, dereference before accessing members member The function of , And use it as point->member The final return result of ; If operator->() The return is still not a pointer, but another custom -> Classes of symbols , Then continue the above process , Until you finally get a pointer , Use the default for this pointer -> function .
So here , First, call the overloaded operator->() function , It returns &(operator*()) This is the pointer to the node object （operator*(), This expression is for the operator Display call ）, Then continue to call on the pointer to the node object -> Operator , So the iterator can get the members of the object .

4.3.4 list Data structure of

list It's not just a two-way list , It is also a ring mounted two-way linked list . Because it is ring mounted , Define pointer node Is the next node of the last node of the element null After node ,node Of next The first node is the first node .

STL One of the norms ： Before closed after opening [start, end) , namely end Points to the next node of the last node of the element null node .

4.3.5 list Structure and memory management of ：constructor,push_back,insert

In the container , Need to be in template Pass in the space configurator when defining .list The custom space configurator only needs to configure the size of one node at a time .

list Of push_back() The bottom layer is still called insert()：

void push_back(const T& x){
     insert(end(),x); }

The bottom layer of the container is implemented , Each insert will request a piece of memory , Then assign the value to be inserted to this memory ：

4.3.6 list Element operation of ：push_front,push_back,erase,pop_front,pop_back,clear,remove,unique,splice,merge,reverse,sort

push_front The underlying implementation and push_back almost , It's all by insert Realized .