Перейти к содержанию

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

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

0. Введение

Почему stack и queue не называют контейнерами?

В этом разделе мы, держа этот вопрос в голове, углубимся в анализ исходников.

1. stack

В исходниках stack нас интересуют две вещи: - по умолчанию _Sequence — это deque - внутренние функции реализованы вызовами функций соответствующего контейнера _Sequence.

stack.png

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

Тест нижележащего контейнера stack

Для stack нижележащим контейнером может быть vector, deque, list, но не map и не set. Поскольку компилятор не выполняет всестороннюю проверку, при вызове несуществующей функции компиляция просто не пройдёт; поэтому, хотя set и не может служить нижележащим контейнером, если у него есть определённые функции, вызовы будут успешны — до тех пор, пока не будет вызвана отсутствующая функция.

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

В исходниках queue нас интересуют две вещи: - по умолчанию _Sequence — это deque - внутренние функции реализованы вызовами функций соответствующего контейнера _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();
    }
}
Соответствующая UML-диаграмма классов такова:

queue_.png

Аналогично, приоритетная очередь использует vector в качестве контейнера по умолчанию.

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

}

priority_queue.png

Протестируем нижележащие контейнеры, поддерживаемые этими двумя адаптерами контейнеров:

queue

Для queue нижележащим контейнером может быть deque, а также list, но не vector, map, set; при использовании deque по умолчанию вставки выполняются быстрее, чем с другими контейнерами в качестве нижележащих!

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

Для приоритетной очереди, как показали тесты, вставки с deque выполняются быстрее, чем с vector по умолчанию! Нижележащими поддерживаются контейнеры vector, deque, но не list, map, 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;
}

Поэтому stack, queue и priority_queue не называют контейнерами — их называют адаптерами контейнеров.

Похожие темы

Комментарии