Última actualización：2026-10-12

Análisis del código fuente de STL queue y stack

0.Introducción

¿Por qué stack y queue no se consideran contenedores?

En esta sección, partiendo de esa pregunta, profundizamos en el análisis del código fuente.

1.stack

En el código fuente de stack nos fijamos en dos cosas: - El _Sequence por defecto es deque - La implementación de sus funciones internas llama a las funciones del contenedor correspondiente de _Sequence.

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack
{

public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:
    //  See queue::c for notes on this name.
    _Sequence c;

public:
     reference
      top()
      {
        __glibcxx_requires_nonempty();
        return c.back();
      }
    void
      push(const value_type& __x)
      { c.push_back(__x); }
}

Probar el contenedor subyacente de stack

Para stack, el contenedor subyacente puede ser vector, deque, list, pero no map ni set. Como el compilador no hace una comprobación exhaustiva, cuando se llama a una función inexistente la compilación no pasa; así, aunque algo como set no puede ser contenedor subyacente, si dispusiera de ciertas funciones la llamada seguiría saliendo bien, hasta llegar a una función que no exista.

int test_stack() {
    cout<<"============test_stack============="<<endl;
    clock_t timeStart = clock();
    stack<int, list<int>> c;
    for (long i = 0; i < 100000; i++)
        c.push(i+1);
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.top()= " << c.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
    timeStart=clock();
    stack<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++)
        c1.push(i+1);
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;

    // vector可以作为stack的底层容器
    stack<int, vector<int>> c2;
    for (long i = 0; i < 100000; i++)
        c2.push(i+1);
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    c2.pop();
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}

2.queue

En el código fuente de queue nos fijamos en dos cosas: - El _Sequence por defecto es deque - La implementación de sus funciones internas llama a las funciones del contenedor correspondiente de _Sequence.

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:

    _Sequence c;

public:

    void push(const value_type& __x)
    { c.push_back(__x); }

    void pop()
    { 
        __glibcxx_requires_nonempty();
      c.pop_front();
    }
}

Su diagrama de clases UML correspondiente es el siguiente:

Por la misma razón, la cola de prioridad usa vector como contenedor por defecto.

template<typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare  = less<typename _Sequence::value_type> >
class priority_queue
{
public:
    typedef typename _Sequence::value_type                value_type;
    typedef typename _Sequence::reference                 reference;
    typedef typename _Sequence::const_reference           const_reference;
    typedef typename _Sequence::size_type                 size_type;
    typedef          _Sequence                            container_type;

protected:
    //  See queue::c for notes on these names.
    _Sequence  c;
    _Compare   comp;

public:
    reference
    top() 
    {
        __glibcxx_requires_nonempty();
        return c.front();
    }

    void
    push(const value_type& __x)
    {
        c.push_back(__x);
        std::push_heap(c.begin(), c.end(), comp);
    }

}

Probemos los contenedores subyacentes que admiten estos dos adaptadores de contenedor:

queue

Para queue el contenedor subyacente puede ser deque y también list, pero no vector, map, set; ¡usando el deque por defecto, la inserción es más rápida que con cualquier otro contenedor como base!

int test_queue() {
    cout<<"============test_queue============="<<endl;
    clock_t timeStart = clock();
    queue<int, list<int>> c;
    for (long i = 0; i < 100000; i++) {
        c.push(i+1);
    }
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.front()= " << c.front() << endl;
    c.pop();
    cout << "stack.size()= " << c.size() << endl;
    cout << "stack.front()= " << c.front() << endl;
    cout << "use list milli-seconds : " << (clock() - timeStart) << endl;

    timeStart=clock();
    queue<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++) {
        c1.push(i+1);
    }
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.front()= " << c1.front() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.front()= " << c1.front() << endl;

    cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;
}

priority_queue

Para la cola de prioridad, las pruebas revelan que ¡insertar con deque es más rápido que con el vector por defecto! Como base admite los contenedores vector y deque, pero no admite list, map ni set.

int test_priority_queue() {
    cout<<"============test_priority_queue============="<<endl;
    clock_t timeStart = clock();

    priority_queue<int, deque<int>> c1;
    for (long i = 0; i < 100000; i++) {
        c1.push(i+1);
    }
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;
    c1.pop();
    cout << "stack.size()= " << c1.size() << endl;
    cout << "stack.top()= " << c1.top() << endl;

    cout << "use deque milli-seconds : " << (clock() - timeStart) << endl;


    priority_queue<int, vector<int>> c2;
    for (long i = 0; i < 100000; i++)
        c2.push(i+1);
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    c2.pop();
    cout << "stack.size()= " << c2.size() << endl;
    cout << "stack.top()= " << c2.top() << endl;
    cout << "use stack milli-seconds : " << (clock() - timeStart) << endl;
}

Por eso stack, queue y priority_queue no se llaman contenedores, sino que se denominan adaptadores de contenedor.

Temas relacionados

• Análisis del código fuente de STL array | C++那些事
• Análisis profundo de STL string | C++那些事
• STL string preguntas de entrevista explicadas | C++那些事
• Análisis del código fuente de STL deque | C++那些事
• STL optimización de clase base vacía EBO | C++那些事
• STL implementación de una tabla hash escrita a mano | C++那些事
• STL hashtable tabla hash | C++那些事
• Análisis del código fuente de los iteradores STL | C++那些事
• Análisis del código fuente de STL list | C++那些事
• STL map y multimap | C++那些事

Comentarios