[analysis of STL source code] summary notes (3): vector introduction

00 Write it at the front

vector We are learning c++ It is also one of the most commonly used containers in the process , from vector It is easier to understand STL Organizational structure of . Here we focus on vector The internal structure of , and vector The interface operation provided is not our focus , Use method can refer to cppreference.

01 summary

array We use it a lot , But it is a static space , Unable to dynamically allocate memory . The size was fixed from the beginning .

vector and array Very similar , The difference lies in vector It's dynamic space , Its internal mechanism will expand its space to accommodate new elements . It doesn't need to be like array Apply for large memory before using large space . And we can see vector When expanding “ Save against a rainy day ” The ability of .

02 vector Data structure of

The basic structure

Let's take a look at a picture

vector Its structure is shown in the figure above . Because it is a linear continuous space , So it's simpler .

vector There are three iterators inside ,start,finish and end of storage.

start and finish Points to the beginning and end of the occupied space （ Notice that this end is next to the last element , Left closed right away ）

end of storage Point to the tail of the whole continuous space .

The code is as follows ：

template <class T,class Alloc=alloc>
class vector {
    
    ...
    protected:
    	iterator start;
    	iterator finish;
    	iterator end_of_storage;
    ...
}

The distributor used here alloc We'll go into more details later . iterator iterator For the time being, the pointer .

therefore vector The size of . A pointer 4 Bytes （32 position ）, therefore vector The size in this version is 12 Bytes .

Derived structure

Because these three iterators exist ,vector Other functions provided, such as calculating data size size, Container capacity capacity Various methods can be easily implemented .

Let's look at the code first , Explain one by one ：

template <class T,class Alloc=alloc>
class vector {
    
    ...
    public:
    	iterator begin(){
    return start};//1
    	iterator end(){
    return finish};//1
    	size_type size() const {
    return size_type(end()-begin());}//2
    	size_type capacity() const{
    //3
            return size(end_of_storage-begin());
        }
    	bool empty() const {
    return begin()==end();}//4
    	reference operator[](size_type n){
    return *(begin()+n);}//5
    	reference front(){
    return *begin();}//6
    	reference back(){
    return *(end()-1);}//6
}

1. begin() and end() The implementation of is very direct , Go back to what we said above start and finish iterator （ The pointer ）.
2. The size of the data size() Is the result of subtracting the head from the tail . Use here finish-start faster , But use begin()-end() Convenient maintenance .
3. Capacity of container capacity() The implementation of is to return the result of subtracting the beginning from the iterator pointing to the end of the whole space .
4. The empty case is that the head and tail are equal .
5. heavy load [ ], That is to say, we often take vector Subscript elements in , The result of dereference is returned （ Subscript from 0 Start ）.
6. The implementation that returns the first element and the last element is to use begin() and end() Dereference results . Be careful end() Points to the next position of the last element .

03 vector Memory management for

principle

Let's see another picture

vector Memory is twice as large , When I put the data, I found that the space was full ,vector Will find a new space twice the size , Then copy the original value , And then release the original space .

Source code analysis

We from push_back() The operation of inserting a new element can be seen vector Methods of memory management

void push_back(const T& x)
{
    
    if(finish != end_of_storage)
    {
    
        construct(finish,x);
        ++finish;// Mobile iterator 
    }
    else
    {
    
        insert_aux(end(),x);
    }
}

push_back() Add data when it is not full , Then reposition the iterator .

If it's full, call insert_aux()

Look again. insert_aux()

template <class T,class Alloc>
    void vector<T,Alloc>::insert_aux(iterator position,const T& x){
    
        if(finish != end_of_storage){
    //1
            ...
            ++finish;
            ...
        }
        else{
    
            const size_type old_size=size();//2
            const size_type len=old_size!=0?2*old_size:1;//3
            
            iterator new_start =data_alloctor:allocate(len);//4
            iterator new_finish=new_start;
            
            try{
    
                new_finish=uninitialized_copy(start,position,new_start);//5
                construct(new_finish,x);//6
                ++new_finish;//6
                
                new_finish=uninitialized_copy(position,finish,new_finish);//7
            }
            catch(...){
    
                ...
            }
            
            destroy(begin(),end());//8
            dellocate();
            
            start=new_start;//9
            finish=new_finish;
            end_of_storage=new_start+len;
        }
    }

This code is a little longer , Let's explain in detail .

1. stay insert_aux Another internal judgment was made , Determine whether the data is full .
2. If it's already full , Then record the original size old_size
3. This is the key . If the original size is 0, Just expand it to 1; Not for 0 Just expand it to 2 Multiple size .
4. This is where space is really allocated . When you get double space , Set up new start, Then let the new finish Equal to it .
5. Start copying the original vector The value in .
6. There are also elements to be added that have not been put in . Then construct a new element , Readjustment new_finish The location of .
7. In fact, the operation of putting elements here can be completed . however insert_aux() May also be called by other functions , such as insert(), At this time, there will be a concept of placement position . You also need to copy the content behind the insertion point .
8. Release the original vector Space
9. Adjust the position of the new iterator

