Специальные контейнеры

Стандартная библиотека С++ не ограничивается контейнерами, входящими в STL В нее также включены контейнеры, предназначенные для особых целей и обладающие простыми, почти очевидными интерфейсами. Такие контейнеры можно разделить на группы.

О Так называемые контейнерные адаптеры,

К этой группе относятся контейнеры, адаптирующие стандартные контейнеры STL для особых целей. Существуют три стандартных контейнерных адаптера:

□ стеки;

□ очереди;

□ приоритетные очереди.

Приоритетными очередями называются очереди, элементы которых автоматически сортируются в соответствии с заданным критерием сортировки. Таким образом, значение следующего: элемента приоритетной очереди больше; значения предыдущего .

О Специальный контейнер bitset.

Контейнер bitset представляет собой битовое поле с произвольным, но фиксированным количеством битов. В стандартную библиотеку С++ также включен специальный контейнер переменного размера для логических значений vector<bool> (см. с. 167).

Стеки

Класс stacko реализует стек, работгпощий по принципу последним прибыл, первым обслужен (LIFO). Функция push() вставляет в стек произвольное количество элементов (рис. 10.1), а функция рор() удаляет элементы в порядке.

обратном порядку их вставки.

Стек

push{)

Рис. 10.1. Интерфейс стека

Чтобы использовать стек в программе, необходимо включить в нее заголовочный файл <stack>:

#1nclude <stack>

В файле <stack> класс stack определяется следующим образом:

namespace std {

template <class Г,

class Container = deque<T> > class stack:

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

Например, следующее объявление определяет стек с элементами типа int:

std::stack<1nt> st: Стек целых чисел

Реализация стека просто отображает операции со стеком на соответствующие операции с используемым контейнером (рис. 10.2). Допускается применение любого класса последовательного контейнера с поддержкой функций Ьаск(), push back() и рор Ьаск(). Например, элементы стека могут храниться в векторе или списке:

std;;stack<1nt.std::vector<int> > st; Стек целых чисел на базе вектора

Основной интерфейс

Основной интерфейс стеков состоит из функций push(), top() и рор():

О функция push() вставляет элемент в стек;

О функция top() возвращает верхний элемент стека;

О функция рор() удаляет элемент из стека.

В исходной версии STL стек определялся в заголовочном файле <stack.li>. В предыдущих версиях STL единственным параметром шаблона был тин контейнера, а объявление стека с элементами типа mt выглядело так:

stack<deque<1nt> > st;

top()

Стек

Ьаск{)

Рис 10.2. Внутренний интерфейс стека

Обратите внимание: функция рор() удаляет верхний элемент, но не возвра-тцает его, тогда как функция tDp() возвращает верхний элемент стека без удаления. Следовательно, чтобы обработать верхний элемент и удалить его из стека, всегда приходится вызывать обе функции. Такой интерфейс несколько неудобен, но он более эффективен при удалении верхнего элемента без его обработки. Если стек не содержит ни одного элемента, поведение функций top() и рор() не определено. Наличие элементов в стеке проверяется функциями size() и empty().

Если стандартный интерфейс stacko вас не устраивает, вы легко можете написать более удобный интерфейс. Пример приведен на с. 428.

Пример использования стека

пример использования класса stacko:

cont/stackl.cpp Iinclude <iostream> Iinclude <stack> using namespace std;

int mainO {

stack<1nt> St;

Занесение трех элементов в стек st.push(l) st.push(2) st.push(3)

Извлечение и вывод двух элементов из стека

cout st.topO ;

st.popC);

cout St.topO : St.popO;

Модификация верхнего элемента St.topO = 77;

Занесение двух новых элементов