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

Análise do código-fonte do STL queue e stack

0. Introdução

Por que stack e queue não são chamados de contêineres?

Nesta seção, vamos levar essa questão para uma análise profunda do código-fonte.

1. stack

No código-fonte do stack, prestamos atenção em dois pontos: - o _Sequence padrão é deque - as funções internas são implementadas chamando as funções do contêiner correspondente 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); }
}

Testando o contêiner subjacente do stack

Para o stack, o contêiner subjacente pode ser vector, deque ou list, mas não pode ser map nem set. Como o compilador não faz uma verificação abrangente, quando uma função chamada não existe, a compilação falha; assim, embora um set, por exemplo, não possa servir como contêiner subjacente, se ele tiver certas funções, as chamadas ainda terão sucesso — até que se chame uma função que não existe.

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

No código-fonte do queue, prestamos atenção em dois pontos: - o _Sequence padrão é deque - as funções internas são implementadas chamando as funções do contêiner correspondente 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();
    }
}

O diagrama de classes UML correspondente é o seguinte:

Pelo mesmo raciocínio, a priority queue usa vector como contêiner padrão.

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

}

Testando os contêineres subjacentes suportados por esses dois adaptadores de contêiner:

queue

Para o queue, o contêiner subjacente pode ser deque e também list, mas não pode ser vector, map nem set; usando o deque padrão, a eficiência de inserção é maior do que com outros contêineres 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 a priority queue, os testes mostram que usar deque é mais rápido na inserção do que o vector padrão! Há suporte aos contêineres vector e deque como base, mas não a list, map nem 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 isso, stack, queue e priority_queue não são chamados de contêineres: chamamo-los de adaptadores de contêiner.

Tópicos relacionados

• Análise do código-fonte do STL array | C++那些事
• Análise aprofundada do STL string | C++那些事
• Questões de entrevista sobre STL string explicadas | C++那些事
• Análise do código-fonte do STL deque | C++那些事
• STL otimização de classe base vazia EBO | C++那些事
• STL implementação manual de tabela hash | C++那些事
• STL hashtable tabela hash | C++那些事
• Análise do código-fonte dos iteradores da STL | C++那些事
• Análise do código-fonte do STL list | C++那些事
• STL map e multimap | C++那些事

Comentários