Язык программирования C++. Пятое издание - Стенли Липпман

Тип 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

По умолчанию используется контейнер deque, но может быть также реализован на основании контейнеров list или vector. s.pop() Удаляет, но не возвращает верхний элемент из стека s.push(item) s.emplace(args) Создает в стеке новый верхний элемент, копируя или перемещая элемент item либо создавая элемент из аргумента параметра args  s.top() Возвращает, но не удаляет верхний элемент из стека

Каждый адаптер контейнера определяет собственные функции, исходя из функций, предоставленных базовым контейнером. Использовать можно только функции адаптера, а функции основного контейнера использовать нельзя. Рассмотрим, например, вызов функции 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 использует контейнер deque, а адаптер priority_queue — контейнер vector; адаптер queue может использовать также контейнер list или vector, адаптер priority_queue может использовать контейнер deque. q.pop() Удаляет, но не возвращает первый или наиболее приоритетный элемент из очереди или приоритетной очереди соответственно q.front() q.back() Возвращает, но не удаляет первый или последний элемент очереди q. Допустимо только для адаптера queue q.top() Возвращает, но не удаляет элемент с самым высоким приоритетом. Допустимо только для адаптера priority_queue q.push(item) q.emplace(args) Создает элемент со значением item или создает его исходя из аргумента args в конце очереди или в соответствующей позиции приоритетной очереди

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

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

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

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

Резюме

Библиотечные типы контейнеров — это шаблоны, позволяющие содержать объекты указанного типа. В последовательных контейнерах элементы упорядочены и доступны по позиции. У последовательных контейнеров общий, стандартизированный интерфейс: если два последовательных контейнера предоставляют некую функцию, то у нее будет тот же интерфейс и значение в обоих контейнерах.

Все контейнеры (кроме контейнера array) обеспечивают эффективное управление динамической памятью. Можно добавлять элементы в контейнер, не волнуясь о том, где хранить элементы. Контейнер сам управляет хранением. Контейнеры vector и string обеспечивают более подробное управление памятью, предоставляя функции-члены reserve() и capacity().

По большей части, контейнеры определяют удивительно мало функций. Они определяют конструкторы, функции добавления и удаления элементов, функции выяснения размера контейнера и возвращения итераторов на те или иные элементы. Другие весьма полезные функции, такие как сортировка и поиск, определены не типами контейнеров, а стандартными алгоритмами, которые будут описаны в главе 10.

Функции контейнеров, которые добавляют или удаляют элементы, способны сделать существующие итераторы, указатели или ссылки некорректными. Большинство функций, которые способны сделать итераторы недопустимыми, например insert() или erase(), возвращают новый итератор, позволяющий не потерять позицию в контейнере. Особую осторожность следует соблюдать в циклах, которые используют итераторы и операции с контейнерами, способные изменить их размер.

Термины

Адаптер priority_queue (приоритетная очередь). Адаптер последовательных контейнеров, позволяющий создать очередь, в которой элементы добавляются не в конец, а согласно определенному уровню приоритета. По умолчанию при определении приоритета используется оператор "меньше" для типа элемента.

Адаптер queue (очередь). Адаптер последовательных контейнеров, позволяющий создать очередь, в которой элементы добавляются в конец, а предоставляются и удаляются в начале.

Адаптер stack (стек). Адаптер последовательных контейнеров, позволяющий создать стек, в который элементы добавляют и удаляют только с одного конца.

Адаптер (adaptor). Библиотечный тип, функция или итератор, который заставляет один объект действовать подобно другому. Для последовательных контейнеров существуют три адаптера: stack, queue и priority_queue, каждый из которых определяет новый интерфейс базового последовательного контейнера.

Диапазон итераторов (iterator range). Диапазон элементов, обозначенный двумя итераторами. Первый итератор относится к первому элементу в последовательности, а второй — к следующему элементу после последнего. Если диапазон пуст, итераторы равны (и наоборот, если итераторы равны, они обозначают пустой диапазон). Если диапазон не пуст, второй итератор можно достичь последовательным увеличением первого итератора. Последовательное приращение итератора позволяет обработать каждый элемент диапазона.

Интервал, включающий левый элемент (left-inclusive interval). Диапазон значений, включающий первый элемент, но исключающий последний. Обычно обозначается как [i, j), т.е. начальное значение последовательности i включено, а последнее, j, исключено.

Итератор после конца (off-the-end iterator). Итератор, обозначающий (несуществующий) следующий элемент после последнего в диапазоне. Обычно называемый "конечным итератором" (end iterator).

Итератор после начала (off-the-beginning iterator). Итератор, обозначающий (несуществующий) элемент непосредственно перед началом контейнера forward_list. Возвращается функцией before_begin() контейнера forward_list. Подобно итератору, возвращенному функцией end(), к значению данного итератора обратиться нельзя.