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

Адаптер 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). Диапазон элементов, обозначенный двумя итераторами. Первый итератор относится к первому элементу в последовательности, а второй — к следующему элементу после последнего. Если диапазон пуст, итераторы равны (и наоборот, если итераторы равны, они обозначают пустой диапазон). Если диапазон не пуст, второй итератор можно достичь последовательным увеличением первого итератора. Последовательное приращение итератора позволяет обработать каждый элемент диапазона.

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

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

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