最終更新：2026-10-12

STL deque ソースコード解析

0.はじめに

dequeは両端が開いた区分的に連続な線形空間です（簡単には：双端キューと理解できます）。先頭と末尾の両端で要素の挿入と削除ができます。

dequeとvectorの最大の違いは次の通りです：

• dequeは定数時間で先頭に対する要素の挿入や削除ができます；

• dequeは区分的に連続な線形空間であり、いつでも新しい区間の空間を追加できます；

dequeはvectorとは異なります。vectorはメモリが足りなくなると、再割り当て／データのコピー／元の空間の解放が必要です。しかしdequeのイテレータの設計はvectorより複雑です。イテレータに普通のポインタが使えないためです。したがって、できる限りvectorを使いましょう。

1.dequeの中核コントローラ（中控器）

ユーザーから見るとdequeは連続した空間を使っているように見えますが、実際には**区分的に連続な線形空間**です。この区分された空間を管理するため、dequeコンテナにはmapが導入されています。これを中核コントローラ（中控器）と呼びます。mapは1つの連続した空間であり、その各要素はバッファへのポインタで、バッファこそがdequeのデータを格納する主体です。

上の図で、bufferはバッファと呼ばれ、map sizeと表示された連続した空間の区切りこそ中核コントローラです。

中核コントローラには、map size、bufferへのポインタ、dequeの先頭イテレータと末尾イテレータが含まれます。

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

bufferもポインタなので、_Tpはポインタへのポインタになります。

dequeは_Deque_baseを継承しており、_Deque_baseの中には_M_implがあります。

下の図と上述の説明から、中核コントローラは_Deque_implによって実現されていることがわかります。

そしてdequeは基底クラス_Deque_baseを使って、メモリ管理と中核コントローラの管理を完了させています。

2.高度なイテレータ

dequeにとって、そのイテレータの設計は非常に素晴らしいものです！

下図に示す通りです：

まず比較的重要なメンバを見てみましょう：

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

これらはいったい何でしょうか。名前から、その意味は容易にわかります。dequeは区分的に連続な空間であり、イテレータが操作を実行するとき、上述の_M_curは具体的な要素を指し、_M_firstはこのbufferの最初の要素を指し、_M_lastは最後の要素（有効な要素ではない）を指し、_M_nodeは中核コントローラを指します。したがって、これはポインタへのポインタです。

例えば、いまイテレータが++操作を実行し、現在のbufferが足りなくなったとします。このとき、中核コントローラに戻れるポインタが必要になり、次のbufferを取得して、_M_firstと_M_lastのポインタの位置をリセットし、_M_curは新しいbuffer中の指定位置を指します。

最初の図に戻りましょう：

一番上のiteratorが、上のいくつかのポインタに対応する図です。

ではbufferの計算はどのように実現されているのでしょうか？

ソースコード中の計算は、渡されてきた型に基づいています。渡された型が512バイト未満なら、buffersizeは512/sizeof(_Tp)になり、512を超えると1になります。

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

__deque_buf_sizeの実装

#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 ) );
}

前のいくつかの節のソースコードで抽出機（traits）技術に触れました。各イテレータには次の5種類のtypedefをネストする必要があります：

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

これによって、dequeのイテレータがランダムアクセスイテレータ：random_access_iterator_tagを使っていることもわかります。

vectorが使うイテレータもこれです。侯捷先生の説明によれば、連続したbufferこそvectorであり、これはイテレータのtagタイプと一致しています。

次に、この強力なイテレータのいくつかの演算子オーバーロードを見てみましょう：

具体的な説明はコードの中で行います。

間接参照演算子

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


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

もちろん上述の->は、*演算子を直接呼び出して実現することもできます。例えば：

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

++と--の演算子

// 前置++操作符
_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);
}

n距離のジャンプ演算子

/*
* 实现随机取,迭代器可以直接跳跃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);
}

次のいくつかの演算子は、いずれも上の+=演算子を呼び出して実現されています：

/*
    * 操作符+重载
    * 返回操作之后的副本
    */
_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のジャンプ

前の++や--などの演算子は、_M_set_node関数を呼び出します。この関数の役割は、buffer間のジャンプを行い、_M_node、_M_first、_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() );       /* 指向新节点的尾部 */
}

以上で、dequeのイテレータの実装詳細の説明は終わりです。

3.deque

begin()関数

_M_startを返します。

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

end()関数

_M_finishを返します。

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

size()関数

size_type
size() const

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

resize()関数

渡されてきたサイズに基づき、総sizeを超えていれば__new_size-size()の空間を再割り当てして拡張します。そうでなければsize()-__new_size以降のデータを削除します。例えば、現在20個の空間があり、resize(12)とすると、後ろの8個の空間のデータを削除し、空間を解放します。

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 ) );
}

empty()関数

2つのポインタの位置を判断するだけです。

bool
empty() const

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

back関数

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

push_front関数

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 );   // 需分配一段新的连续空间
}

push_back関数

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 );
}

上述に対応するpopの動作はこれと逆です。

insert()関数

insert関数はなかなか興味深いものです。渡されてきたイテレータの位置に基づいて、先頭と末尾にあるかどうかを確認します。先頭にあれば直接push_front関数を呼び、末尾にあれば直接push_back関数を呼びます。そうでなければ、コンテナの中に直接要素を挿入します。

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);
}

そして上述の、コンテナの中に直接要素を挿入する関数は、挿入位置を計算します。比較的前面に近ければ前面に挿入し、後ろに近ければ後ろに挿入します：

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;
}

関連トピック

• STL array ソースコード解析 | C++那些事
• STL string 深入解析 | C++那些事
• STL string 面接問題解説 | C++那些事
• STL 空基底クラス最適化 EBO | C++那些事
• STL 手書きハッシュテーブル実装 | C++那些事
• STL hashtable ハッシュテーブル | C++那些事
• STL イテレータソースコード解析 | C++那些事
• STL list ソースコード解析 | C++那些事
• STL map と multimap | C++那些事
• STL queue と stack ソースコード解析 | C++那些事

コメント