[STL source code analysis] summary notes (7): ingenious deque

00 Write it at the front

【STL Source analysis 】 Summary notes （6）：iterator Design and magic traits

After mastering the basic design principles of iterators , Let's take a look at the implementation of the remaining sequential containers . At this time, we can focus more on the design of each container itself .

01 summary

deque It's a continuous linear space with two-way openings , That is, you can insert and delete at both ends . We know vector It's a continuous linear space with one-way openings , When the space is insufficient, you need to find a larger space and transplant it .

Why do you say deque Ingenious , because deque There is no concept of capacity , Can dynamically increase space .

But this continuity is just deque Create a kind of “ illusion ”, So let's see deque How to achieve continuity .

Not yet iterator, Just look at the middle part .

You can find map Where there are many pointers , And each pointer points to a piece buffer.

When adding elements , Only need buffer Add to . If you reach the boundary , Then expand map The pointer maintained in . That's why deque The reason why it can be expanded .

But it also means trying to maintain continuity “ illusion ”,iterator Will make a huge change （ heavy load ） To achieve, for example ++,– The operation of .

We will explain one by one later .

02 deque Structure

From the above figure, we have a brief understanding of deque Structure .

there map In fact, that is deque Control center （ Pay attention to this map No STL Medium map）.map It is a small continuous space （ The bottom is actually vector）, Each of them node Point to a large continuous space buffer, stay STL Its size can be specified in .

Look at the implementation directly ：

template <class T,class Alloc=alloc,size_t BufSize=0>
class deque{
    public:
    	typedef T value_type;
    	typedef _deque_iterator<T,T&,T*,BufSiz>iterator;
    protected:
    	typedef pointer* map_pointer;
    protected:
    	iterator start;
    	iterator finish;
    	map_pointer map;//1
    	size_type map_size;//2
}

Look at this code from the above figure

1. First of all, pay attention to map,map Is a pointer to the space of the control center , And this includes pointers , therefore map The type of is a pointer to a pointer .（T**）

2. map_size Namely map Size , For example, the picture above shows 8.

3. We can think about it deque How many bytes is the size of .

   map Is a pointer structure ：4 byte .map_size 4 byte . Also need to know iterator Size .

   And in the iterator There are four parts shown in the figure above ：cur,first,last,node. Is the total 16 byte .

   therefore deque Its size is 16+16+4+4=40 byte
   
   

03 deque The iterator

Then we can study it carefully deque The iterator of , This is also deque Soul . because deque The partition of the internal buffer , If you want to make it continuous ,iterator It must be possible to accurately find the previous or next buffer The location of , It is necessary to make some special judgment .

iterator Structure

Because the lines in the above figure are intricate , So here we put iterator Take it out and explain .

template <class T,class Ref,class Ptr,size_t BufSiz>
struct _deque_iterator{
    typedef random_access_iterator_tag iterator_category;//1
    typedef T value_type;//2
    typedef Ptr pointer;//3
    typedef Ref reference;//4
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;//5
    typedef T** map_pointer;
    typedef _deque_iterator self;
    
    T* cur;
    T* first;
    T* last;
   	map_pointer node;
    ...
};

First of all, I was in iterator We mentioned in iterator Must be able to answer five questions .

The main concern here is iterator The pointers defined at the bottom .

1. iterator One of the most basic functions is to point to the current element ,cur That's what it does .
2. first Point to the header of the buffer segment （ Including spare space ）
3. last Point to the next position at the end of the buffer segment （ Including spare space ） Note that both of these pointers refer to the segment buffer .
4. node Point to the control center , Used to distinguish which is currently in the control center node Control this buffer （ The pointer to the pointer ）

Go back to the top and have a look start and finish, here start It refers to the above pointer of the first buffer ,finish Refers to the above pointer of the last buffer .

therefore begin() and end() It's settled. .

iterator begin(){return start;}
iterator end(){return finish;}

insert() Realization

