III Implementation principle of vector

Review tips ： For the convenience of reading , I didn't add the source code , If you want to know more , You can see Mr. Houjie's STL Source analysis . This is a summary for the students who have read this book , Just recite it directly .

One .vector Implementation principle of

1.vector Base class introduction

• vector Is a template class , Its base class does nothing vector<int> v; Such a statement , It just calls the parameterless construction of the base class , It did nothing . There is no dynamic allocation of memory .

• If vector Specify container size at construction time , Then dynamic memory will be applied when declaring , But if the construct is the default construct , It doesn't apply for dynamic memory .

• The role of base classes ：

1. Save container start position 、 The end location and the next location of the requested memory space ;
2. Apply for dynamic memory space .

2.vector What happens when you insert elements from the back

• 2.1 In the air vector Insert an element

1. Assign an element as 1 Space , Insert this element , If the back exceeds the space requested by the container , Reallocate a new memory space （ Its size is the size of the original space 2 times ）.

2. Copy all the elements of the original memory to the new memory in the same order , And insert the element to be inserted into the next position of the last element .

3. Call the destructor in the original memory , Destroy original memory .

• 2.2 vector Insert when current memory runs out

  ditto

3.vector What happens when you insert an element in the middle

• In fact, it is to move the element behind the current position of the element to be inserted backward , Then insert the element to be inserted into the corresponding position .

4.vector Delete element memory will be released

• 4.1 Remove from the end of the container

1. The last deletion from the container is to call pop_back(), Move the iterator forward one bit , Then destroy the last element .

• 4.2 Remove... From the middle of the container

1. What removes the call from the middle of the container is erase（ The function is to delete the element in the current position , Move the following elements of the deleted element forward one bit in turn , And returns the iterator pointing to the current position ）. So deleting an element from the middle will not release the dynamic memory that has been requested

5.vector How to modify the element value of a certain position

• vector You can modify the value of the current element by means of iterators and subscripts .

6.vector The time complexity of reading and inserting elements

• vector Read an element , You can take at, as well as [] To access elements directly , So the time complexity of reading elements is O(1), Inserting and deleting elements requires moving elements , The time complexity is O(n). The time complexity of inserting and deleting elements at the end is O(1).

7.vector Basic algorithm

• because vector have operator *,operator ++,operator --,operator +=,operator -=,operator -,operator +,opeator->, therefore vector Our iterators are random access iterators .

  pop_back(), push_back() Deletion at the end , Tail insertion

  erase Delete... In the specified location

  clear Delete all

  insert Insert... At specified location

  [] , at[] visit , Modifying elements

8.vector Summary of the underlying implementation

• vector It's a dynamic array , Used to maintain a continuous dynamic control , There are three member functions inside , Used to store the starting position , Used position , And the last position , Whenever dynamic memory runs out , It will follow the original memory 2 times , Reapply for new memory . Copy the data from the original memory to the new memory , Free the original memory .

Two .vector Precautions for

1. Use... In uncertain situations at instead of operator[]

• at Will check if it's out of bounds , Suppose you are not sure whether the current access action will cross the boundary

2. What type can't be used as vector The template type of

• about vector Template specialization types , Because in vector During the implementation of , Variables are often copied or assigned values , therefore vector The template type of should have a public copy constructor and overloaded assignment operator functions .

3. vector The reason why the iterator of will fail

1. The space pointed to by the corresponding pointer at the bottom of the iterator is destroyed , And use a space that has been released , The consequence is that the program crashes ( That is, if you continue to use an iterator that has expired , The program could crash ).

2. An operation that causes a change in its underlying space , It is possible that the iterator fails , such as ：resize、reserve、insert、assign、 push_back etc.

3. stay vector Delete elements in the middle of the container according to the specified iterator , That is to call erase function , At this time, because the current position will be covered by the following elements , So the specified iterator will fail , But at this point you can go through erase Gets the correct iterator for the current position ;

4. stay vector When you need to re apply for memory , Such as capacity , For example, in the process of releasing unused memory and so on, the problem of iterator failure will occur , Because the memory has changed , At this point, you need to regain the iterator ;

4. vector How to release memory quickly

1. Some people say it can be called reserve(0) To release , After all reserve Function will reapply the memory according to the size we specified , That won't work , This function will only act when the size of the input memory is larger than the original memory , Otherwise, no action will be taken .

2. As for passing resize perhaps clear It doesn't work , These functions only destruct all elements that are currently stored in the container , But the memory space of the container itself will not be released .

• 4.1 adopt swap function

• Now we can think about , Under what circumstances vector The size is 0 Well , As an empty container , So to release memory quickly , We can refer to swap Function mechanism , Use an empty vector With the current vector swapping , Use form like vector<int>().swap(v) This code , take v This vector The memory space represented by the variable is the same as an empty vector swapping , such v The memory space of is equal to be released , And this empty vector Because it's a temporary variable , It's at the end of this line of code , Automatically called vector The destructor of frees up dynamic memory space , such , One vector The dynamic memory is quickly released .

• 4.2 Use shrink_to_fit function

• Its function is to free up unused memory , Suppose we call clear Function cleans out all the elements , Is the whole container unused , Then call shrink_to_fit Function to free up unused memory , Let's take this one vector Is the memory free .

​