Последовательные контейнеры. Итераторы
К последовательным контейнерам относятся шаблонные классы std::vector, std::deque и std::list. На практике класс std::vector используется крайне широко, тогда как два оставшихся класса применяются довольно редко.
Класс std::vector можно рассматривать как альтернативу обычным динамическим массивам. При использовании векторов значительно снижается риск утечек памяти, поскольку освобождение памяти происходит автоматически в деструкторе данного класса (который вызовется даже при возникновении исключения).
Также большим плюсом вектора является возможность автоматически увеличивать свой размер при вставке элементов. Рассмотрим подробнее, как это происходит. Внутри вектора имеется указатель на блок памяти (динамический массив), в котором реально хранятся данные. Для того, чтобы можно было эффективно добавлять новые элементы в конец вектора, размер этого блока памяти обычно берётся с некоторым запасом. Для демонстрации этого приведём следующий код:
std::vector<int> a(4);
a.push_back(5);
std::cout << a.size() << " " << a.capacity() << std::endl;
Функция size возвращает количество элементов в векторе, а функция capacity − размер динамического массива, выделенного для хранения данных. Для компилятора, которым пользовался автор, на экран будет выведено "5 8" − то есть реально в массиве хранится пять элементов, но память выделена под хранение восьми. Это означает, что если мы продолжим добавление в вектор, то следующие три вызова функции push_back выполнятся максимально эффективно (с константной временной сложностью).
Что произойдёт при попытке выполнить вставку в вектор в четвёртый раз? Поскольку место для хранения элементов закончится, то будет выделен новый блок памяти большего размера, все текущие элементы скопируются из старого блока памяти в новый, а старая память будет освобождена. Таким образом, четвёртый вызов функции push_back выполнится существенно медленней, чем предыдущие − с линейной временной сложностью. При этом размер зарезервированной памяти снова увеличился.
Примечание. Насколько именно увеличивается размер зарезервированной памяти, стандартом не регламентируется, поэтому в разных компиляторах может отличаться (обычно в полтора-два раза).
Заметим, что хотя отдельные вызовы push_back могут выполняться с линейной сложностью, но средняя (амортизационная) вычислительная сложность данной функции является константной.
Для обращения к элементам вектора имеются два основных способа. Во-первых, вектор поддерживает эффективное обращение по индексу, используя операцию [] или функцию at, например:
a[2] = 5;
a.at(2) = 5;
Отличие между этими вариантами состоит в том, что в функции at проверяется выход индекса за границы, а в операции [] в целях производительности такая проверка не делается (точнее, проверка может выполняться, если проект компилируется в конфигурации Debug, но в конфигурации Release она отключается).
Во-вторых, как и для других контейнеров, для обращения к элементам вектора можно использовать итераторы.
Итератор − специальный объект, ссылающийся на элемент внутри контейнера. По своему использованию итератор похож на обычный указатель. Например, операция ++ перемещает итератор на следующий элемент контейнера, операция -- − на предыдущий элемент (поддерживается для двунаправленных итераторов). Операция разыменования * возвращает ссылку на текущий элемент. Итераторы произвольного доступа (для векторов и деков) поддерживают также операции прибавления и вычитания целого числа. При этом итератор смещается вперёд или назад на соответствующее число элементов.
Любой контейнер содержит методы begin и end, где функция begin возвращает итератор на первый элемент, а функция end − на воображаемый несуществующий элемент, следующий за последним. Для примера напишем вывод на консоль всех элементов вектора с использованием итератора:
std::vector<int> a = {1, 2, 3, 4, 5};
for (std::vector<int>::iterator it=a.begin(); it!=a.end(); it++){
std::cout << *it << " ";
}
Используя итераторы, важно понимать, что при изменении контейнера некоторые итераторы могут стать недействительными. Например, пусть у нас есть итератор, ссылающийся на какой-то элемент вектора. Вставим в вектор несколько новых элементов. Если в процессе вставки в векторе закончится свободное место, будет выполнено перераспределение памяти. При этом все предыдущие итераторы станут недействительными, а попытка их использования приведёт к неопределённому поведению программы:
std::vector<int> a;
a.push_back(1);
std::vector<int>::iterator it = a.begin();
a.push_back(2); a.push_back(3); a.push_back(4);
*it = 8; // ошибка - неопределённое поведение
Рекомендуется с осторожностью применять итераторы при изменении контейнера, обязательно убедившись по документации, что итераторы, которые вы используете, не могут стать недействительными.
Перечислим кратко некоторые полезные методы, которые имеются в классе std::vector.
• assign − устанавливает новое содержимое для вектора, заменяя его старое содержимое. Пример: a.assign(10, 1); − вектор a будет содержать 10 целых чисел, каждое из которых равно 1.
• resize − изменяет размер вектора. Если размер увеличивается, то новые элементы заполняются значением по умолчанию либо указанным значением. Пример: a.resize(10, 1); устанавливает размер вектора равным 10 элементам. Предыдущие 10 значений вектора сохраняются. Если в векторе было меньше десяти элементов, то новые элементы будут равны единице.
• empty − логическая функция, которая возвращает true, если вектор пуст.
• size − возвращает размер вектора (то есть количество элементов в нём).
• capacity − возвращает ёмкость вектора (количество элементов, которое может быть в нём сохранено перед тем как потребуется перераспределить память).
• reserve − требует установить ёмкостьне меньше, чем указанное значение. Пример: a.reserve(100); означает, что если изначально вектор был пуст, то как минимум следующие сто вызовов push_back не вызовут перераспределения памяти. Может использоваться для небольшого повышения производительности, если заранее известно, сколько элементов будет добавляться.
• clear − очистка вектора.
• pop_back − удаляет последний элемент. При этом ёмкость вектора не уменьшается.
• shrink_to_fit − уменьшает ёмкость (capacity) вектора, устанавливая её равной размеру вектора. Данную функцию удобно использовать после большого количества удалений из вектора для экономии памяти, поскольку ёмкость вектора автоматически не уменьшается никогда.
• insert − выполняет вставку в заданную позицию. Пример: a.insert(a.begin(), 8); − число 8 будет вставлено в начало вектора, остальные элементы сдвинутся вправо. Для вектора данная операция имеет линейную сложность.
• erase − выполняет удаление из заданной позиции одного элемента или указанный диапазон элементов. Пример: a.erase(a.begin()); − удалить начальный элемент; a.erase(a.begin() + 1, a.begin() + 3); − удалить элементы с позиции 1 по позицию 3. Последующие элементы при этом сдвинутся влево. Для вектора данная операция имеет линейную сложность.
Заметим, что многие из перечисленных методов имеются не только в классе std::vector, но и в других контейнерах.
В качестве более сложного примера на применение векторов решим следующую задачу. Имеется N городов, пронумерованных от 1 до N. Некоторые пары городов соединены двухсторонними дорогами (всего дорог M). Требуется найти город, из которого выходит больше всего дорог (если таких несколько, то первый из них), и вывести его, а также города, с которыми он соединён.
Для решения этой задачи будем для каждого города запоминать, какие дороги из него выходят. Для этого создадим вектор, элементами которого будут вектора из целых чисел. Такая структура данных часто используется для представления графов в памяти.
// Пример 5.12 - поиск города с максимальным числом дорог
#include <stdio.h>
#include <vector>
int main() {
int n, m;
scanf("%d %d", &n, &m);
std::vector<std::vector<int> > g(n + 1);
for (int i = 1; i <= m; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
g[v1].push_back(v2);
g[v2].push_back(v1);
}
int ans = 1;
for (int i = 2; i <= n; i++)
if (g[i].size() > g[ans].size())
ans = i;
printf("%d\n", ans);
for (int to : g[ans])
printf("%d ", to);
}
В заключение данного подраздела поговорим немного о классах std::list и std::deque.
Класс std::list представляет собой двухсвязный список. Основное его преимущество по сравнению с вектором − высокая эффективность выполнения операций insert и erase для текущей позиции списка. Однако, для их использования нужно иметь итератор, указывающий на текущую позицию. На практике данный класс используется довольно редко.
Класс std::deque реализует структуру данных "дек" − двухстороннюю очередь, где возможны эффективная вставка и удаление элементов с обоих концов. Кроме методов push_back и pop_back, в данном классе имеются методы push_front и pop_front, которые работают тоже с константной (в среднем) алгоритмической сложностью.
Как и в векторе, в деке реализована операция индексирования [], которая тоже выполняется с константной алгоритмической сложностью. Однако, на практике она работает несколько медленней, чем в векторе, из-за более сложного внутреннего устройства дека (данные внутри дека хранятся не в одном непрерывном блоке памяти, как в векторе, а в нескольких блоках, связанных между собой).
Адаптеры контейнеров
Адаптеры контейнеров представляют собой шаблонные классы, которые используют для внутреннего хранения элементов другие контейнеры, адаптируя их интерфейсы под другой интерфейс. В пункте 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 целых чисел, не превышающих по модулю 109. Требуется для каждого из них вывести ближайшее к нему слева число меньше его (а если такого числа нет, вывести прочерк). Например, если на вход поступили числа 1 3 2 5 2 4, то ответом будет "- 1 1 2 1 2".
Данная задача решается очевидным образом с вычислительной сложностью O(N2). Однако, с помощью стека данную задачу можно решить за 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)), что несколько хуже предыдущего решения.
Ассоциативные контейнеры
Ассоциативные контейнеры реализуют упорядоченные структуры данных с возможностью быстрого поиска по ключу. К ассоциативным контейнерам относятся шаблонные классы std::set, std::multiset, std::map и std::multimap. Для хранения элементов в таких контейнерах используются сбалансированные деревья, что обеспечивает логарифмическую сложность операций поиска, вставки и удаления элементов.
Начиная с C++11, в стандартную библиотеку языка были также добавлены неупорядоченные ассоциативные контейнеры, основанные на хеш-таблицах − классы std::unordered_set, std::unordered_multiset, std::unordered_map и std::unordered_multimap. Данные контейнеры обеспечивают среднюю скорость поиска, вставки и удаления O(1). Однако, в худшем случае вычислительная сложность достигает O(N), поэтому неупорядоченные контейнеры стоит использовать с осторожностью.
Шаблонный класс std::set реализует абстрактный тип данных "множество". Из его методов наиболее часто требуются следующие:
• insert − вставляет элементы в множество
• erase − удаляет элементы из множества
• find − выполняет поиск элемента и возвращает итератор на него. Если элемент не найден, возвращается set::end()
• count − возвращает количество элементов с заданным значением. Поскольку в множестве не может быть дубликатов, то результатом может быть только 0 или 1.
• lower_bound − ищет в множестве самый маленький элемент, больший или равный заданному, и возвращает итератор на него
• upper_bound − ищет в множестве самый маленький элемент, строго больший заданного, и возвращает итератор на него
• clear − очищает содержимое контейнера
• size − возвращает количество элементов
• empty − возвращает true, если множество пусто
• begin − возвращает итератор на первый элемент
• end − возвращает итератор на "псевдоэлемент" после последнего
Множество может содержать элементы любого типа, для которого определена операция сравнения '<' (меньше). Если элементами будут объекты нашего собственного класса, то мы либо должны определить в этом классе operator <, либо задать способ сравнения элементов c помощью второго параметра шаблона std::set.
Рассмотрим примеры решения задач с использованием множества. Первая задача звучит так: вводится N чисел, требуется вывести их в порядке возрастания без повторов. Для решения поместим все числа во множество, при этом повторы уберутся автоматически. Далее, поскольку множество − упорядоченный контейнер, то, пройдясь последовательно циклом по его элементам, мы как раз получим их в порядке возрастания.
// Пример 5.17 - вывод входных чисел по возрастанию без повторов
#include <iostream>
#include <set>
int main() {
int n;
std::cin >> n;
std::set<int> s;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
s.insert(x);
}
for (int x : s)
std::cout << x << " ";
}
Вторая задача чуть посложнее. Вводится N чисел. Нужно вывести те из них, которые встречаются только один раз. Для решения создадим два множества s1 и s2. Входные числа будем заносить в s1. Если обнаружилось, что число уже имеется в s1, то поместим его в s2. В конце выведем все числа из s1, которые отсутствуют в s2.
// Пример 5.18 - поиск чисел, встречающихся в одном экземпляре
#include <iostream>
#include <set>
int main() {
std::set<int> s1, s2;
int n;
std::cin >> n;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
if (s1.count(x) > 0)
s2.insert(x);
s1.insert(x);
}
for (int x : s1)
if (s2.count(x) == 0)
std::cout << x << " ";
}
Третья задача является модификацией предыдущей. Пусть требуется найти такие числа, у которых последняя цифра не встречается ни в одном другом числе. Например, для входных данных 34, 245, 74, 528, 15 ответом будет 528, так как только восьмёрка на конце числа у нас встречается в одном экземпляре.
Для решения этой задачи просто изменим способ сравнения элементов − будем сравнивать числа не обычным образом, а по их последней цифре. Для этого напишем функтор с операцией сравнения по последней цифре и укажем его в качестве второго аргумента шаблонного класса std::set:
// Пример 5.19 - поиск чисел с уникальной последней цифрой
struct lastDigitLess { // функтор для сравнения по последней цифре
bool operator() (int a, int b) const {
return a % 10 < b % 10;
}
};
int main() {
std::set<int, lastDigitLess> s1, s2;
// остальная часть программы не изменилась
Примечание. Конечно, можно было бы эту задачу решить проще и эффективней, причём даже без использования множеств: например, сначала прочитать числа в вектор, при этом запомнив, сколько раз встретилась каждая цифра на конце числа, а потом пройтись по вектору и вывести ответ.
Шаблонный класс std::multiset реализует абстрактный тип данных "мультимножество". По своему использованию он очень похож на std::set. Основное отличие состоит в том, что мультимножество может содержать дубликаты элементов. Это нужно учитывать при выполнении операций − например, вызов s.erase(5) удалит все пятёрки из множества s, а не одну.
Шаблонный класс std::map реализует абстрактный тип данных "ассоциативный массив" или "словарь". Он хранит упорядоченные пары "ключ-значение" и обеспечивает быстрый поиск по ключу, а также быструю вставку и удаление элементов. Из методов данного класса наиболее часто требуются следующие:
• operator[] − возвращает ссылку на значение элемента по заданному ключу. Если элемент с таким ключом отсутствует в контейнере, то он будет автоматически создан со значением по умолчанию. Поэтому нужно с осторожностью использовать данный оператор, чтобы не получить повышенное потребление памяти.
• at − возвращает ссылку на значение элемента по заданному ключу. Если элемент с таким ключом отсутствует в контейнере, будет возбуждено исключение. Данный метод появился в C++11.
• find − ищет элемент с заданным ключом и возвращает итератор на него. Если элемент не найден, возвращается map::end()
• count − возвращает количество элементов с заданным ключом (0 или 1)
• insert − вставляет элементы в контейнер
• erase − удаляет элементы из контейнера
• clear − очищает содержимое контейнера
• size − возвращает размер контейнера (количество элементов)
• empty − возвращает true, если контейнер пуст
• begin − возвращает итератор на первый элемент
• end − возвращает итератор на "псевдоэлемент" после последнего
Как уже говорилось, элементами словаря являются пары "ключ-значение" (используется класс std::pair). Для обращения к ключу используется поле first, для обращения к значению − поле second.
В качестве примера рассмотрим следующую задачу. Вводится N чисел. Требуется найти число (или числа, если их несколько), которые повторяются наиболее часто. Для решения данной задачи создадим словарь, где ключами будут входные числа, а значениями − количество их повторений. Заполнив словарь, найдём в нём элемент с максимальным значением:
// Пример 5.20 - поиск самых часто повторяющихся чисел
#include <iostream>
#include <map>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::map<int, int> nums;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
nums[x]++;
}
int maxCount = 0;
for (auto &elem : nums)
maxCount = std::max(maxCount, elem.second);
for (auto elem : nums)
if (elem.second == maxCount)
std::cout << elem.first << " ";
}
Класс std::multimap похож на класс std::map. Основное отличие состоит в том, что в нём допускаются дубликаты ключей.
Алгоритмы
В стандартной библиотеке имеется большое количество различных алгоритмов, реализованных в виде шаблонных функций. Для использования большинства из них необходимо подключить заголовочный файл algorithm.
В данном разделе мы рассмотрим лишь небольшую часть алгоритмов, полный их перечень можно найти в документации. Вначале перечислим функции, которые мы будем далее рассматривать, после чего опишем их более подробно с примерами применения.
• std::sort − сортировка
• std::stable_sort − устойчивая сортировка
• std::unique − удаление дубликатов
• std::binary_search − двоичный поиск
• std::lower_bound − нижняя граница
• std::upper_bound − нижняя граница
Одной из наиболее востребованных задач в программировании является сортировка данных. Для сортировки в C++ можно использовать две функции − std::sort и std::stable_sort. Отличие между ними состоит в том, что вторая функция выполняет устойчивую сортировку (то есть гарантируется, что элементы с одинаковыми ключами не поменяют свой порядок относительно друг друга). Для некоторых задач это может быть важно. Вычислительная сложность обеих функций составляет O(N∙log(N)). Однако, std::stable_sort требует больше памяти для работы, и на практике работает несколько медленнее, чем std::sort.
По умолчанию сортировка выполняется по возрастанию (точнее, по неубыванию). Однако, порядок можно поменять путём указания дополнительного аргумента функции. Примеры:
std::sort(a.begin(), a.end()); // отсортировать a по возрастанию
std::sort(a.begin(), a.end(), std::greater<int>()); // по убыванию
// по возрастанию последней цифры
std::sort(a.begin(), a.end(), [](int a, int b) {return a%10<b%10;});
В последней строчке для сравнения чисел по последней цифре используется лямбда-выражение (лямбда-выражения поддерживаются начиная с С++11).
Функция std::unique удаляет дубликаты из каждой группы стоящих подряд одинаковых элементов и возвращает итератор на элемент после последнего элемента результата (размер контейнера не изменяется). Например, если вектор a содержал числа 2, 2, 5, 5, 5, 3, 3, 2, 2, то после вызова
auto last = std::unique(a.begin(), a.end());
в векторе будет находиться 2, 5, 3, 2, 5, 3, 3, 2, 2, а итератор last будет ссылаться на пятый элемент вектора. В большинстве случаев функция std::unique применяется к уже отсортированному контейнеру, чтобы убрать в нём все повторяющиеся элементы.
Для примера решим задачу, которую мы уже решали выше с помощью множеств (см. пример 5.17): вводится N целых чисел, требуется вывести их в порядке возрастания без повторов. Решение: прочитаем входные числа в вектор, отсортируем его с помощью std::sort, уберём дубликаты с помощью std::unique, отрежем "хвост" с дубликатами с помощью метода erase, выведем результат:
// Пример 5.21 - вывод чисел по возрастанию без повторов
#include <iostream>
#include <algorithm>
int main() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++)
std::cin >> a[i];
std::sort(a.begin(), a.end());
auto last = std::unique(a.begin(), a.end());
a.erase(last, a.end());
for (int x : a)
std::cout << x << " ";
}
Функции std::binary_search, std::lower_bound и std::upper_bound предназначены для выполнения двоичного поиска в упорядоченном контейнере. Заметим, что логарифмическая сложность достигается лишь для контейнеров, поддерживающих итераторы произвольного доступа − к ним относятся std::vector и std::deque.
Функция std::binary_search возвращает логическое значение − с её помощью можно эффективно определить, присутствует ли элемент в контейнере, но нельзя получить его позицию. Если нам также нужна позиция элемента, то можно использовать функцию std::lower_bound − она возвращает итератор на первый элемент, который больше или равен искомому. Функция std::upper_bound возвращает итератор на первый элемент строго больше искомого.
Для примера рассмотрим следующую задачу. Даны две последовательности чисел. Требуется вывести те числа из второй последовательности, которые также присутствуют в первой. Возможный вариант решения: прочитать первую последовательность в вектор, отсортировать его, для каждого элемента второй последовательности использовать двоичный поиск:
// Пример 5.21 - вывод чисел из второй последовательности,
// которые имеются также и в первой
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
int n, m;
std::cin >> n;
std::vector<int> f(n);
for(int i = 0; i < n; i++)
std::cin >> f[i];
std::sort(f.begin(), f.end());
std::cin >> m;
for(int i = 0; i < m; i++) {
int x; std::cin >> x;
if (std::binary_search(f.begin(), f.end(), x))
std::cout << x << " ";
}
}
Заметим, что в стандартной библиотеке имеется целый ряд других алгоритмов, которые мы не рассмотрели: линейный поиск, копирование и перемещение, слияние, работа с двоичными кучами, генерация перестановок, частичная сортировка, переворот, случайное перемешивание и др. Рекомендуется найти время для более глубокого знакомства со стандартной библиотекой языка C++.
ПАТТЕРНЫ ПРОЕКТИРОВАНИЯ
Шаблоны проектирования или паттерны проектирования (design patterns) являются удачными, хорошо описанными решениями, которые могут применяться при разработке программ. Шаблоны проектирования позволяют обеспечить гибкость и возможность масштабирования программы.
Шаблон включает в себя описание ситуации, в которой он может быть применен, свойства программы, которые он позволяет обеспечить, диаграмму входящих в его состав классов, а также пример программного кода.
Шаблоны проектирования описывают взаимодействие объектов и классов в программе. Не стоит путать их с архитектурными шаблонами, такими, как MVC (model-view-contoller), каналы и фильтры (pipe and filter) или многоуровневая система (layers), которые описывают высокоуровневые связи компонентов и подсистем в программе. Шаблоны проектирования не учитывают особенности конкретных языков программирования и являются универсальными решениями, описывающими общие взаимосвязи между объектами и классами системы.
Шаблоны проектирования могут использоваться при общении разработчиков для быстрого разъяснения принятых архитектурных решений.
При разработке больших программ сложность нарастает лавинообразно. Если не предпринимать упреждающих действий, в определенный момент времени дальнейшая разработка программы станет чрезвычайно трудоемкой и дорогой. Любое изменение будет влиять на множество частей программы и приводить к трудно прогнозируемым результатам.
Шаблоны проектирования − это мощный инструмент борьбы со сложностью программ. Используя шаблоны проектирования, программист получает систему с предсказуемыми характеристиками и экономит значительный объем времени. Шаблон проектирования − это не готовое решение, которое может быть скопировано в код, шаблон должен быть вписан в архитектуру с учетом особенностей разрабатываемого программного продукта.
Начинающим программистам следует помнить, что шаблоны проектирования − это решения, которые применяются при разработке больших программ. Написание программы для расчета площади круга или прямоугольника с использованием шаблонов проектирования так же нелепо, как и применение башенного крана при постройке собачьей конуры. В этом случае программный код, относящийся к шаблонам проектирования, будет многократно превосходить по объему код, отвечающий непосредственно за решение задачи.
Разрабатывая программу, следует соотносить применяемые методы со сложностью задачи, и знание шаблонов проектирования будет значительным подспорьем разработчику.
Шаблоны проектирования можно разделить на три группы: порождающие шаблоны, шаблоны поведения и структурные шаблоны.
Порождающие шаблоны
Порождающие шаблоны описывают различные способы создания объектов в программе при условии сохранения гибкости и независимости от конкретных типов. К порождающим шаблонам относятся: фабричный метод (factory method), абстрактная фабрика (abstract factory), строитель (builder), прототип (prototype), одиночка (singleton) и пул объектов (object pool).
Шаблон "фабричный метод" (factory method) предназначен для создания объектов. Он переносит процесс создания в специальный класс − фабрику, отвечающую за создание объектов конкретного типа. Это делает систему независимой от типа создаваемых объектов, так как имя класса не прописывается жестко в коде программы, а задается с помощью идентификатора перечислимого или строкового типа. Существует вариант фабричного метода, основанный на создании статического метода в базовом классе иерархии.
Шаблон "абстрактная фабрика" (abstract factory) предназначен для создания множества взаимосвязанных объектов. Примером таких объектов могут быть элементы графического интерфейса для различных операционных систем или библиотек графического интерфейса: кнопка − button, надпись − label, текстовое поле − text field и так далее. Абстрактная фабрика позволяет отделить процесс создания элементов управления для конкретной системы от их непосредственного использования.
Шаблон "строитель" (builder) применяется для конструирования сложного объекта. Известна последовательность действий для создания объекта, при этом конкретный строитель может определять содержание этих действий. Данный шаблон позволяет при создании объекта абстрагироваться от его внутренней структуры.
Шаблон "прототип" (prototype)позволяет создавать различные объекты путем их клонирования из эталонного объекта − прототипа. Данный шаблон схож с шаблоном "фабричный метод", однако он предполагает хранение дополнительных экземпляров объектов, которые будут клонироваться.
Шаблон "одиночка" (singleton) отвечает за создание единственного экземпляра некоторого класса и обеспечение централизованного доступа к нему. Данный шаблон позволяет избежать создания глобального объекта класса.
Шаблон "пул объектов" (object pool) позволяет оптимизировать процесс создания объектов за счет хранения отработавших экземпляров и повторного их использования. Создание объектов происходит через запрос к пулу объектов. Если в пуле есть неиспользуемый объект, он будет передан для работы. Если пул пустой, будет создан новый объект. Вместо уничтожения объекты возвращаются в пул. Данный шаблон может быть полезен при работе с объектами, процесс создания которых занимает длительное время. Помимо создания объектов, данный шаблон позволяет контролировать их максимальное количество и проверять наличие невозвращенных объектов в момент завершения программы.
Структурные шаблоны
Структурные шаблоны предназначены для решения вопросов построения системы на основе компоновки объектов и классов. Компоновка осуществляется при помощи наследования и композиции. При наследовании структура классов определяется статически, на этапе написания программы. Базовые классы определяют интерфейс для всей иерархии, подклассы определяют детали реализации. При использовании композиции структура классов определяется динамически путем объединения объектов различных классов на этапе выполнения программы.
К структурным шаблонам относятся: адаптер (adapter), мост (bridge), компоновщик (composite), декоратор (decorator), фасад (facade), приспособленец (flyweight), замести