Take up a insert() Example , Take a look at iterator How is the buffer Jumping between .

insert(position,x) Allows you to insert an element at a certain point . about deque Come on , It is necessary to judge where this point is closer to the left and right ends , This moves fewer elements .

iterator insert(iterator position,const value_type& x){
    if(position.cur==start.cur){// First, judge whether it is at the head end , If yes, give it to push_front() To deal with it 
        push_front(x);
        return start;
    }
    else if(position.cur==finish.cur){// Then judge whether it is at the end , If yes, give it to push_back() To deal with it 
        push_back(x);
        iterator tmp=finish;
        --tmp;
        return tmp;
    }
    else{
        return insert_aux(position,x);
    }
}

Let's see inert_aux() What did you do .

template <class T,class Alloc,size_t BufSize>
typename deque<T,Alloc,BufSize>::iterator
deque<T,Alloc,BufSize>::insert_aux(iterator pos,const value_type& x){
    difference_type index=pos-start;
    value_type x_copy=x;
    
    if(index<size()/2){
        push_front(front());// Add an element with the same value as the first element to the front .
        iterator front1=start; 
        ++front1;
        iterator front2=front1;
        ++front2;
        pos=start+index;
        iterator pos1=pos;
        ++pos1;
        copy(front2,pos1,front1);// Move elements 
    }
    else{
        push_back(back());// Add an element with the same value as the last element at the last end .
        iterator back1=finish;
        --back1;
        iterator back2=back1;
        --back2;
        pos=start+index;
        copy_backward(pos,back2,back1);// Move elements 
    }
    *pos=x_copy;
    return pos;
    
}

insert_aux() First of all, I figured out which side this insertion point is close to .

If it's close to the left , Then push the element on the left .（ We don't need to look at the specific implementation of the mobile operation first , Copy a header element in the header , Then the following use copy Move ）

If it's close to the right , Then push the element on the right to insert .

Clever overloading

Back in size() when ,deque This is how it works ：

size_type size() const {
    return finish-start;
}

It looks very consistent with the continuous space , In fact, these are overloads operator- Later results .

Let's see deque In order to achieve a continuous look , How operators are overloaded .

++/– operation

stay deque In this structure , The most important thing to consider is whether it is in the same buffer .

++ The operation is divided into two parts ++ And post ++, The difference between them can be found in list Found in that article .

In front of ++

The general implementation process is to implement the pre implementation first ++, Then use the overloaded prefix ++ To implement post ++

self& operator++(){
    ++cur;// Move to the next element 
    if(cur==last){// If you reach the end 
        set_node(node+1);// Change to the next buffer 
        cur=first;
    }
    return *this;
}

Note that this is the first step + Compare later . because last The position of is the next position of the last element .

After ++

After ++ It depends on the front ++ To achieve .

self operator++(int){
    self tmp=*this;// Record original value 
    ++*this;// Add 
    return tmp;// Return the original value 
}

– operation

– The operation is the same .

self& operator--(){// In front of --
    if(cur==first){
        set_node(node-1);
        cur=last;
    }
    --cur;
    return *this;
}

self operator--(int){// After --
    self tmp=*this;
    -- *this;
    return tmp;
}

+=/-= operation

deque It supports random access , For example, let the iterator jump several positions directly . The focus of consideration is still the problem of regional jump

+=

self& operator+=(differenc_type n){
    difference_type offset=n+(cur-first);
    if(offset>=0 && offset<difference_type(buffer_size()))
        cur+=n;
    else{
        difference_type node_offset=offset>0?offset/difference_type(buffer_size()):-difference_type((-offset-1)/buffer_size())-1;
        set_node(node+node_offset);
        cur=first+(offset-node_offset*difference(buffer_size()));
    }
    return *this;  
        
}

First calculate the jumping distance , If not more than one buffer The length of , Then directly cur Move .

If more than one buffer The length of , I'm going to jump to the number from now on buffer, Adjust at the same time cur Point to .

