Отдельной категорией библиотеки стандартных шаблонов являются адаптеры. Адаптеры — это не новые понятия или реализации, а адаптация уже существующих понятий библиотеки под конкретные, часто использующиеся цели. Часто такая адаптация делается посредством ограничения функциональности базового понятия под запросы адаптера. В библиотеке представлены адаптеры контейнеров, итераторов и функций.
Проще всего показать, как появляются адаптеры на примере адаптеров контейнеров: stack (стек), queue (очередь), priority_queue (очередь с приоритетами). Уже из их перечисления понятно, что:
Это очень широко и часто используемые структуры данных;
Для них не нужны какие-то отдельные реализации. Для обеспечения их функциональности можно использовать (адаптировать) в качестве базового любой из стандартных контейнеров STL, который обеспечивает операции типа push_back, pop_back или pop_front (в зависимости от типа адаптера);
«Лишние» операции из арсенала базового контейнера для адаптера нужно исключить (чтобы не создавать искушения … например, операцию индексации, если vector используется для адаптации стека);
И, вместо громоздких шаблонных синтаксических определений (заголовочные файлы <stack>, <queue> и т. п.), обратимся к примерам…
Начнём со стека: стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека. Это коллекция данных, функционирующая по принципу LIFO (Last In — First Out). Вот такой простенький пример раскрывает нам практически всю функциональность стека:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | #include <iostream> #include <vector> #include <stack> #include <string> using namespace std; int main(int argc, char *argv[]) { setlocale(LC_ALL, "rus"); stack<string> st; stack<string, vector<string> > vst( vector<string>({ "строка 1", "строка 2" }) ); vst.push("последняя строка"); while (!vst.empty()) { cout << vst.top() << " : в стеке строк " << vst.size() << endl; vst.pop(); } cout << "стек " << (vst.empty() ? "" : "не ") << "пуст" << endl; } |
Проанализируем код и сделаем некоторые выводы:
Первое определение stack<string> (мы его дальше не используем) объявляет переменную стек, элементами которого являются строки. Обращаем внимание на то, что объекты string сами по себе являются контейнерами STL. Таким образом, стек может содержать элементы любой глубины вложенности контейнеров (что свойственно и любым другим контейнерам STL).
Такое определение ( stack<string> ) вы сможете увидеть, как описание стека в подавляющем большинстве примеров. Многие авторы и не подозревают, что может быть по-другому. Но мы воспользуемся другим определением: stack< string, vector<string> > — это стек строк (во многом эквивалентный предыдущему), но построенный на базовом классе vector<string>. В качестве базовых могут использоваться, например, vector, list и deque, или даже ваш собственный контейнерный класс, расширяющий базовые. По умолчанию (так как в 1-м определении) используется база deque. Иногда спрашивают: почему нельзя написать (определить так в реализации stack): stack< vector<string> > (убрав дублирование string)? Потому что (и это вполне возможно) это будет описание совсем другого типа: стек векторов строк (см. выше замечание о структурной вложенности контейнеров).
Дальше следует инициализация начального состояния из вектора строк. Отметьте, что такой трюк допустим только в стандарте C++11.
Дальше мы видим практически все операции (методы), требуемые от стека: push() – заталкивание объекта в стек, top() – получение ссылки на элемент в вершине стека, pop() – выбрасывание верхнего элемента, size() – текущий размер стека, empty() – проверка на пустоту.
Как легко понять, адаптер stack потерял присущие базовому контейнеру методы (at(), [ ] и др.), но приобрёл (переопределением) свои собственные (push(), pop()).
Теперь посмотрим что из этого получилось:
Разобравшись со стеком теперь элементарно просто перенести аналогии на очередь. В противоположность стеку – это коллекция данных, функционирующая по принципу FIFO (First In — First Out). (Это такая «труба», в один конец которой что-то втекает, а из другого конца затем вытекает.)
Специально оставим для очереди пример практически неизменным, внеся правки, требуемые семантикой языка:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <iostream> #include <list> #include <queue> #include <string> using namespace std; int main(int argc, char *argv[]) { setlocale(LC_ALL, "rus"); queue<string> st; queue<string, list<string> > vst( list<string>({ "строка 1", "строка 2" }) ); vst.push("последняя строка"); while (!vst.empty()) { cout << vst.front() << " : в очереди строк " << vst.size() << endl; vst.pop(); } cout << "очередь " << (vst.empty() ? "" : "не ") << "пуста" << endl; } |
От нас потребовали изменить:
Очередь не может быть построена на базовом контейнере vector у которого нет метода pop_front(), но может строиться на list, deque, или любом другом контейнере, реализующем базовый набор методов (front(), push_back(), pop_front()), по умолчанию используется deque.
У адаптера queue нет метода top(), а есть метод аналогичного смысла front().
И в итоге получаем (сравните с результатами для стека!):
