Последнее обновление：2026-10-12

Анализ исходников STL deque

0. Введение

deque — это сегментированное непрерывное линейное пространство, открытое с обеих сторон (проще говоря: двусторонняя очередь), позволяющее вставлять и удалять элементы на обоих концах.

Наибольшее различие между deque и vector:

• deque позволяет вставлять и удалять элементы на переднем конце за константное время;

• deque — сегментированное непрерывное линейное пространство, к которому в любой момент можно добавить новый сегмент;

В отличие от vector, которому при нехватке памяти требуется перевыделить память, скопировать данные и освободить исходное пространство, deque устроен иначе; зато итератор deque устроен сложнее, чем у vector, поскольку итератор не может быть обычным указателем — поэтому по возможности используйте vector.

1. Диспетчер deque

Со стороны пользователя deque выглядит как непрерывное пространство, но на деле это сегментированное непрерывное линейное пространство. Для управления сегментированным пространством контейнер deque вводит map, называемый диспетчером (центром управления): map — это непрерывный блок пространства, каждый элемент которого — указатель на буфер, и именно буферы являются основной памятью, где 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 ) );
}

В исходниках предыдущих разделов упоминалась техника экстрактора: каждый итератор должен содержать следующие пять 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()

Достаточно сравнить позиции двух указателей.

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++那些事
• Оптимизация пустого базового класса EBO в STL | C++那些事
• Реализация хеш-таблицы своими руками | C++那些事
• Хеш-таблица STL hashtable | C++那些事
• Анализ исходников STL итераторов | C++那些事
• Анализ исходников STL list | C++那些事
• STL map и multimap | C++那些事
• Анализ исходников STL queue и stack | C++那些事

Комментарии