Última atualização：2026-10-12

Análise do código-fonte do STL deque¶

0. Introdução¶

deque é um espaço linear contínuo por segmentos, aberto nas duas direções (entenda simplesmente como: uma fila de duas pontas), permitindo inserir e remover elementos nas duas pontas.

A maior diferença entre deque e vector é:

deque permite inserir ou remover elementos na ponta frontal em tempo constante;
deque é um espaço linear contínuo por segmentos, e um novo segmento de espaço pode ser acrescentado a qualquer momento;

Diferentemente do vector — que, quando a memória é insuficiente, precisa realocar/copiar dados/liberar o espaço original —, o deque tem um desenho de iterador mais complexo que o do vector, pois o iterador não pode usar um ponteiro comum; por isso, dê preferência ao vector.

1. O controlador central do deque¶

Aos olhos do usuário, o deque usa um espaço contínuo, mas na verdade é um espaço linear contínuo por segmentos. Para gerenciar os segmentos, o contêiner deque introduziu o map, chamado de controlador central: o map é um espaço contínuo em que cada elemento é um ponteiro para um buffer, e os buffers são o corpo principal do armazenamento de dados do deque.

Na figura acima, buffer é o nome do buffer, e o trecho contínuo mostrado como map size é o controlador central.

O controlador central contém o map size, ponteiros para os buffers, além do iterador de início e do iterador de fim do deque.

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

Como o buffer também é um ponteiro, _Tp é um ponteiro para ponteiro.

O deque herda de _Deque_base, e dentro de _Deque_base há um _M_impl.

De acordo com a figura abaixo e a descrição acima, pode-se saber que o controlador central é implementado por _Deque_impl.

E o deque usa a classe base _Deque_base para realizar o gerenciamento de memória e o gerenciamento do controlador central.

2. Um iterador sofisticado¶

Para o deque, o desenho do seu iterador é excelente!

Conforme a figura abaixo:

Primeiro, vejamos os membros mais importantes:

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

O que afinal são esses? Pelos nomes, é fácil saber o significado. Para o deque, que é um espaço contínuo por segmentos, quando o iterador executa operações: o _M_cur acima aponta para um elemento concreto, o _M_first aponta para o primeiro elemento deste buffer, o _M_last aponta para o último elemento (que não é um elemento válido), e o _M_node aponta para o controlador central. Por isso, é um ponteiro para ponteiro.

Por exemplo, quando o iterador executa ++ e o buffer atual já não basta, é preciso um ponteiro capaz de voltar ao controlador central, pegar o próximo buffer, reiniciar as posições dos ponteiros _M_first e _M_last, e fazer _M_cur apontar para a posição indicada no novo buffer.

Volvamos agora à figura do início:

O iterator no topo é a ilustração do bloco desses ponteiros acima.

E como é implementado o cálculo do buffer?

No código-fonte, o cálculo se baseia no tipo passado: se o tipo passado ocupa menos de 512 bytes, o buffersize é 512/sizeof(_Tp); se ultrapassar 512, é 1.

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

implementação de __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 ) );
}

Nas seções anteriores do código-fonte mencionamos a técnica do extrator; cada iterador precisa embutir os cinco typedef abaixo:

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

Com isso, também se pode saber que o iterador do deque é um iterador de acesso aleatório: random_access_iterator_tag.

O vector também usa esse tipo de iterador; segundo o professor 侯捷, buffers contínuos são como um vector, o que coincide exatamente com o tipo de tag do iterador.

Vejamos agora algumas sobrecargas de operadores deste iterador poderoso:

A explicação concreta está no código.

Operadores de desreferência

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


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

Claro, o -> acima também pode ser implementado chamando diretamente o operador *, por exemplo:

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

Operadores ++ e --

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

Operador de salto de uma distância 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);
}

Os operadores a seguir são todos implementados chamando o operador += acima:

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

Salto de buffer

Os operadores anteriores, como ++ e --, chamam a função _M_set_node, cujo papel é permitir o salto entre buffers, alterando os apontamentos de _M_node, _M_first e _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() );       /* 指向新节点的尾部 */
}

Com isso, concluímos a explicação dos detalhes de implementação do iterador do deque.

3. deque¶

Função begin()

Retorna _M_start.

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

Função end()

Retorna _M_finish.

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

Função size()

size_type
size() const

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

Função resize()

De acordo com o tamanho passado: se exceder o size total, realoca e expande com __new_size-size() de espaço; caso contrário, remove os dados a partir de size()-__new_size. Por exemplo, se agora há 20 espaços, resize(12) apagará os dados dos 8 espaços finais e liberará esses espaços.

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

Função empty()

Basta comparar as posições dos dois ponteiros.

bool
empty() const

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

Função back

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

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

Função 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 );
}

As ações de pop correspondentes às anteriores são o inverso destas.

Função insert()

A função insert é bastante interessante: conforme a posição do iterador passado, verifica-se se está no início ou no fim; se estiver no início, chama diretamente push_front; se estiver no fim, chama diretamente push_back; caso contrário, insere o elemento diretamente no contêiner.

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

E a função acima, que insere o elemento diretamente no contêiner, calcula o ponto de inserção: se estiver mais para o início, insere por cima; se estiver mais para o fim, insere por baixo:

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

Análise do código-fonte do STL deque¶

0. Introdução¶

1. O controlador central do deque¶

2. Um iterador sofisticado¶

3. deque¶

Tópicos relacionados¶

Comentários