Last updated：2026-10-12

STL deque source code analysis

0.Introduction

A deque is a segmented, continuous linear space open at both ends (simply put: a double-ended queue); elements can be inserted and removed at both the front and the back.

The biggest differences between deque and vector are:

• deque allows inserting or removing elements at the front in constant time;

• deque is a segmented continuous linear space, and a new segment of space can be added at any time;

Unlike vector, which — when memory runs short — must reallocate, copy data, and free the original space, deque avoids that; however, deque's iterator design is more complex than vector's, because its iterators cannot be ordinary pointers, so prefer vector when possible.

1.The deque controller

To the user, deque appears to use continuous space, but it is in fact a segmented continuous linear space. To manage the segmented space, the deque container introduces a map, called the controller: the map is a contiguous space whose every element is a pointer to a buffer, and the buffers are what actually store the deque's data.

In the figure above, buffer denotes a buffer, and the contiguous stretch of space shown as map size is the controller.

The controller holds map size, pointers to buffers, and the deque's start and finish iterators.

_Tp     **_M_map;
size_t      _M_map_size;
iterator    _M_start;
iterator    _M_finish;

Since a buffer is itself referenced via a pointer, _Tp is a pointer to a pointer.

deque inherits from _Deque_base, and _Deque_base contains an _M_impl.

From the figure below and the description above, we can see that the controller is implemented by _Deque_impl.

And deque uses the base class _Deque_base to accomplish memory management and controller management.

2.A sophisticated iterator

For deque, its iterator design is excellent!

As shown in the figure below:

First, a look at the more important members:

typedef _Tp             **_Map_pointer;
_Tp     *_M_cur;
_Tp     *_M_first;
_Tp     *_M_last;
_Map_pointer    _M_node;

What exactly are these? Judging by their names, the meaning is easy to grasp. For deque, which is a segmented continuous space, when the iterator performs operations, _M_cur points to the concrete element, _M_first points to the first element of the current buffer, _M_last points to the last element (not a valid element), and _M_node points into the controller. Hence it is a pointer to a pointer.

For example, when the iterator performs a ++ operation and the current buffer is exhausted, a pointer is needed that can go back to the controller, fetch the next buffer, reset the positions of the _M_first and _M_last pointers, and point _M_cur to the designated position in the new buffer.

Let's return to the figure from the beginning:

The iterator at the very top is the block diagram of the pointers above.

So how is the buffer size computed?

In the source code, the computation is based on the passed-in type: if the passed type is smaller than 512 bytes, the buffersize is 512/sizeof(_Tp); if it exceeds 512, it is 1.

static size_t _S_buffer_size()
_GLIBCXX_NOEXCEPT
{
    return(__deque_buf_size( sizeof(_Tp) ) );
}

The __deque_buf_size implementation

#ifndef _GLIBCXX_DEQUE_BUF_SIZE
#define _GLIBCXX_DEQUE_BUF_SIZE 512
#endif
inline size_t
__deque_buf_size( size_t
            __size )
{
    return(__size < _GLIBCXX_DEQUE_BUF_SIZE
            ? size_t( _GLIBCXX_DEQUE_BUF_SIZE / __size ) : size_t( 1 ) );
}

The previous few sections mentioned the traits extractor technique; every iterator needs to embed the following five typedefs:

typedef std::random_access_iterator_tag iterator_category;
typedef _Tp             value_type;
typedef _Ptr                pointer;
typedef _Ref                reference;
typedef ptrdiff_t           difference_type;

From this we can also tell that deque's iterator is a random access iterator: random_access_iterator_tag.

vector's iterator is this same one; as teacher 侯捷 explains, a contiguous buffer is a vector, which coincides with the iterator's tag type.

Now let's look at some operator overloads of this powerful iterator:

The detailed explanations are given inside the code.

Dereference operators

reference
operator*() const
_GLIBCXX_NOEXCEPT
{
    return(*_M_cur);
}


pointer
operator->() const
_GLIBCXX_NOEXCEPT
{
    return(_M_cur);
}

Of course, the -> above could also be implemented by directly calling the * operator, for example:

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

The ++ and -- operators

// 前置++操作符
_Self &
operator++()
_GLIBCXX_NOEXCEPT
{
    // 先++，判断是否到了buffer的末尾，如果到了末尾，就要跳到下一个buffer。
    ++_M_cur;
    if ( _M_cur == _M_last ) // _M_last指向的不是有效元素，保留节点  
    {
        _M_set_node( _M_node + 1 );
        _M_cur = _M_first;
    }
    return(*this);
}

