Оглавление

• Оглавление
• Массив
• Список
• Стек
• Очередь
• Двусторонняя очередь
• Двоичная куча
• Реализация
• Построение
• Куча в С++
• Строка
• Пара (С++)
• Итераторы (С++)
• Множества
• Множества и мультимножества
• Отображения
• Анализ
• Сравнение множества и сортировки
• Сравнение отображения и массива
• Сравнение очереди с приоритетом и мультимножества

Структуры данных — это форматы эффективного хранения и обработки логически связанных данных.

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

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

Массив

Массив — это структура данных, состоящая из набора элементов одинакового размера, каждый из которых идентифицируется индексом.

Массив бывает статическим — с постоянным размером и динамическим — с изменяемым размером.

Чаще всего при решении задач в качестве массива в языке С++ используют контейнер vector<Type>.

Вектор — это динамический массив, который позволяет эффективно добавлять элементы в конце и удалять последние элементы. Векторы реализованы так, что функции push_back и pop_back в среднем имеют сложность $O(1)$.

Чтобы использовать вектор необходимо подключить библиотеку #include <vector>

Объявление вектора:

vector<Type> Name;
vector<Type> Name = {...};

Основные функции:

.clear()                     //очищает элементы вектора
.empty()                     //проверяет, пуст ли контейнер вектора
.pop_back()                  //удаляет элемент в конце вектора
.push_back(Type)             //добавляет элемент в конец вектора
.resize(unsigned long)       //определяет новый размер вектора
.size()                      //возвращает количество элементов в векторе
.assign(unsigned long, Type) //изменяет размер массива и заполняет одним значением.

Список

Связный список — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка.

Односвязный список — простейшая реализация списка. В узлах хранятся данные и указатель на следующий элемент в списке.

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

Чаще всего при решении задач в качестве двусвязного списка в языке С++ используют контейнер list<Type>.

Лист — Это структура данных, которая построена на двусвязных списках. Это значит, что любой элемент знает только о предыдущем и о следующем элементах.

Чтобы использовать лист необходимо подключить библиотеку #include <list>

Объявление листа:

list<Type> Name;
list<Type> Name = {...};

Основные функции:

.pop_front()            //удалить элемент в начале
.pop_back()             //удалить элемент в конце
.push_front(Type).      //добавить элемент в начала
.push_back(Type)        //добавить элемент в конец
.front()                //обратится к первому элементу
.back()                 //обратиться к последнему элементу
.insert(Iterator, Type) //добавить элемент в какое-то место

Стек

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

Стек имеет реализацию как на массиве, так и на списке. В языке C++ стек реализован контейнером stack<Type>.

Чтобы использовать стек необходимо подключить библиотеку #include <stack>

Объявление стека:

stack<Type> Name;

Основные функции:

.empty()    //проверяет, является ли стек пустым
.pop()      //удаляет элемент из верхней части стек
.push(Type) //добавляет элемент в верхнюю часть стек
.size()     //возвращает количество элементов в стеке
.top()      //возвращает ссылку на элемент в верхней части стека

Очередь

Очередь — структура данных, представляющая из себя упорядоченный набор элементов, в которой новые элементы добавляются в хвост очереди, а удаление происходит из головы очереди, то есть в очереди реализуется принцип «первым вошел — первым вышел».

Очередь имеет реализацию на массиве, на списке, на 2 стеках и на 6 стеках. В языке C++ очередь реализована контейнером queue<Type>

Чтобы использовать очередь необходимо подключить библиотеку #include <queue>

Объявление очереди:

queue<Type> Name;

Основные функции:

.empty()    //проверяет, является ли очередь пустой
.pop()      //удаляет элемент из головы очереди
.push(Type) //добавляет элемент в хвост очереди
.size().    //возвращает количество элементов в очереди
.front().   //возвращает ссылку на элемент в голове очереди
.back()     //возвращает ссылку на элемент в хвосте очереди

Двусторонняя очередь

Дек (двусторонняя очередь) — структура данных, представляющая из себя список элементов, в которой добавление новых элементов и удаление существующих производится с обоих концов. Эта структура поддерживает как FIFO, так и LIFO, поэтому на ней можно реализовать как стек, так и очередь. В первом случае нужно использовать только методы головы или хвоста, во втором — методы push и pop двух разных концов.