Because the buffer size is fixed , So you can find the number of buffers by division .

-=

-= The operation is through += To complete .

self& operator-=(difference_type n){
    return *this+=-n;
}

+=-n This operation is also very clever .

+ and -

+ and - The operations of are respectively through += and -= Realized .

self operator+(difference_type n) const {//+
    self tmp=*this;
    return tmp+=n;
}

self operator-(difference_type n) const {//-
    self tmp=*this;
    return tmp-=n;
}

04 deque Structure and memory management of

Last but not least deque Memory structure , This part is quite long in the book , Let's simplify the key points of implementation .

deque Two dedicated space configurators are defined , Used to configure element size and map size

typedef simple_alloc<value_type,Alloc>data_allocator;// Configure element size 
typedef simple_alloc<pointer,Alloc>map_allocator;// Configure pointer size 

constructor as follows ：

deque(int n,const value_type& value):statr(),finish(),map(0),map_size(0){
    fill_initialize(n,value);
}

fill_initialize Responsible for generating and arranging deque Structure .

fill_initialize Internal create_map_and_node() Responsible for arrangement deque Structure

void deque<T,Alloc,BufSize>::create_map_and_nodes(size_type num_elements){
     Number of nodes required =（ Element number / The elements that each buffer can hold ）+1;
     To configure map;
     take map Stay in the middle , The expandability of both ends of the head and tail is the same ;
        
}

Let's first look at when a buffer is full , Need to configure a new buffer

This part is implemented in the operation function , such as push_back()

void push_back(const value_type& t){
     If the buffer has two or more spare spaces , Continue construction ;
     There's only one spare space left , call push_back_aux();
}

void deque< T, Alloc,BufSize>::push_back_aux(const value_type& t){
     Call if it meets the condition reserve_map_at_back();
     Configure new buffer ;
}

There is also a case of map It needs to be expanded map

At this time, it involves the above mentioned reserve_map_at_back(), And the corresponding reserve_map_at_front(), stay push_front() in .
If map In the store map The position of the pointer is not enough , Will reallocate space .

In fact, the implementation depends on reallocate_map()

front and back The difference is that map Keep in the middle position ,front than back Make more space in front of you .

And expanding map It is also used to allocate more space , Copy and release , Namely vector Construction process of .

05 stack and queue

Stack and queue are the key contents when we learn data structure , The FIFO and FIFO structures can facilitate the operation of many data .

stay STL In the implementation of ,stack and queue In fact, it is done through the bottom container , So it is not called a container , It's called “ Container adapter ”（container adapter).

Adapter yes STL One of the six major components .

We need to pay attention to

stack and queue It specifies the way of data access , Therefore, traversal is not provided , It means that... Is not provided iterator.

So the two can only manipulate elements through their exits .

stack

stack It's a first in and last out structure , With deque As an underlying implementation, the head end opening needs to be closed .

template <class T,class Sequence = deque<T>>
class stack{
    protected:
    	Sequence c;
    public:
    	bool empty() const{return c.empty()};
    	...
}

It can be seen that all operations are calls deque Of .

According to our container knowledge , It can also be understood that stack You can also use list as well as vector As the bottom layer .

queue

queue It's a first in first out structure , That is, the top is added , Take out the bottom end .

In the same way, through deque Realized .

template <class T,class Sequence = deque<T>>
class queue{
    protected:
    	Sequence c;
    public:
    	bool empty() const{return c.empty();}
    	reference front(){return c.front();}
    	void push(const value_type& x){c.push_back();}
    	void pop(){c.pop_front();}
    	...
}

According to our container knowledge , It can also be understood that stack You can also use list As the bottom layer , But it can't be used. vector, because vector Cannot manipulate header elements .

06 summary

deque This structure is commonly used by us stack and queue The bottom of the , Need to master its ingenious design method .

deque The control center of is the core of the whole , And in each map Switching between is also the key point .