Адаптеры stl-контейнеров

В стандартной библиотеке шаблонов имеются так называемые АДАПТЕРЫ КОНТЕЙНЕРОВ (container adaptors), моделирующие известные абстрактные типы данных (АТД):

• std::stack (стек, заголовочный файл <stack>);

• std::queue (очередь, заголовочный файл <queue>);

• std::priority_queue (очередь с приоритетами, заголовочный файл <priority_queue>).

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

СТЕК (stack) логически представляет собой стопку вертикально сложенных один на другом предметов. Новый элемент можно разместить только сверху других на ВЕРШИНЕ (top), удалять также разрешается только лишь элемент находящийся в данный момент на вершине. Элемент вставленный последним будет удален первым (принцип LIFO - Last In First Out), соответственно, элемент вставленный первым будет удален последним:

Набор методов реализации std::stack весьма прост и ограничен:

• метод top возвращает ссылку на значение, находящееся в вершине;

• метод empty выясняет является ли стек пустым в данный момент;

• метод size возвращает количество размещенных в стеке в текущий момент элементов;

• метод push “вталкивает” новое значение в стек, размещая его копию на вершине “поверх” предыдущего элемента;

• метод emplace похож на метод push, однако перемещает элемент на вершину, а не копирует;

• метод pop “выталкивает” значение на вершине из стека.

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

От внутреннего контейнера код стека ожидает наличие операций push_back, emplace_back, pop_back, back. Обеспечить такой список операций способны контейнеры std::vector, std::list и std::deque. По умолчанию, стандартная библиотека использует контейнер std::deque:

template<

typename T,

typename Container = std::deque<T>

> class stack;

Чтобы выбрать другой контейнер, необходимо указать его при создании объекта вторым аргументом:

std::stack< int, std::vector< int > > s1;

std::stack< int, std::list< int > > s2;

ОЧЕРЕДЬ (queue) позволяет помещать новые элементы с конца, а забирать с начала. Первый размещенный элемент будет удаляться первым, а последний размещенный - последним (принцип FIFO - First In First Out):

В std::queue представлены следующие методы:

• метод front возвращает первый элемент в очереди;

• метод back возвращает последний элемент в очереди;

• метод empty выясняет является ли очередь пустой в данный момент;

• метод size возвращает количество размещенных в очереди в текущий момент элементов;

• метод push помещает новое значение в очередь, размещая его копию в конец;

• метод emplace похож на метод push, однако перемещает элемент в очередь, а не копирует;

• метод pop удаляет элемент, стоящий в начале очереди.

Адаптер std::queue требует от базового контейнера как работы с концом (push_back, emplace_back, back), так и работы с началом (front, pop_front). Требование работы с начальными элементами исключает из контейнеров-кандидатов std::vector. Соответственно, очередь может быть реализована либо на основе std::list, либо std::deque. Контейнер std::deque используется по умолчанию.

ОЧЕРЕДЬ С ПРИОРИТЕТАМИ (std::priority_queue) похожа на обычную очередь с точки зрения вставки новых элементов, однако извлечение элементов происходит в порядке убывания. Вместо методов front и back, имеется метод top, содержащий максимальное значение среди всех размещенных элементов в данный момент. Элементы внутри такой очереди сравниваются при помощи оператора <. Реализация очереди с приоритетами std::priority_queue, как правило, основана на идее двоичной кучи (binary heap):

Реализация двоичной кучи предполагает, что к элементам обеспечивающего контейнера можно будет обращаться в случайном порядке по индексу. Среди контейнеров такими возможностями обладают только std::vector и std::deque. При этом, std::vector используется по умолчанию.

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