Дек имеет реализацию на. векторе, списке и 2 стеках. В языке C++ дек реализован контейнером deque<Type>

Чтобы использовать дек #include <deque>

Объявление дека:

deque<Type> Name;

Основные функции:

.empty()          //проверяет, является ли дек пустым
.pop_back()       //удаляет элемент из хвоста дека
.push_back(Type)  //добавляет элемент в хвост дека
.pop_front()      //удаляет элемент из головы дека
.push_front(Type) //добавляет элемент в хвост дека
.size()           //возвращает количество элементов в деке
.front()          //возвращает ссылку на элемент в голове дека
.back()           //возвращает ссылку на элемент в хвосте дека

Двоичная куча

Другое название, лучше отражающее функциональность — очередь с приоритетами.

Заметим, что двоичная куча строится неоднозначно: например, значения сыновей, которые являются листами, всегда можно менять местами. Фиксирована только сама структура и предикат «родитель не больше детей».

Обозначим высоту дерева как h. Так как куча всегда состоит из нескольких слоев заполненных полностью и одного заполненного частично, и каждый следующий слой содержит в два раза больше вершин, чем предыдущий, то высота дерева будет O(log n).

Помимо основных трёх, можно определить и другие, например «изменить значение ключа», но пока мы остановимся на этих трёх.

Реализация

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

Хранить кучу будем в виде массива t, где у корня индекс равен 1, а у вершины k индексы ее детей равны 2・k и (2・k + 1). Нулевая ячейка массива при этом остается пустой.

Дальше определим две вспомогательные функции, которые восстанавливают инварианты кучи при изменении значения одного элемента.

Если значение элемента уменьшается, то чтобы исполнялось первое условие кучи, его, возможно, нужно переместить выше. Это можно сделать, несколько раз итеративно меняя элемент с его непосредственным родителем, если его значение больше. Так как каждый раз мы поднимаемся по дереву, то работать такая функция будет за его высоту:

void sift_up(int v) {
	// если элемент больше своего отца, то всё корректно и больше ничего 
	// делать не нужно
	while (v > 1 && t[v] < t[v / 2]) {
		// иначе меняем его с отцом и запускаемся от отца
		swap(t[v], t[v / 2]);
		v /= 2;
	}
}

Если значение измененного элемента увеличивается, то нам нужно наоборот переместить его ниже. Это можно сделать похожим способом, итеративно меняя его с меньшим из сыновей и продолжая уже от него. Аналогично, каждый раз мы спускаемся глубже, поэтому эта процедура будет работать тоже за высоту дерева:

void sift_down(int v) {
	// пока не пришли в лист
	while (2 * v <= n) { // n -- количество элементов в куче
		int l = 2 * v; // левый сын
		int r = 2 * v + 1; // правый сын
		// если правый сын существует и меньше, выбираем его
		int u = (r <= n && t[r] < t[l] ? r : l);
		if (t[v] <= t[u]) {
			break; // инвариант и так выполняется, завершаемся
		}
		swap(t[v], t[u]);
		v = u;
	}
}

Примечание. Если рассматривать не двоичную кучу, а так называемую d-кучу, в которой у каждой вершины может быть не более d сыновей, то время работы останется таким же для любой константы d.

Построение

Кучу для множества из n элементов можно построить, просто добавляя их по одному — такой алгоритм построения работает за O(n · log n), что в большинстве случаев достаточно быстро. Но это можно делать и чуть быстрее — за линейное время. Мы на самом деле хотим просто переупорядочить элементы некоторого массива t так, чтобы для любого индекса 1 ≤ i ≤ n выполнялось условие кучи.

Давайте тогда это свойство кучи восстанавливать с конца: будем постепенно увеличивать суффикс, на котором выполняется свойство, с помощью просеивания вниз (sift_down). Получаем следующий алгоритм:

void build_heap() {
	for (int i = n; i > 0; --i) {
		// для суффикса t[i + 1 .. n] свойство кучи выполняется
		sift_down(i);
		// теперь выполняется для суффикса t[i .. n]
	}
}

Куча в С++

В C++ куча реализована контейнером priority_queue<Type> Объявление кучи:

