Deque of STL

deque Is a two-way open data structure , The so-called double end opening , It means that it can be carried out easily from both ends push,pop operation .

1 Realization way

1.1deque The overall structure

deque Logically speaking, it is a continuous linear space , In fact, it consists of segments of quantitative continuous space ,deque Responsible for maintaining the continuity of the whole .
deque Use a continuous map Space ( No stl Of map) As the master ,map Stored in n Elements , Each element is a pointer , Points to a contiguous memory space . Here's the picture :

template <class T,class Alloc=alloc,size_t BufSiz = 0>
class deque{
    typedef T** mappointer;          //
    typedef __deque_iterator<T,T&,T*,BufSiz> iterator;
protected:
    iterator start;         // First node 
    iterator finish;        // The last node 
    map_pointer map;        // Point to map,map It's a continuous space , Each element is a pointer , Point to a contiguous data space 
    size_type map_size;     //map Number of internal pointers 
};

Be careful , The interior is also closed front and opened back [start,finish)
Operation method
The following operations can be easily realized

• begin
• end
• []

    return start[n];  // The iterator class implements [] operation 

• front
• back

    iterator tmp = finish;
    tmp--;
    return *tmp

• size

    return finish - start; // The iterator implements - operation 

• empty

---

1.2 iterator

deque To achieve logical continuity , The key is the movement of the iterator . Key points in different continuous spaces see jump .

template <class T,class Ref,class Ptr,size_t BufSiz>
struct __deque_iterator{
    T *cur;       // Current element position 
    T *first;     // The first element of the current buffer 
    T *last;      // The last location of the current buffer ( Reserve an end position to do end, There is no element )
    T ** node;    // Point to the continuous space in map The location of 
};

At the same time, the iterator implements * -> ++ – + - += -= [] == != < Wait for the operation （ Determine whether the iterator is still in the current buffer when moving , Whether to switch the buffer, etc ）

---

1.3： Insert deletion

• push_back
• push_front
• pop_front
• pop_back

Delete from the beginning and end of the queue , In defining deque when , By default, a map( Unless the number of elements is specified ).
Constructed map central , By two pointers nStart,nEnd. The default point to map The middle of a continuous space , This makes it easy to plug in front and back .

The details will not be discussed , The general idea is

Insertion time , Determine whether the current buffer has a position , If there is one, insert , No new block buffer is constructed ,push_back The new element is placed at the beginning of the new buffer ,push_front The new element is placed at the end of the new buffer .

deleted , Delete node , At the same time, judge whether the buffer needs to be emptied .

At the same time, both of these operations require central control map Add or reduce nodes , And judge the central control map Is it big enough , Not enough to replace it map.

• earse

    iterator erase(iterator it);// Delete an element in the double ended queue 

    iterator erase(iterator first,iterator last);// Delete from the double ended queue [first,last） The elements in 

• insert

    // Add an element before an element in a double ended queue x
    iterator insert(iterator it,const T& x);

    // Add before an element in a double ended queue n The same elements x
    void insert(iterator it,int n,const T& x);

    // Insert another vector of the same type before an element in a double ended queue [forst,last) Data between 
    void insert(iterator it,const_iterator first,const_iteratorlast);