// 后置++操作符
_Self
operator++( int )
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;
    ++*this;
    return(__tmp);
}

// 前置--操作符
_Self &
operator--()
_GLIBCXX_NOEXCEPT
{
    // 先判断是否到了起始位置，如果到了，由于需要进行--操作，那么就应该进入前一个buffer
    if ( _M_cur == _M_first )
    {
        _M_set_node( _M_node - 1 );
        _M_cur = _M_last;
    }
    --_M_cur;
    return(*this);
} //先在容器头部插入与第一个元素相同的元素

// 后置--操作符
_Self
operator--( int )
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;    /* 定义一个副本 */
    --*this;                /* 迭代器自减操作 */
    return(__tmp);
}

The jump-n-distance operators

/*
* 实现随机取,迭代器可以直接跳跃n个距离
* 将迭代器前移n个距离,当n负值时就为下面的operator-=操作
*/
_Self &
operator+=( difference_type __n )

_GLIBCXX_NOEXCEPT
{
    const difference_type __offset = __n + (_M_cur - _M_first);
    /*
        * 若前移n个距离后，目标依然在同一个缓冲区
        * 则直接前移n个距离
        */
    if ( __offset >= 0 && __offset < difference_type( _S_buffer_size() ) )
        _M_cur += __n;
    else {
        /*
            * 若前移n个距离后,目标超出了缓冲区范围
            * __offset>0   __offset / difference_type(_S_buffer_size())计算向后移动多少个缓冲区
            * __offset<=0  -difference_type((-__offset - 1) / _S_buffer_size()) - 1计算向前移动多少个缓冲区
            */
        const difference_type __node_offset =
            __offset > 0 ? __offset / difference_type( _S_buffer_size() )
            : -difference_type( (-__offset - 1)
                        / _S_buffer_size() ) - 1;
        /* 调整到正确的缓冲区,此时_M_first已经修改了 */
        _M_set_node( _M_node + __node_offset );
        /* 修改为正确的指针位置 */
        _M_cur = _M_first + (__offset - __node_offset
                        * difference_type( _S_buffer_size() ) );
    }
    return(*this);
}

The operators below are all implemented by calling the += operator above:

/*
    * 操作符+重载
    * 返回操作之后的副本
    */
_Self
operator+( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;
    /* 调用operator+=操作 */
    return(__tmp += __n);
}


/* 利用operator+=操作实现 */
_Self &
operator-=( difference_type __n )
_GLIBCXX_NOEXCEPT
{
    return(*this += -__n);
}


/*
    * 操作符-重载
    * 返回操作之后的副本
    */
_Self
operator-( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    _Self __tmp = *this;    /*  保存副本 */
    return(__tmp -= __n);   /* 调用operator-=操作符 */
}


/* 返回指定位置的元素，即实现随机存取 */
reference
operator[]( difference_type __n ) const
_GLIBCXX_NOEXCEPT
{
    return(*(*this + __n) );    /* 该函数调用operator+,operator* */
}

Buffer jumping

The ++ and -- operators above call the _M_set_node function, whose role is to jump between buffers, updating the pointers _M_node, _M_first, and _M_last.

/**
    *  Prepares to traverse new_node.  Sets everything except
    *  _M_cur, which should therefore be set by the caller
    *  immediately afterwards, based on _M_first and _M_last.
    */
void
_M_set_node( _Map_pointer __new_node )
_GLIBCXX_NOEXCEPT
{
    _M_node     = __new_node;                                           /* 指向新的节点 */
    _M_first    = *__new_node;                                          /* 指向新节点的头部 */
    _M_last     = _M_first + difference_type( _S_buffer_size() );       /* 指向新节点的尾部 */
}

With that, we have finished explaining the implementation details of deque's iterator.

3.deque

The begin() function

Returns _M_start.

iterator
begin()
_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_start);
}

The end() function

Returns _M_finish.

iterator
end()
_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish);
}

The size() function

size_type
size() const

_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish - this->_M_impl._M_start);
}

The resize() function

Based on the passed-in size: if it exceeds the total size, reallocate and expand by __new_size-size() of space; otherwise delete size()-__new_size of data. For example, with 20 slots now, resize(12) removes the data in the last 8 slots and frees that space.