priority_queue<Type> Name;

.empty()                       // проверяет, является ли куча пустой
.pop()                         // удаляет максимальный элемент
.push(Type)                    // добавляет элемент в кучу
.size()                        // возвращает количество элементов в куче
.top()                         // возвращает ссылку на максимальный элемент

Строка

Строка — массив символов.

В языке C++ строка реализована контейнером string

Чтобы использовать строку необходимо подключить библиотеку

#include <string>

Объявление строки:

string Name;
string Name = "...";

Основные функции:

.clear()                            // очищает строку
.empty()                            // проверяет, пуста ли строка
.pop_back()                         // удаляет элемент в конце строки
.push_back(Type)                    // добавляет элемент в конец строки
.resize(unsigned long)              // определяет новый размер строки
.size()                             // возвращает количество элементов в строке
.assign(iterator, iterator)         // удаляет строку и копирует указанны элементы в пустую строку
.stod(string)                       // преобразует последовательность символов в double

stoi(string)           // преобразует последовательность символов в int
stoll(string)          // преобразует последовательность символов в long long
to_string(Type)        // преобразует значение в string

.substr(size_t, size_t) // копирует из указанного положения в строке
												// подстроку, содержащую по крайней мере несколько символов

Также для строк перегружено множество операторов (==, +, …).

Пара (С++)

Пара — структура, позволяющая хранить пару элементов не обязательно одного типа.

Пару можно объявить:

pair<Type1, Type2> <Name>;
pair<Type1, Type2> <Name> = {... , ...};

Доступ к элементам пары возможен через .first, .second:

pair<int, vector<int>> pr1 = {9, {1,2,3}};
pair<int, double> pr2;
pr2.first = 0;
pr2.second = 3.1;
cout << pr2.first << " " << pr2.second << '\n';

Итераторы (С++)

Итератор — это объект, указывающий на элемент какого-то контейнера.

Итератор является абстракцией над концепцией указателей. Если указатели работают только с последовательными данными (массивами), то итераторы работают с любыми контейнерами — например со связными списками или деревьями поиска — причём в единообразном синтаксисе, что сильно помогает разработчикам библиотек избегать дублирования кода.

Чтобы получить элемент, на который указывает итератор it, необходимо воспользоваться оператором разыменования: *it. Если нужно перейти к следующему элементу надо использовать инкремент: ++it (постфиксного инкремента у итераторов нет). У всех контейнеров есть какой-то первый и последний элемент. Итератор на первый элемент можно получить через begin(), а через end() можно получить итератор на некий фиктивный элемент, следующий последним (обратите внимание на асимметрию итераторов: begin() указывает на элемент, принадлежащий структуре данных, а end() ведет за пределы структуры данных). Таким образом, если проходить от begin() до end() не включительно, ты мы пройдём по всем элементам контейнера.

Итератор можно объявить:

<Container> :: iterator <Name>;

<Container> cont_name = {...};
<Container> :: iterator <Name> = cont_name.begin();

auto <Name> = cont_name.begin();

Также в последних версиях C++ итерация по контейнеру возможна с использованием auto:

vector<int> vec = { 1,2,3,4,5 };
for (auto it : vec)
{
	cout << it << " ";
}
for (auto &it : vec)
{
	cout << it << " ";
}

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

Диапазоном называется последовательность соседних элементов структуры данных. Чаще всего диапазон задается с помощью двух итераторов: указывающего на первый элемент и на позицию за последним элементом. В частности, итераторы begin() и end() определяют диапазон, содержащий все элементы структуры данных.

Функции из стандартной библиотеки C++ обычно применяются к диапазонам. Так, в следующем фрагменте сначала вектор сортируется, затем порядок его элементов меняется на противоположный, и, наконец, элементы перемешиваются в случайном порядке.

vector<int> v = {5,2,10,3,8};
sort(v.begin(),v.end()); // v = {2 3 5 8 10}
reverse(v.begin(),v.end()); // v = {10 8 5 3 2}
random_shuffle(v.begin(),v.end()); // v = {2 10 3 8 5}

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

cout << *v.begin() << "\n";

Более полезный пример: функция lower_bound возвращает итератор на первый элемент отсортированного диапазона, значение которого не меньше x, а функция upper_bound – итератор на первый элемент, значение которого не больше x:

