Оглавление

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

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

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

Массив

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

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

Untitled

Чаще всего при решении задач в качестве массива в языке С++ используют контейнер 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) //изменяет размер массива и заполняет одним значением.

Список

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

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

Untitled