9.6. Адаптеры контейнеров

Кроме последовательных контейнеров, библиотека предоставляет три адаптера последовательного контейнера: stack (стек), queue (очередь) и priority_queue (приоритетная очередь). Адаптер (adaptor[4]) — это фундаментальная концепция библиотеки. Существуют адаптеры контейнера, итератора и функции. По существу, адаптер — это механизм, заставляющий нечто одно действовать как нечто другое. Адаптер контейнера получает контейнер существующего типа и заставляет его действовать как другой. Например, адаптер stack получает любой из последовательных контейнеров (array и forward_list) и заставляет его работать подобно стеку. Функции и типы данных, общие для всех адаптеров контейнеров, перечислены в табл. 9.17.

Таблица 9.17. Функции и типы, общие для всех адаптеров

Определение адаптера

Каждый адаптер определяет два конструктора: стандартный конструктор, создающий пустой объект, и конструктор, получающий контейнер и инициализирующий адаптер, копируя полученный контейнер. Предположим, например, что deq — это двухсторонняя очередь deque<int>. Ее можно использовать для инициализации нового стека следующим образом:

stack<int> stk(deq); // копирует элементы из deq в stk

По умолчанию оба адаптера, stack и queue, реализованы на основании контейнера deque, а адаптер priority_queue реализован на базе контейнера vector. Заданный по умолчанию тип контейнера можно переопределить, указав последовательный контейнер как второй аргумент при создании адаптера:

// пустой стек, реализованный поверх вектора

stack<string, vector<string>> str_stk;

// str_stk2 реализован поверх вектора и первоначально содержит копию

svec stack<string, vector<string>> str_stk2(svec);

Существуют некоторые ограничения на применение контейнеров с определенными адаптерами. Всем адаптерам нужна возможность добавлять и удалять элементы. В результате они не могут быть основаны на массиве. Точно так же нельзя использовать контейнер forward_list, поскольку все адаптеры требуют функций добавления, удаления и обращения к последнему элементу контейнера. Стек требует только функций push_back(), pop_back() и back(), поэтому для стека можно использовать контейнер любого из остальных типов. Адаптеру queue требуются функции back(), push_back(), front() и push_front(), поэтому он может быть создан на основании контейнеров list и deque, но не vector. Адаптеру priority_queue в дополнение к функциям front(), push_back() и pop_back() требуется произвольный доступ к элементам; он может быть основан на контейнерах vector и deque, но не list.

Адаптер stack

Тип stack определен в заголовке stack. Функции-члены класса stack перечислены в табл. 9.18. Следующая программа иллюстрирует использование адаптера stack:

stack<int> intStack; // пустой стек

// заполнить стек

for (size_t ix = 0; ix != 10; ++ix)

 intStack.push(ix); // intStack содержит значения 0...9

while (!intStack.empty()) { // пока в intStack есть значения

 int value = intStack.top();

 // код, использующий, значение

 intStack.pop(); // извлечь верхний элемент и повторить

}

Сначала intStack объявляется как пустой стек целочисленных элементов:

stack<int> intStack; // пустой стек

Затем цикл for добавляет десять элементов, инициализируя каждый следующим целым числом, начиная с нуля. Цикл while перебирает весь стек, извлекая его верхний элемент, пока он не опустеет.

Таблица 9.18. Функции, поддерживаемые адаптером контейнера stack, кроме приведенных в табл. 9.17

Каждый адаптер контейнера определяет собственные функции, исходя из функций, предоставленных базовым контейнером. Использовать можно только функции адаптера, а функции основного контейнера использовать нельзя. Рассмотрим, например, вызов функции push_back() контейнера deque, на котором основан стек intStack:

intStack.push(ix); // intStack содержит значения 0...9

Хотя стек реализован на основании контейнера deque, прямого доступа к его функциям нет. Для стека нельзя вызвать функцию push_back(); вместо нее следует использовать функцию push().

Адаптеры очередей

Адаптеры queue и priority_queue определены в заголовке queue. Список функций, поддерживаемых этими типами, приведен в табл. 9.19.

Таблица 9.19. Функции адаптеров queue и priority_queue, кроме приведенных в табл. 9.17 

Библиотечный класс queue использует хранилище, организованное по принципу "первым пришел, первым вышел" (first-in, first-out — FIFO). Поступающие в очередь объекты помещаются в ее конец, а извлекаются из ее начала.

Адаптер priority_queue позволяет установить приоритет хранимых элементов. Добавляемые элементы помещаются перед элементами с более низким приоритетом. По умолчанию для определения относительных приоритетов в библиотеке используется оператор <. Его переопределение рассматривается в разделе 11.2.2.

Упражнения раздела 9.6

Упражнение 9.52. Используйте стек для обработки выражений со скобками. Встретив открывающую скобку, запомните ее положение. Встретив закрывающую скобку, после открывающей скобки, извлеките эти элементы, включая открывающую скобку, и поместите полученное значение в стек, переместив таким образом заключенное в скобки выражение.