vector<int> v = {2,3,3,5,7,8,8,8};
auto a = lower_bound(v.begin(),v.end(),5);
43auto b = upper_bound(v.begin(),v.end(),5);
cout << *a << " " << *b << "\n"; // 5 7

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

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

sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());

Множества

Множеством называется структура данных, в которой хранится набор элементов. Основные операции над множествами – вставка, поиск и удаление. Множества реализованы так, что все эти операции эффективны, что часто позволяет улучшить время работы алгоритмов, в которых множества используются.

Множества и мультимножества

Обе структуры эффективны, и во многих случаях годится любая(о различиях, особенностях и реализациях этих структур мы поговорим в другой главе. Отметим только, что unordered_set имеет среднюю оценку O(1), а также немалую константу на каждой операции. О том что такое средняя оценка мы также разберем другой главе).

Чтобы использовать set(unordered_set) необходимо подключить библиотеку

#include <set>
#include <unordered_set>

Объявление set(unordered_set):

set<Type> Name;
unordered_set<Type> Name;

Основные функции:

.clear()                  // стирает все элементы
.empty()                  // проверяет, пуст ли set(unordered_set)
.erase(Type)              // удаляет элемент или диапазон элементов в наборе с заданных
                          // позиций или удаляет элементы, соответствующие заданному
                          // ключу
.find(Type)               // возвращает итератор, адресующий расположение элемента в
													// наборе с ключом, эквивалентным указанному ключу
.insert(Type)             // вставляет элемент или диапазон элементов
.size()                   // возвращает количество элементов в контейнере

Важным свойством множеств является тот факт, что все их элементы различны, а функция insert никогда не добавляет элемент во множество, если он в нем уже присутствует. Множество в основном можно использовать как вектор, однако доступ к элементам с помощью оператора [ ] невозможен. В следующем коде печатается количество элементов во множестве, а затем эти элементы перебираются:

cout << s.size() << "\n";
for (auto x : s) {
	cout << x << "\n";
}

Функция find(x) возвращает итератор, указывающий на элемент со значением x. Если же множество не содержит x, то возвращается итератор end().

if (s.find(x) == s.end()) {
	// x не найден
}

Упорядоченные множества. Основное различие между двумя структурами множества в C++ – то, что set упорядочено, а unordered_set не упорядочено. Поэтому если порядок элементов важен, то следует пользоваться структурой set. Рассмотрим задачу о нахождении наименьшего и наибольшего значений во множестве. Чтобы сделать это эффективно, необходимо использовать структуру set. Поскольку элементы отсортированы, найти наименьшее и наибольшее значения можно следующим образом:

auto first = s.begin();
auto last = --s.end();
cout << *first << " " << *last << "\n";

Отметим, что поскольку end() указывает на позицию, следующую за последним элементом, то необходимо уменьшить итератор на единицу. В структуре set имеются также функции lower_bound(x) и upper_bound(x), которые возвращают итератор на наименьший элемент множества, значение которого не меньше x или больше x соответственно. Если искомого элемента не существует, то обе функции возвращают end().

cout << *s.lower_bound(x) << "\n";
cout << *s.upper_bound(x) << "\n";

Мультимножества. В отличие от множества, в мультимножество один и тот же элемент может входить несколько раз. В C++ имеются структуры multiset и unordered_multiset, похожие на set и unordered_set. В следующем коде в мультимножество три раза добавляется значение 5.

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 3

Функция erase удаляет все копии значения из мультимножества.

s.erase(5);
cout << s.count(5) << "\n"; // 0

Если требуется удалить только одно значение, то можно поступить так:

s.erase(s.find(5));
cout << s.count(5) << "\n"; // 2

Отметим, что во временной сложности функций count и erase имеется дополнительный множитель O(k), где k – количество подсчитываемых (удаляемых) элементов. В частности, подсчитывать количество копий значения в мультимножестве с помощью функции count неэффективно.

Отображения

Отображением называется множество, состоящее из пар ключ - значение.

