Última actualización：2026-10-12

Análisis del código fuente de STL deque¶

0. Introducción¶

deque es un espacio lineal continuo por segmentos, abierto por ambos extremos (en términos simples: una cola de doble extremo), que permite insertar y eliminar elementos por el frente y por el final.

La mayor diferencia entre deque y vector es:

deque permite insertar o eliminar elementos por el frente en tiempo constante;
deque es un espacio lineal continuo por segmentos y puede añadir un nuevo segmento de espacio en cualquier momento;

A diferencia de vector —que, cuando la memoria es insuficiente, debe reasignar, copiar los datos y liberar el espacio original—, deque no necesita hacerlo; eso sí, el diseño de su iterador es más complejo que el de vector, ya que el iterador no puede usar un puntero ordinario, por lo que conviene usar vector siempre que sea posible.

1. El controlador central de deque¶

Para el usuario parece que deque usa un espacio continuo, pero en realidad es un espacio lineal continuo por segmentos. Para gestionar los segmentos, el contenedor deque introduce un map, llamado controlador central: map es un bloque de espacio continuo cuyos elementos son punteros a buffers, y los buffers son el cuerpo principal donde deque almacena los datos.

En la figura anterior, cada buffer se denomina buffer, y el tramo continuo etiquetado como map size es el controlador central.

El controlador central contiene el map size, los punteros a los buffers, y los iteradores de inicio y de fin de deque.

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

Como los buffers también son punteros, _Tp es un puntero a puntero.

deque hereda de _Deque_base, y dentro de _Deque_base hay un _M_impl.

Según la figura anterior y la descripción de arriba, se deduce que el controlador central está implementado por _Deque_impl.

Y deque usa la clase base _Deque_base para gestionar la memoria y el controlador central.

2. Un iterador de alto nivel¶

Para deque, ¡el diseño de su iterador es excelente!

Como muestra la siguiente figura:

Veamos primero los miembros más importantes:

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

¿Qué son exactamente? Por sus nombres es fácil deducirlo: para deque, que es un espacio continuo por segmentos, cuando el iterador ejecuta una operación, _M_cur apunta al elemento concreto, _M_first apunta al primer elemento del buffer actual, _M_last apunta al último elemento (no es un elemento válido) y _M_node apunta al controlador central. Por eso es un puntero a puntero.

Por ejemplo, si el iterador ejecuta ahora la operación ++ y el buffer actual se queda sin espacio, se necesita un puntero que pueda volver al controlador central, tomar el siguiente buffer, restablecer las posiciones de _M_first y _M_last, y hacer que _M_cur apunte a la posición indicada del nuevo segmento de buffer.

Volviendo a la figura del principio:

El iterator de la parte superior es la ilustración del bloque de los punteros anteriores.

¿Y cómo se implementa el cálculo del buffer?

En el código fuente, el cálculo se basa en el tipo que se pasa: si el tipo pasado ocupa menos de 512 bytes, el buffersize es 512/sizeof(_Tp); si supera 512, es 1.

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

Implementación 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 ) );
}

En las secciones anteriores del código fuente se mencionó la técnica de extracción (traits); cada iterador debe incorporar los siguientes cinco typedef:

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

Con esto también se sabe que el iterador de deque es un iterador de acceso aleatorio: random_access_iterator_tag.

El iterador de vector también es de este tipo; según explica el profesor Hou Jie, un buffer continuo es un vector, lo cual coincide plenamente con el tipo de tag del iterador.

Veamos ahora algunas sobrecargas de operadores de este potente iterador:

La explicación concreta está en el código.

Operador de desreferencia

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


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

Por supuesto, el operador -> anterior también puede implementarse invocando directamente el operador *; por ejemplo:

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

Operadores ++ y --

// 前置++操作符
_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 n posiciones

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

Los siguientes operadores se implementan todos invocando el operador += anterior:

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

Los operadores anteriores como ++ y -- invocan la función _M_set_node, cuya función es permitir el salto entre buffers, modificando a qué apuntan _M_node, _M_first y _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() );       /* 指向新节点的尾部 */
}

Con esto terminamos la explicación de los detalles de implementación del iterador de deque.

3.deque¶

Función begin()

Devuelve _M_start.

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

Función end()

Devuelve _M_finish.

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

Función size()

size_type
size() const

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

Función resize()

Según el tamaño que se pase: si supera el size total, se reasigna y se amplía con __new_size-size() de espacio; en caso contrario, se eliminan los datos a partir de size()-__new_size. Por ejemplo, si ahora hay 20 espacios y se hace resize(12), se eliminarán los datos de los 8 espacios finales y se liberará ese espacio.

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

Función empty()

Basta con comparar las posiciones de los dos punteros.

bool
empty() const

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

Función back

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

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

Función 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 );
}

Las operaciones pop correspondientes a las anteriores funcionan al revés.

Función insert()

La función insert es interesante: según la posición del iterador que se le pase, se comprueba si está al principio o al final; si está al principio, llama directamente a push_front; si está al final, llama directamente a push_back; en caso contrario, inserta el elemento directamente en el contenedor.

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

Y la función anterior, que inserta el elemento directamente en el contenedor, calcula el punto de inserción: si está más cerca del frente, inserta por delante; si está más cerca del final, inserta por detrás:

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álisis del código fuente de STL deque¶

0. Introducción¶

1. El controlador central de deque¶

2. Un iterador de alto nivel¶

3.deque¶

Temas relacionados¶

Comentarios