void
resize( size_type __new_size )
{
    const size_type __len = size();
    if ( __new_size > __len )
        _M_default_append( __new_size - __len );
    else if ( __new_size < __len )
        _M_erase_at_end( this->_M_impl._M_start
                    + difference_type( __new_size ) );
}

The empty() function

Just compare the two pointer positions.

bool
empty() const

_GLIBCXX_NOEXCEPT
{
    return(this->_M_impl._M_finish == this->_M_impl._M_start);
}

The back function

reference
back()
_GLIBCXX_NOEXCEPT       // 指向finish的前一个位置
{
    iterator __tmp = end();
    --__tmp;
    return(*__tmp);
}

The push_front function

void
push_front( const value_type &__x )
{
    //若当前缓冲区存在可用空间
    if ( this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first )
    {
        this->_M_impl.construct( this->_M_impl._M_start._M_cur - 1, __x );// 直接构造对象
        --this->_M_impl._M_start._M_cur;    // 调整指针所指位置
    } else
        _M_push_front_aux( __x );   // 需分配一段新的连续空间
}

The push_back function

void
push_back( const value_type &__x )
{
    //若当前缓冲区存在可用空间
    if ( this->_M_impl._M_finish._M_cur
            != this->_M_impl._M_finish._M_last - 1 )
    {
        this->_M_impl.construct( this->_M_impl._M_finish._M_cur, __x ); // 直接构造对象
        ++this->_M_impl._M_finish._M_cur;       //调整指针所指位置
    } else     // 若当前缓冲区不存在可用空间
    // 需分配一段新的连续空间
        _M_push_back_aux( __x );
}

The corresponding pop operations are the reverse of the above.

The insert() function

The insert function is rather interesting: based on the passed iterator position, it checks whether it is at the beginning or the end — at the beginning it directly calls push_front, at the end it directly calls push_back, otherwise it inserts the element directly into the container.

template <typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
insert(iterator __position, const value_type& __x)
{
        if (__position._M_cur == this->_M_impl._M_start._M_cur)   
    {
        push_front(__x);
        return this->_M_impl._M_start;
    }
        else if (__position._M_cur == this->_M_impl._M_finish._M_cur)
    {
        push_back(__x);
        iterator __tmp = this->_M_impl._M_finish;
        --__tmp;
        return __tmp;
    }
        else  //否则在容器直接插入数据
        return _M_insert_aux(__position._M_const_cast(), __x);
}

And the function above that inserts the element directly into the container computes the insertion point: if it is relatively close to the front, insertion happens at the front; if close to the back, at the back:

template<typename _Tp, typename _Alloc>
typename deque<_Tp, _Alloc>::iterator
deque<_Tp, _Alloc>::
_M_insert_aux(iterator __pos, const value_type& __x)
{
    value_type __x_copy = __x; // XXX copy
    difference_type __index = __pos - this->_M_impl._M_start;  //计算插入点之前元素个数
    if (static_cast<size_type>(__index) < size() / 2)   //若插入点之前的元素较少
        {
        push_front(_GLIBCXX_MOVE(front())); //先在容器头部插入与第一个元素相同的元素
        iterator __front1 = this->_M_impl._M_start;
        ++__front1;
        iterator __front2 = __front1;
        ++__front2;
        __pos = this->_M_impl._M_start + __index;
        iterator __pos1 = __pos;
        ++__pos1;
        _GLIBCXX_MOVE3(__front2, __pos1, __front1); // 元素搬移
        }
    else
    {
        push_back(_GLIBCXX_MOVE(back()));
        iterator __back1 = this->_M_impl._M_finish;
        --__back1;
        iterator __back2 = __back1;
        --__back2;
        __pos = this->_M_impl._M_start + __index;
        _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
    }
    *__pos = _GLIBCXX_MOVE(__x_copy);       // 在安插点上设定新值
    return __pos;
}

Related Topics

• STL array source code analysis | C++那些事
• STL string deep dive | C++那些事
• STL string interview questions in depth | C++那些事
• STL empty base optimization EBO | C++那些事
• STL hand-written hash table implementation | C++那些事
• STL hashtable hash table | C++那些事
• STL iterator source code analysis | C++那些事
• STL list source code analysis | C++那些事
• STL map and multimap | C++那些事
• STL queue and stack source code analysis | C++那些事

Comments