Отображение можно также рассматривать как обобщение массива. Если в обыкновенном массиве ключами служат последовательные целые числа 0, 1, …, n − 1, где n – размер массива, то в отображении ключи могут иметь любой тип и необязательно должны быть последовательными. В стандартной библиотеке C++ есть две структуры отображений, соответствующие структурам множеств: в основе map лежит сбалансированное двоичное дерево со временем доступа к элементу O(log n), а в основе unordered_map – техника хеширования со средним временем доступа к элементам O(1).

Чтобы использовать map(unordered_map) необходимо подключить библиотеку

#include <map>
#include <unordered_map>

Объявление map(unordered_map):

map<Type> Name;
unordered_map<Type> Name;

Основные функции:

.clear()                       // стирает все элементы
.empty()                       // проверяет, пуст ли map(unordered_map)
.erase(Type)                   // удаляет элемент или диапазон элементов в наборе с заданных
                               // позиций или удаляет элементы, соответствующие заданному
                               // ключу
.find(Type)                    // возвращает итератор, адресующий расположение элемента в
															 // наборе с ключом, эквивалентным указанному ключу
.insert(Type)                  // вставляет элемент или диапазон элементов
.size()                        // возвращает количество элементов в контейнере

Для доступа к значениям через ключ осуществляется оператором [ ]. В следующем фрагменте создается отображение, ключами которого являются строки, а значениями – целые числа:

map<string, int> m;
m["monkey"] = 4;
m["banana"] = 3;
m["harpsichord"] = 9;
cout << m["banana"] << "\n"; // 3

Если в отображении нет запрошенного ключа, то он автоматически добавляется, и ему сопоставляется значение по умолчанию. Например, в следующем коде в отображение добавляется ключ “aybabtu” со значением 0.

map<string, int> m;
cout << m["aybabtu"] << "\n"; // 0

Функция count проверяет, существует ли ключ в отображении:

if (m.count("aybabtu")) {
	// ключ существует
}

В следующем коде печатаются все имеющиеся в отображении ключи и значения:

for (auto x : m) {
	cout << x.first << " " << x.second << "\n";
}

Анализ

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

Сравнение множества и сортировки

Многие задачи можно решить, применяя как множества, так и сортировку. Важно понимать, что алгоритмы на основе сортировки обычно гораздо быстрее, даже если это не очевидно из одного лишь анализа временной сложности. В качестве примера рассмотрим задачу о вычислении количества уникальных элементов вектора. Одно из возможных решений – поместить все элементы во множество и вернуть размер этого множества. Поскольку порядок элементов не важен, можно использовать как set, так и unordered_ set. Можно решить задачу и по-другому: сначала отсортировать вектор, а затем обойти его элементы. Подсчитать количество уникальных элементов отсортированного вектора просто. В таблице приведены результаты эксперимента, в котором оба алгоритма тестировались на случайных векторах чисел типа int. Оказалось, что алгоритм на основе unordered_set примерно в два раза быстрее алгоритма на основе set, а алгоритм на основе сортировки быстрее алгоритма на основе set более чем в 10 раз. Отметим, что временная сложность обоих алгоритмов равна O(n · log n), и тем не менее алгоритм на основе сортировки работает гораздо быстрее. Причина в том, что сортировка – простая операция, тогда как сбалансированное двоичное дерево поиска, применяемое в реализации set, – сложная структура данных. Результаты эксперимента по вычислению количества уникальных элементов вектора. Первые два алгоритма вставляют элементы во множество, а последний сортирует вектор, а затем просматривает соседние элементы

Сравнение отображения и массива

Отображения – удобные структуры данных, по сравнению с массивами, поскольку позволяют использовать индексы любого типа, но и постоянные множители велики. В следующем эксперименте мы создали вектор, содержащий n случайных целых чисел от 1 до 10^6, а затем искали самое часто встречающееся значение путем подсчета числа вхождений каждого элемента. Сначала мы использовали отображения, но поскольку число 10^6 достаточно мало, то можно использовать и массивы. Результаты эксперимента сведены в таблице. Хотя unordered_map примерно в три раза быстрее map, массив все равно почти в 100 раз быстрее. Таким образом, по возможности следует пользоваться массивами, а не отображениями. Особо отметим, что хотя временная сложность операций unordered_map равна O(1), скрытые постоянные множители, характерные для этой структуры данных, довольно велики.

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

Сравнение очереди с приоритетом и мультимножества

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