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

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 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.52. Используйте стек для обработки выражений со скобками. Встретив открывающую скобку, запомните ее положение. Встретив закрывающую скобку, после открывающей скобки, извлеките эти элементы, включая открывающую скобку, и поместите полученное значение в стек, переместив таким образом заключенное в скобки выражение.

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

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

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

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

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

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

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

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

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