5.9. Адаптеры контейнеров

Адаптеры контейнеров представляют собой шаблонные классы, которые используют для внутреннего хранения элементов другие контейнеры, адаптируя их интерфейсы под другой интерфейс. В пункте 5.2 приводился пример реализации класса PasArray − его вполне можно назвать адаптером контейнера std::vector. В библиотеке STL имеется три адаптера контейнеров − std::stack, std::queue и std::priority_queue.

Класс std::stack реализует абстрактный тип данных "стек", в котором элементы организованы по принципу LIFO (last in − first out, то есть "последним пришёл − первым вышел"). Элементы могут вставляться и удаляться только с одного конца контейнера, который обычно называется вершиной стека. По умолчанию для хранения данных используется класс std::deque (но при желании его можно изменить, например, на std::vector).

Класс std::stack имеет следующие основные методы:

• push − вставляет элемент на вершину стека

• pop − удаляет элемент с вершины стека

• top − возвращает значение элемента на вершине стека

• size − возвращает количество элементов в стеке

• empty − возвращает true, если стек пуст

Все перечисленные операции имеют константную (в среднем) временную сложность.

Рассмотрим примеры решения задач с использованием стека. Первая задача звучит так: вводится некоторое количество целых чисел. Количество чисел заранее неизвестно, окончание ввода обозначается числом ноль. Требуется вывести эти числа в обратном порядке.

// Пример 5.13 - разворот последовательности чисел

#include <iostream>

#include <stack>

int main() {

std::stack<int> st;

for(;;) {

int x;

std::cin >> x;

if (x == 0) break;

st.push(x);

}

while (!st.empty()) {

std::cout << st.top() << " ";

st.pop();

}

}

Теперь решим более интересную задачу. Вводится N целых чисел, не превышающих по модулю 10⁹. Требуется для каждого из них вывести ближайшее к нему слева число меньше его (а если такого числа нет, вывести прочерк). Например, если на вход поступили числа 1 3 2 5 2 4, то ответом будет "- 1 1 2 1 2".

Данная задача решается очевидным образом с вычислительной сложностью O(N²). Однако, с помощью стека данную задачу можно решить за O(N). Будем последовательно помещать входные числа в стек. Заметим следующее: если очередное прочитанное число меньше или равно числу на вершине стека, то число на вершине стека нам никогда более не понадобится (ведь оно никогда не сможет больше оказаться в ответе). Поэтому число на вершине можно удалить. Операцию удаления из стека производим до тех пор, пока на вершине не окажется число меньше текущего − это как раз и будет очередной ответ. Решение:

// Пример 5.14 - поиск для каждого числа ближайшего слева к нему

// числа строго меньше его

#include <iostream>

#include <stack>

const int INF = 1E9+1; // "бесконечность"

int main() {

int n;

std::cin >> n;

std::stack<int> st;

st.push(-INF); // "барьерный" элемент

for (int i = 0; i < n; i++) {

int x;

std::cin >> x;

while (x <= st.top())

st.pop();

if (st.top() == -INF)

std::cout << "- ";

else

std::cout << st.top() << " ";

st.push(x);

}

}

Класс std::queue реализует абстрактный тип данных "очередь", где элементы организованы по принципу FIFO (first in − first out, "первым пришёл − первым вышел"). Элементы вставляются в конец очереди (back), а удаляются из начала очереди (front). По умолчанию для хранения данных используется класс std::deque.

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

• push − вставляет элемент в конец очереди

• pop − удаляет элемент из начала очереди

• front − возвращает значение первого элемента очереди (тот, который будет удалён при следующем вызове pop)

• back − возвращает значение первого последнего элемента очереди (тот, который был вставлен последним вызовом push)

• size − возвращает количество элементов

• empty − возвращает true, если очередь пуста

Рассмотрим пример решения задачи с использованием очередей. Требуется вывести в порядке возрастания первые N чисел (где N не превышает 1000), в разложение которых на простые множители входят только числа 2, 3, 5 (https://www.mccme.ru/free-books/shen/shen-progbook.pdf). Например, для N = 10 ответом будет 1 2 3 4 5 6 8 9 10 12.

Для решения этой задачи создадим три очереди q2, q3 и q5, в которых будут храниться элементы в 2, 3 и 5 раз больше напечатанных, но ещё не напечатанные. На каждом шаге цикла будет делать следующее. Пусть x = min (q2.front(), q3.front(), q5.front()). Выведем x в ответ. Добавим x∙2 в очередь q2, x∙3 − в q3, x∙5 − в q5. Удалим x из тех очередей, где он является первым элементом (заметим, что x может присутствовать в более чем одной очереди).

Для обоснования правильности данного алгоритма заметим, что в каждой очереди элементы будут располагаться в порядке возрастания. Сложность алгоритма, очевидно, линейная. Решение:

// Пример 5.15 - вывод чисел, в разложении которых

// на простые множители встречаются только 2, 3, 5

#include <iostream>

#include <queue>

int main() {

int n;

std::cin >> n;

std::queue<int> q2, q3, q5;

std::cout << 1;

q2.push(2); q3.push(3); q5.push(5);

for (int i = 2; i <= n; i++) {

int x=std::min(q2.front(),std::min(q3.front(),q5.front()));

std::cout << " " << x;

q2.push(x * 2); q3.push(x * 3); q5.push(x * 5);

if (q2.front() == x) q2.pop();

if (q3.front() == x) q3.pop();

if (q5.front() == x) q5.pop();

}

}

Класс std::priority_queue реализует абстрактный тип данных "очередь с приоритетами", в котором первый элемент всегда является наибольшим среди всех элементов контейнера. По умолчанию для хранения данных используется класс std::vector.

Класс std::priority_queue содержит следующие основные методы:

• push − вставляет элемент в очередь

• pop − удаляет верхний (максимальный) элемент из очереди

• top − возвращает верхний (максимальный) элемент

• size − возвращает количество элементов

• empty − возвращает true, если очередь пуста

Методы push и pop имеют логарифмическую вычислительную сложность, остальные перечисленные методы − константную.

Часто бывает нужно, чтобы верхним элементом приоритетной очереди был не максимальный, а минимальный элемент. Для изменения способа сравнения элементов предназначен третий параметр данного шаблонного класса. Изменить порядок на противоположный можно с помощью функционального объекта std::greater:

std::priority_queue<int, std::vector<int>, std::greater<int> > q;

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

// Пример 5.16 - решение задачи из примера 5.15

// с помощью приоритетной очереди

#include <iostream>

#include <queue>

#include <functional>

int main() {

int n;

std::cin >> n;

std::priority_queue<int, std::vector<int>, std::greater<int> > q;

int x = 0;

q.push(1);

for (int i = 1; i <= n; i++) {

while (q.top() == x) // удаляем дубликаты

q.pop();

x = q.top();

q.pop();

std::cout << x << " ";

q.push(x * 2); q.push(x * 3); q.push(x * 5);

}

}

Заметим, что данное решение имеет вычислительную сложность O(N∙log(N)), что несколько хуже предыдущего решения.