Something to pay special attention to

1. Dynamic space augmentation is not simply an increase in size , Instead, copy in the new space .
2. After the space is configured, all points to the original vector Your iterators will fail .

04 vector The iterator

Although we haven't explored the structure of iterators , But because of vector Maintain a continuous linear space , So some operations are needed, such as *,->,++,–,+=,-=, Ordinary pointers can meet the requirements of .

therefore vector The iterator of is actually a normal pointer , That is to say random access iterators.

template <class T,class Alloc=alloc>
    class vector{
    
        public:
        	typedef T value_type;
        	typedef value_type * iterator;// Normal pointer 
        ...
    };

05 vector Add and delete

pop_back()

The implementation of deleting the tail element is relatively simple , Move the end mark forward directly , Re destroy elements .

void pop_back(){
    
    --finish;
    destory(finish);
}

erase

erase There are two uses , Let's talk about clearing first To last Between the elements .（ Note that [first,last) Left closed right away ）

Look at the picture first :

The basic idea is to put last The following contents are copied to first The location of , Adjust the new finish Location .

iterator erase(iterator first,iterator last){
    
    iterator i= copy(last,finish,first);// Copy last To finish Location data to first
    destroy(i,finish);
    finish=finish-(last-first);// Adjust new finish
    return first;
}

1. About destroy(), I'll talk more about it in the iterator section . Here is to accept first and last Two iterators , Destructs objects within the scope of two iterators .
2. About copy(), Will appear in the algorithm section , It is the copy we mentioned above , But it returns an iterator :result+(last-first), That is, return the next location of the copied data , That's why destroy From i To finish, Translation is from the new finish To the original finish.

insert

insert The usage of is insert(position,n,x), From position Start , Insert n Elements , The initial value is x.

There are several situations in the implementation process ：

The first is when there is enough spare space ：

if(size_type(end_of_storage-finish)>=n)
{
    
    T x_copy=x;
    const size_type elems_after=finish-position;// Calculate the existing element after the insertion point 
    iterator old_finish=finish;
    ...
}

1. Existing elements after the insertion point > Number of new elements
   For example, insert 2 individual , And now position There are three in the back

if(elem_after>n){
        
	uninitialized_copy(finish-n,finish,finish);    
	finish +=n;    
	copy_backward(position,old_finish-n,old_finish);    
	fill(position,position+n,x_copy);}

In the picture , The second step calls uninitialized_copy(), The third step calls copy_backward().

Of course, everyone will be very curious about why these two steps need to open the copy , But not at one go .

For the time being, it means uninitialized_copy() Is to copy data to an uninitialized area , For example, moving two bits requires two spare spaces , So the range to be moved is [finish-2,finish)

In addition, you cannot call... Alone copy_backward(), There will be cases where the constructor is destructed without being called （uninitialized_copy() Call constructor ）

2. Existing elements after the insertion point <= Number of new elements
   For example, insert 3 individual , And now position There are two in the back
   

else{
        
	uninitialized_fill_n(finish,n-elems_after,x_copy);    
	finish+=n-elems_after;    
	uninitialized_copy(position,old_finish,finish);    
	finish+=elem_after;    
	fill(position,old_finish,x_copy);}

First from finish Start adding n-elems_after Elements , Update again finish.

And then copy the original element to the new one finish Back .

Finally, fill up the vacancy .

It's easy to understand , No matter how many elements are added （ Of course, the prerequisites must be met ）, such as 10 individual 20 individual , Then the position of the element after the insertion position will be occupied , So first fill the rest , Then replace the place with elements .

In case of insufficient space, it will also double

else{
        
	const size_type old_size=size();//1 
	const size_type len = old_size+max(old_size,n);//2 
	iterator new_start=data_alloctor:allocte(len);//3 
	iterator new_finish=new_start;//3 _STL_TRY{//4 
	new_finish=uninitialized_copy(start,position,new_start);//5 
	new_finish=uninitialized_fill_n(new_finish,n,x);//6 
	new_finish=uninitialized_copy(position,finish,new_finish);//7 } 

1. Record the original size
2. Expand space , It could be twice the old length , If the number of inserted elements is greater than the original size, So the new length is old_size+n
3. Apply for new space , Set up the new start and finish
4. Because this space is not initialized , So they all use uninitialized_, Note that this operation has been for new_finish assignment , to update new_finish
5. First, copy the data before the insertion position . from start To position copy to new_start
6. And then from the insertion point （ That is to say new_finish） Start filling in n individual x
7. Original vector Copy the data after the insertion point in （position To finish）

06 summary

vector The internal implementation is mostly consistent with what we expected , There are also a few very flexible implementations . Just make sure it has three important iterators , Understand the principle of its memory allocation and the realization of its main functions .

Generally speaking, no matter it is study STL Use or analyze its internal structure ,vector Are very suitable to start .