class Algorithms {
public:
Algorithms lecture {
.author = "Р.А. Нестеров"
.year = "2026/27"
.course = "НИУ ВШЭ ПИ, 2 курс"
};
алгоритмы
и структуры данных
// 01. Асимптотические границы временной сложности алгоритма
void lower_bound();
void upper_bound();
// 02. Абстрактный тип данных, упорядочение объектов
// и размещение структур данных в памяти
template<typename T> Container {...};
void order_objects();
void memory_layout();
// 03. ADT Связный список и варианты его реализации
template<typename T> List {...};
->02
02.00
краткая ретроспектива
и повторение
инвариант бесконечного цикла
порядок роста функции временной сложности $T(N)$: асимтотически точная граница
выбор констант $c_1$, $c_2$ и значения $N_0$ в соответствии с определением множества функций $\Theta(g(N))$
#include <queue>
#include <random>
double read_sensor() {
static double base = 20.0;
static std::mt19937 gen(42);
static std::normal_distribution<> noise(0.0, 2.0);
return (base += 0.5) + noise(gen);
}
int main() {
std::queue<double> window;
double cur_sum = 0.0;
const int WINDOW_SIZE = 5;
while (true) {
double val = read_sensor();
window.push(val);
cur_sum += val;
if (window.size() > WINDOW_SIZE) {
cur_sum -= window.front();
window.pop();
}
double avg = cur_sum / window.size();
}
}
скользящее среднее по потоку данных
- мониторинг температурного датчика процессора
- «сырой» сигнал сенсора состоит из двух частей: тренд постоянного нагрева и случайные флуктуации
- вычисляем среднее значение значение последних WINDOW_SIZE измерений методом скользящего окна за $\Theta(1)$
#include <queue>
#include <random>
double read_sensor() {
static double base = 20.0;
static std::mt19937 gen(42);
static std::normal_distribution<> noise(0.0, 2.0);
return (base += 0.5) + noise(gen);
}
int main() {
std::queue<double> window;
double cur_sum = 0.0;
const int WINDOW_SIZE = 5;
while (true) {
double val = read_sensor();
window.push(val);
cur_sum += val;
if (window.size() > WINDOW_SIZE) {
cur_sum -= window.front();
window.pop();
}
double avg = cur_sum / window.size();
}
}
имеет ли этот бесконечный цикл инвариант?
* клик по ответу покажет, верный ли он
-
да, и мы сможем его использовать
для обоснования его корректности -
нет, поскольку цикл не заканчивается,
и точку TRM достичь невозможно
инвариант бесконечного цикла
- фокус инварианта цикла смещается на обоснование частичной [промежуточной] корректности
- в конце каждой итерации система находится в согласованном состоянии [для внешнего контроля]
- защита от потенциального накопления ошибок
#include <queue>
#include <random>
double read_sensor() {
static double base = 20.0;
static std::mt19937 gen(42);
static std::normal_distribution<> noise(0.0, 2.0);
return (base += 0.5) + noise(gen);
}
int main() {
std::queue<double> window;
double cur_sum = 0.0;
const int WINDOW_SIZE = 5;
while (true) {
double val = read_sensor();
window.push(val);
cur_sum += val;
if (window.size() > WINDOW_SIZE) {
cur_sum -= window.front();
window.pop();
}
double avg = cur_sum / window.size();
}
}
утверждение 02.01
для любого $\mathrm{WINDOW\_SIZE} \geqslant 0$ верно, что в конце $i$-ой итерации цикла while выполняются два условия инварианта $P$:
$\mathrm{cur\_sum} = \sum \mathrm{window}$ и $\vert\mathrm{window}\vert\leqslant \mathrm{WINDOW\_SIZE}$
доказательство
обозначим $W = \mathrm{window}$ и $w = \mathrm{WINDOW\_SIZE}$
-
INIT — пустая очередь
и начальное значение суммы$W = \varnothing \Rightarrow \mathrm{cur\_sum} = 0$
$W = \varnothing \Rightarrow \vert\mathrm{W}\vert \leqslant w$ -
MNT —
перед $i$-ой
итерацией $P$ верен:.cpp: 17 $W = W \cup \{\mathrm{val}\}$
.cpp: 18 $\mathrm{cur\_sum} = \mathrm{cur\_sum} + \mathrm{val}$
.cpp: 20 $\vert W \vert > w \Rightarrow \mathrm{cur\_sum} - W.\mathrm{front}$
.cpp: 21 $\vert W \vert > w \Rightarrow W = W \setminus W.\mathrm{front}$
$\Rightarrow$ равенство суммы и размера окна восстанавливаются, а выполнение операции cur_sum / window.size() безопасно
void order_of_growth();
порядок роста функции — символ $\Theta$
применение определения для обоснования асимптотической точной границы
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
определение 01.02
$T(n)$ имеет тот же порядок роста, что и $g(n)$, то есть,
$T(n) = \Theta(g(n))$, если $T(n)$ принадлежит
множеству
$\Theta(g(n))=\{ T(n) \,\vert\, 0 \leqslant c_1g(n) \leqslant T(n) \leqslant c_2g(n) \}$
для некоторых $c_1$, $c_2 > 0$ и $\forall n \geqslant n_0$
ключевые свойства
- $T(n) = \Theta(g(n)) \Leftrightarrow T(n) \in \Theta(g(n))$
- $0 < \lim\limits_{n\to \infty} \frac{T(n)}{g(n)} < \infty \Rightarrow T(n) = \Theta(g(n))$
- $T(n)$, начиная с $n_0$, «зажата» между $c_1g(n)$ и $c_2g(n)$
утверждение 02.02
$T(n) = \dfrac{1}{2}n^2 - 3n = \Theta(n^2)$
найти $c_1, c_2, n_0 > 0$, что $c_1n^2 \leqslant T(n) \leqslant c_2n^2$ для всех $n>n_0$
доказательство
-
найдем $c_1$ и $n_0^{L}$, для которых
верно, что $c_1n^2 \leqslant T(n)$:$c_1n^2 \leqslant \dfrac{1}{2}n^2 - 3n \Leftrightarrow$
$c_1 \leqslant \dfrac{1}{2} - \dfrac{3}{n}$ - с учетом $c_1 > 0$ можем выбрать $n_0^L = 7 \Rightarrow c_1 \leqslant \dfrac{1}{14}$
-
найдем $c_2$ и $n_0^{U}$, для которых
верно, что $T(n) \leqslant c_2n^2$:$\dfrac{1}{2}n^2 - 3n \leqslant c_2n^2 \Leftrightarrow$
$c_2 \geqslant \dfrac{1}{2} - \dfrac{3}{n}$ - с учетом $c_2 > 0$ можем выбрать $n_0^U = 1 \Rightarrow c_2 \geqslant \dfrac{1}{2}$
ответ можем выбрать $n_0 = 7$, $c_1 = 1\,/\,14$ и $c_2 = 1\,/\,2$
void order_of_growth();
порядок роста функции — символ $\Theta$
применение определения для обоснования асимптотической точной границы
- повысить порядок при использовании $\Theta$ нельзя
- $T(n)= n+1 \neq \Theta(n^2)$
- понизить порядок при использовании $\Theta$ нельзя
- $T(n)= n^3 - 2n^2 + 1 \neq \Theta(n)$
02.01
асимптотические границы временной сложности
верхняя граница и символ $\mathrm{O}$
нижняя граница и символ $\Omega$
соотношение асимптотических границ
void upper_bound();
асимптотическая верхняя граница
определение и свойства символа $\mathrm{O}$
#include <iostream>
int main() {
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k <j; ++k) {
sum += i + j + k;
}
}
}
return 0;
}
определение 02.01
$T(n)$ ограничена сверху функцией $g(n)$, то есть, $T(n) = \mathrm{O}(g(n))$, если $T(n)$ принадлежит множеству функций
$\mathrm{O}(g(n))=\{ T(n) \,\vert\, 0 \leqslant T(n) \leqslant cg(n) \}$
для некоторых $c, n_0 > 0$ и для всех $n \geqslant n_0$
ключевые свойства
- $T(n) = \mathrm{O}(g(n)) \Leftrightarrow T(n) \in \mathrm{O}(g(n))$
- связь с пределом отношения: $\lim\limits_{n\to \infty} \frac{T(n)}{g(n)} < \infty \Rightarrow T(n) = \mathrm{O}(g(n))$
- график функции $T(n)$, начиная с $n_0$, находится ниже $cg(n)$
void upper_bound();
асимптотическая верхняя граница
определение и свойства символа $\mathrm{O}$
#include <iostream>
int main() {
int sum = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
for (int k = 0; k < j; ++k) {
sum += i + j + k;
}
}
}
return 0;
}
* клик по строчке кода покажет ее точную сложность
вычисление сложности
-
сложность цикла по k:
$\mathrm{C}1\cdot j = \Theta(1) \cdot j = \Theta(j)$
-
сложность цикла по j:
$X = \sum\limits_{j = 0}^{i-1}j\cdot \mathrm{C}1 = \frac{i(i-1)}{2}\cdot \mathrm{C}1 = \Theta(i^2)$
-
сложность цикла по i:
$Y = \sum\limits_{i = 0}^{n-1}\frac{i(i-1)}{2}\cdot \mathrm{C}1 = \frac{\mathrm{C}1(n-2)(n-1)n}{6} = \Theta(n^3)$
-
суммарная сложность:
$\begin{aligned} T(n) &= \Theta(n^3) + \Theta(1) = \Theta(n^3) \\ T(n) &= \mathrm{O}(n^3)\end{aligned}$
void upper_bound();
асимптотическая верхняя граница
определение и свойства символа $\mathrm{O}$
- повысить порядок при определении $\mathrm{O}$ можно
- $T(n)= 3n = \mathrm{O}(n^2)$, начиная с $n_0=3$ при $c=1$
- $g(n)$ как минимум того же порядка роста , что и $T(n)$
- $T(n)= 3n +2 = \mathrm{O}(n)$, начиная с $n_0=2$ при $c=4$
void lower_bound();
асимптотическая нижняя граница
определение и свойства символа $\Omega$
#include <vector>
void insertion_sort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
определение 02.02
$T(n)$ ограничена снизу $g(n)$, то есть,$T(n) = \Omega(g(n))$, если $T(n)$
принадлежит
множеству функций
$\Omega(g(n))=\{ T(n) \,\vert\, T(n) \geqslant cg(n) \geqslant 0 \}$
для некоторых $c, n_0 > 0$ и для всех $n \geqslant n_0$
ключевые свойства
- $T(n) = \Omega(g(n)) \Leftrightarrow T(n) \in \Omega(g(n))$
- связь с пределом отношения: $\lim\limits_{n\to \infty} \frac{T(n)}{g(n)} > 0 \Rightarrow T(n)=\Omega(g(n))$
- график функции $T(n)$, начиная с $n_0$, находится выше $cg(n)$
void lower_bound();
асимптотическая нижняя граница
определение и свойства символа $\Omega$
- понизить порядок при определении $\Omega$ можно
- $T(n)= n^2 = \Omega(n)$, где $n_0=3$ при $c=3$
- порядок роста $g(n)$ не больше чем у $T(n)$
- $T(n)= 2n^2-5n+4 = \Omega(n^2)$, где $n_0=2$ при $c=0.5$
какие из этих асимптотических соотношений верны для функций
$T_1(n) = n^{\log_4 8}$
$T_2(n) = \dfrac{\sqrt{n^3}}{\log_2 n}$
* клик по ответу покажет, верный ли он
- $T_1(n) = \mathrm{O}(T_2(n))$
- $T_1(n) = \Omega(T_2(n))$
- $T_2(n) = \mathrm{O}(T_1(n))$
- $T_2(n) = \Omega(T_1(n))$
02.02
абстрактный тип данных
абстрактный тип данных [ADT], структура данных
и общая модель ADT Контейнер
различные способы упорядочения объектов:
от линейного порядка до отношения смежности
непрерывное, связное, индексированное и гибридное размещение структуры данных в памяти
template<typename T> Container {...};
абстрактный тип данных
ADT Контейнер — общая модель хранения объектов и предоставления доступа к ним
template<typename T> class Container {
public:
Container();
Container(const Container& other);
Container(Container&& other) noexcept;
~Container();
Container& operator=(const Container& other);
Container& operator=(Container&& other) noexcept;
void clear();
void merge(const Container& other);
void intersect(const Container& other);
bool empty() const;
size_t size() const;
size_t capacity() const;
size_t count(const T& value) const;
bool contains(const T& value) const;
void insert(const T& value);
bool remove(const T& value);
bool comparable(const T& a, const T& b) const;
bool equal(const T& a, const T& b) const;
bool equivalent(const T& a, const T& b) const;
bool less(const T& a, const T& b) const;
bool less_or_equal(const T& a, const T& b) const;
Iterator lower_bound(const T& value);
Iterator upper_bound(const T& value);
bool sorted() const;
void sort();
Iterator find(const T& value);
ConstIterator find(const T& value) const;
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
private:
// скоро уточним
};
* код можно прокручивать
компоненты интерфейса контейнера
-
жизненный цикл контейнера
создание, копирование, перемещение, уничтожение, ...
-
наблюдатели
проверка пустоты, размер, вместимость, ...
-
модификаторы
вставка, удаление объектов, ...
-
доступ к объектам
поиск, изменение, итерация по содержимому, ...
-
взаимодействие с отношением порядка на объектах
равенство, эквивалентность, строгий и нестрогий линейный порядок, верхняя и нижняя граница, ...
void order_objects();
линейный порядок $\leqslant$
различные виды отношений порядка на множестве объектов
определение 02.03
отношение $\leqslant \,\,\subseteq X \times X$ на множестве объектов $X$ называется линейным порядком, если оно:
- рефлексивно: $x \leqslant x$
- антисимметрично: $(x \leqslant y, y \leqslant x) \Rightarrow x = y$
-
транзитивно:
$(x\leqslant y, y \leqslant z) \Rightarrow x \leqslant z$
- сильно связно: $\forall x, y \in X\colon x \leqslant y$ или $y \leqslant x$
сильная связность перекликается с теорией графов — линейный порядок также называют полным порядком
примеры линейных порядков
-
порядок на множестве чисел:
$... \leqslant -9 \leqslant ... \leqslant 1 \leqslant 2 \leqslant 3 \leqslant ...$
$1.2 \leqslant ... \leqslant 1.21 \leqslant 1.211 \leqslant 2.65 \leqslant ...$ -
порядок на множестве символов:
'A' $\leqslant$ 'B' $\leqslant$ 'C' $\leqslant \cdots \leqslant$ 'a' $\leqslant$ 'b' $\leqslant$ 'c' $\leqslant \cdots$
-
лексикографический порядок на сложных объектах:
$(a, b) \leqslant (c, d) \Leftrightarrow a \leqslant b$ или $a = b$, $c \leqslant d$
контейнер с явным или неявным упорядочением
void order_objects();
частичный порядок $\leqslant$
различные виды отношений порядка на множестве объектов
определение 02.04
отношение $\leqslant \,\,\subseteq X \times X$ на множестве объектов $X$ называется частичным порядком, если оно:
- рефлексивно: $x \leqslant x$
- антисимметрично: $(x \leqslant y, y \leqslant x) \Rightarrow x = y$
-
транзитивно:
$(x\leqslant y, y \leqslant z) \Rightarrow x \leqslant z$
в отличие от линейного, частичный порядок допускает наличие несравнимых объектов
ориентированный ациклический граф
void order_objects();
иерархия $\preccurlyeq$
различные виды отношений порядка на множестве объектов
определение 02.05
отношение $\preccurlyeq \,\,\subseteq X \times X$ на множестве объектов $X$ называется иерархией, если оно:
- рефлексивно: $x \preccurlyeq x$
- антисимметрично: $(x \preccurlyeq y, y \preccurlyeq x) \Rightarrow x = y$
-
транзитивно:
$(x\preccurlyeq y, y \preccurlyeq z) \Rightarrow x \preccurlyeq z$
- «унитарно»: $(x \preccurlyeq y, x \preccurlyeq z) \Rightarrow y \preccurlyeq z$ или $z \preccurlyeq y$
предки объекта также связаны отношением иерархии
int some_function() {
int a;
{
int b;
}
{
int c;
}
return a;
}
Контейнер с отношением родитель-потомок
void order_objects();
эквивалентность $\sim$
различные виды отношений порядка на множестве объектов
определение 02.06
отношение $\sim \,\,\subseteq X \times X$ на множестве объектов $X$ называется эквивалентностью, если оно:
- рефлексивно: $x \sim x$
- симметрично: $x \sim y \Rightarrow y \sim x$
-
транзитивно:
$(x \sim y, y \sim z) \Rightarrow x \sim z$
классы эквивалентности $[x] = \{y \in X\,\vert\, y \sim x\}$
объекты-представители
- при реализации каждый класс эквивалентности имеет выделенного объекта-представителя
- операции с объектами выполняются только через представителей классов эквивалентности
система непересекающихся множеств
void order_objects();
слабый порядок $\lesssim$
различные виды отношений порядка на множестве объектов
определение 02.07
отношение $\lesssim \,\,\subseteq X \times X$ на множестве объектов $X$ называется слабым порядком, если оно:
- рефлексивно: $x \lesssim x$
-
транзитивно:
$(x \lesssim y, y \lesssim z) \Rightarrow x \lesssim z$
- сильно связно: $\forall x, y \in X\colon x \lesssim y$ или $y \lesssim x$
слабый порядок уточняет отношение эквивалентности и упорядочивает классы эквивалентности
упорядоченные классы
- как упорядочиваются объекты внутри одного класса эквивалентности — определяется внутренней реализацией
- std::weak_ordering — это стандартный тип результата для оператора трехстороннего сравнения <=>
cтандартные контейнеры библиотеки C++
void order_objects();
смежность $\leftrightarrow$
различные виды отношений порядка на множестве объектов
определение 02.08
граф соответствует произвольному бинарному отношению $R \subseteq X \times X$ на некотором множестве объектов $X$:
- вершины графа — объекты из множества $X$
- ребра графа — факты связи объектов отношением $R$
представление графа определяется реализацией:
список ребер / список смежности / матрицы / ...
контейнер для представления графа
| R | S | T | C | U | реализация | |
|---|---|---|---|---|---|---|
| линейный порядок $\leqslant$ | ✅ | ❌ | ✅ | ✅ | — | линейный контейнер с явным / неявным упорядочением |
| частичный порядок $\leqslant$ | ✅ | ❌ | ✅ | ❌ | — | ориентированный ациклический граф |
| иерархия $\preccurlyeq$ | ✅ | ❌ | ✅ | ❌ | ✅ | контейнер с поддержкой связи родитель -> потомок |
| эквивалентность $\sim$ | ✅ | ✅ | ✅ | ❌ | — | система непересекающихся множеств |
| слабый порядок $\lesssim$ | ✅ | — | ✅ | ✅ | — | стандартные библиотечные контейнеры C++ |
| смежность $\leftrightarrow$ | ? | ? | ? | ? | ? | контейнер представления произвольного графа |
template<typename T> Container {...};
структура данных
внутреннее обеспечение контракта публичного интерфейса контейнера
template<typename T> class Container {
public:
Container();
Container(const Container& other);
Container(Container&& other) noexcept;
~Container();
Container& operator=(const Container& other);
Container& operator=(Container&& other) noexcept;
void clear();
void merge(const Container& other);
void intersect(const Container& other);
bool empty() const;
size_t size() const;
size_t capacity() const;
size_t count(const T& value) const;
bool contains(const T& value) const;
void insert(const T& value);
bool remove(const T& value);
bool comparable(const T& a, const T& b) const;
bool equal(const T& a, const T& b) const;
bool equivalent(const T& a, const T& b) const;
bool less(const T& a, const T& b) const;
bool less_or_equal(const T& a, const T& b) const;
Iterator lower_bound(const T& value);
Iterator upper_bound(const T& value);
bool sorted() const;
void sort();
Iterator find(const T& value);
ConstIterator find(const T& value) const;
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
private:
// скоро уточним
};
* код можно прокручивать
adt как контракт
абстрактный тип данных предоставляет контракт с пользователем о том, какие операции возможны — пользователь не знает детали внутренней реализации
структура данных обеспечивает контракт
- в private-области контейнера определяется реализация и основная логика работы — внутренняя структура данных обеспечивает выполнение контракта ADT
- один из ключевых факторов эффективности реализации — логика размещения структуры данных в памяти
void memory_layout();
структура данных
различные схемы размещения в памяти
template<typename T> class Container {
public:
Container();
Container(const Container& other);
Container(Container&& other) noexcept;
~Container();
Container& operator=(const Container& other);
Container& operator=(Container&& other) noexcept;
void clear();
void merge(const Container& other);
void intersect(const Container& other);
bool empty() const;
size_t size() const;
size_t capacity() const;
size_t count(const T& value) const;
bool contains(const T& value) const;
void insert(const T& value);
bool remove(const T& value);
bool comparable(const T& a, const T& b) const;
bool equal(const T& a, const T& b) const;
bool equivalent(const T& a, const T& b) const;
bool less(const T& a, const T& b) const;
bool less_or_equal(const T& a, const T& b) const;
Iterator lower_bound(const T& value);
Iterator upper_bound(const T& value);
bool sorted() const;
void sort();
Iterator find(const T& value);
ConstIterator find(const T& value) const;
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
private:
T* data_;
size_t count_;
size_t capacity_;
};
* код можно прокручивать
непрерывное размещение
- фиксированный или динамический массив — объекты располагаются в смежных ячейках памяти
- быстрый произвольный доступ — индексация через смещение указателя data[i] = *(data + i)
- необходимость выделения нового блока памяти и копирования при исчерпании емкости
void memory_layout();
структура данных
различные схемы размещения в памяти
template<typename T> class Container {
public:
Container();
Container(const Container& other);
Container(Container&& other) noexcept;
~Container();
Container& operator=(const Container& other);
Container& operator=(Container&& other) noexcept;
void clear();
void merge(const Container& other);
void intersect(const Container& other);
bool empty() const;
size_t size() const;
size_t capacity() const;
size_t count(const T& value) const;
bool contains(const T& value) const;
void insert(const T& value);
bool remove(const T& value);
bool comparable(const T& a, const T& b) const;
bool equal(const T& a, const T& b) const;
bool equivalent(const T& a, const T& b) const;
bool less(const T& a, const T& b) const;
bool less_or_equal(const T& a, const T& b) const;
Iterator lower_bound(const T& value);
Iterator upper_bound(const T& value);
bool sorted() const;
void sort();
Iterator find(const T& value);
ConstIterator find(const T& value) const;
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
private:
struct Node {
T value {};
Node* next = nullptr;
};
Node* head;
void insert_after(Node* prev, T val) {
if (!prev) return;
Node* new_node = new Node{val, prev->next};
prev->next = new_node;
}
};
* код можно прокручивать
связное размещение
- односвязный, двусвязный или циклический список
- быстрая вставка после известного узла списка
- медленный поиск или произвольный доступ
void memory_layout();
структура данных
различные схемы размещения в памяти
template<typename T> class Container {
public:
Container();
Container(const Container& other);
Container(Container&& other) noexcept;
~Container();
Container& operator=(const Container& other);
Container& operator=(Container&& other) noexcept;
void clear();
void merge(const Container& other);
void intersect(const Container& other);
bool empty() const;
size_t size() const;
size_t capacity() const;
size_t count(const T& value) const;
bool contains(const T& value) const;
void insert(const T& value);
bool remove(const T& value);
bool comparable(const T& a, const T& b) const;
bool equal(const T& a, const T& b) const;
bool equivalent(const T& a, const T& b) const;
bool less(const T& a, const T& b) const;
bool less_or_equal(const T& a, const T& b) const;
Iterator lower_bound(const T& value);
Iterator upper_bound(const T& value);
bool sorted() const;
void sort();
Iterator find(const T& value);
ConstIterator find(const T& value) const;
Iterator begin();
Iterator end();
ConstIterator begin() const;
ConstIterator end() const;
private:
struct HashNode {
T value;
size_t hash;
HashNode* next;
HashNode(const T& val, size_t h) :
value(val), hash(h), next(nullptr) {}
};
HashNode** buckets_;
size_t buckets_count_;
};
* код можно прокручивать
индексированное размещение
- массив указателей на непрерывные или связные области
- быстрая* вставка / поиск элементов
- падение производительности при большой вложенности
представление графа в виде списка смежности
представление матрицы — массив строчек / столбцов
представление матрицы — массив индексов
| размещение | доступ по индексу | вставка | поиск | упорядочение | примеры |
|---|---|---|---|---|---|
| непрерывное | $\mathrm{O}(1)$ ✅ | $\mathrm{O}(n)$ | $\mathrm{O}(n)$ | явное |
std::vectorstd::arraystd::string
|
| связное | $\mathrm{O}(n)$ | $\mathrm{O}(1)$* ✅ | $\mathrm{O}(n)$ | явное |
std::liststd::forward_list
|
| индексированное | нет | $\mathrm{O}(1)$* ✅ | $\mathrm{O}(1)$* ✅ | нет |
std::unordered_mapstd::unordered_set
|
* при наличии указателя на позицию вставки / ключа
02.03
ADT Связный список
односвязный, двусвязный и циклический список
особенности работы с динамической памятью:
понятие пула памяти и его применение
template<typename T> List {...};
ADT Связный список
основные варианты реализации списка
template<typename T> class List {
public:
// интерфейс списка
private:
struct Node {
T value { };
Node* next = nullptr;
};
Node* head;
void insert_after(Node* prev, T val) {
if (!prev) return;
Node* new_node = new Node{val, prev->next};
prev->next = new_node;
}
Node* find(T val) {...}
void remove(T val) {
if (!head) return;
if (head->value = val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* cur = head;
Node* prev = nullptr;
while (cur && cur->value != val) {
prev = cur;
cur = cur->next;
}
if(!cur) return;
prev->next = cur->next;
delete cur;
}
};
* код можно прокручивать
односвязный список
- быстрая вставка после известного узла списка
- однонаправленная итерация
- медленный поиск или произвольный доступ, что также делает все зависящие от поиска операции медленными
стандартный контейнер std::forward_list
template<typename T> List {...};
ADT Связный список
основные варианты реализации списка
template<typename T> class List {
public:
// интерфейс списка
private:
struct Node {
T value { };
Node* next = nullptr;
Node* prev = nullptr;
};
Node* head_;
Node* tail_;
void insert_after(Node* prev, T val) {...}
Node* find(T val) {...}
void remove(Node* node) {
if (!node) return;
if (node->prev) node->prev->next = node->next;
if (node->next) node->next->prev = node->prev;
delete node;
}
};
* код можно прокручивать
двусвязный список
- быстрая вставка после известного узла списка
- двусторонняя итерация
- быстрое удаление известного узла
- увеличенные затраты памяти на хранение узла
стандартный контейнер std::list
template<typename T> List {...};
ADT Связный список
основные варианты реализации списка
template<typename T> class List {
public:
// интерфейс списка
private:
struct Node {
T value { };
Node* next = nullptr;
Node* prev = nullptr;
};
Node* head;
void traverse() {
if (!head) return;
Node *cur = head;
do {
std::cout << cur->value << std::endl;
cur = cur->next;
} while (cur != head);
}
};
* код можно прокручивать
циклический список
- отсутствие nullptr-указателей
- обращаем внимание на обход списка и не используем потенциально бесконечный цикл while (!cur)
представления std::views::cycle и std::views::take
кэш-промахи?
- с теоретической точки зрения, вставка в список выполняется быстрее, чем вставка в массив
- с практической точки зрения, применения массива должно демонстрировать лучшую пространственную локальность
| размер контейнера | std::vector | std::list | соотношение времени |
|---|---|---|---|
| 1 000 | 0.088 мкс | 0.073 мкс | 1.2x 👌 |
| 10 000 | 0.343 мкс | 0.055 мкс | 6.2x 👍 |
| 100 000 | 3.062 мкс | 0.030 мкс | 100.6x 😎 |
| 1 000 000 | 28.599 мкс | 0.116 мкс | 246.8x 😲 |
| 10 000 000 | 325.166 мкс | 0.247 мкс | 1318.3x 🤩 |
* усредненное по 100 итерациям время вставки в одно и то же место массива / списка с дополнительными оптимизациями
какие «подводные» камни таит в себе выделение памяти с помощью new
это же просто new?
-
нарушение сильной гарантии исключений
[strong exception guarantee] -
накладные расходы
[блокировки, поиск в куче, выравнивание, ...]
template<typename T> class List {
public:
// конструктор копирования
List(const List& other) : head(nullptr) {
if (!other.head) return;
head = new Node(other.head->value);
Node* cur_s = other.head->next;
Node* cur_d = head;
while (cur_s) {
cur_d->next = new Node(cur_s->value);
cur_d = cur_d->next;
cur_s = cur_s->next;
}
}
private:
struct Node {
T value {};
Node* next = nullptr;
};
Node* head;
};
почему unique_ptr не решает проблемы new
умные указатели все решат?
-
рекурсивный вызов деструкторов ~Node()
[100 000 фреймов стека...]
-
«сырые» указатели Node* в сочетании с
итеративным деструктором ~List()[как в стандартном контейнере std::list]
#include <memory>
template<typename T> class List {
public:
// вставка в голову списка
void push_front(T val) {
auto n = std::make_unique<Node>(val);
n->next = std::move(head);
head = std::move(new_node);
}
// деструктор не нужен, правда?
private:
struct Node {
T value;
std::unique_ptr<Node> next;
Node(T val) : value(val), next(0) {}
};
std::unique_ptr<Node> head;
};
int main() {
List<int> lst;
for (int i = 0; i < 100'000; ++i) {
lst.push_front(i);
}
}
template<typename T> List {...};
ADT Связный список
внедрение зависимости: пул памяти
struct Node {
int value;
Node* next;
};
class NodePool {
public:
NodePool(size_t capacity)
: arena_(capacity), free_list_(nullptr) {
for (size_t i = 0; i < capacity; ++i) {
arena_[i].next = &arena_[i + 1];
}
arena_[capacity - 1].next = nullptr;
free_list_ = &arena_[0];
}
Node* allocate() {
if (!free_list_) throw std::bad_alloc();
Node* node = free_list_;
free_list_ = free_list_->next;
return node;
}
void deallocate(Node* node) {
node->next = free_list_;
free_list_ = node;
}
private:
std::vector<Node> arena_;
Node* free_list_;
};
class List {
public:
List(NodePool& p) : head_(nullptr), pool_(p) {}
void push_front(int val) {
Node* new_node = pool_.allocate();
new_node->value = val;
new_node->next = head_;
head_ = new_node;
}
void pop_front() {
if (!head_) return;
Node* temp = head_;
head_ = head_->next;
pool_.deallocate(temp);
}
~List() {
while (head_) {
pop_front();
}
}
private:
Node* head_;
NodePool& pool_;
};
* код можно прокручивать
пул памяти и список свободных
-
указатели next используются также для организации
связного списка свободных ячеек free_list_ - allocate() выделяет первую ячейку из списка свободных
- deallocate() возвращает ячейку в начало списка свободных
выделение и освобождение памяти выполняется за $\Theta(1)$
template<typename T> List {...};
ADT Связный список
внедрение зависимости: пул памяти
struct Node {
int value;
Node* next;
};
class NodePool {
public:
NodePool(size_t capacity)
: arena_(capacity), free_list_(nullptr) {
for (size_t i = 0; i < capacity; ++i) {
arena_[i].next = &arena_[i + 1];
}
arena_[capacity - 1].next = nullptr;
free_list_ = &arena_[0];
}
Node* allocate() {
if (!free_list_) throw std::bad_alloc();
Node* node = free_list_;
free_list_ = free_list_->next;
return node;
}
void deallocate(Node* node) {
node->next = free_list_;
free_list_ = node;
}
private:
std::vector<Node> arena_;
Node* free_list_;
};
class List {
public:
List(NodePool& p) : head_(nullptr), pool_(p) {}
void push_front(int val) {
Node* new_node = pool_.allocate();
new_node->value = val;
new_node->next = head_;
head_ = new_node;
}
void pop_front() {
if (!head_) return;
Node* temp = head_;
head_ = head_->next;
pool_.deallocate(temp);
}
~List() {
while (head_) {
pop_front();
}
}
private:
Node* head_;
NodePool& pool_;
};
int main() {
NodePool pool(1000);
List lst(pool);
lst.push_front(42);
lst.push_front(100);
lst.pop_front();
return 0;
}
* код можно прокручивать
// Лекция 02 завершена
// Резюме основных моментов
что мы
рассмотрели сегодня:
-
асимптотические границы
временной сложности алгоритмаверхняя и нижняя граница, символы $\mathrm{O}$ и $\Omega$
-
абстрактный тип данных
ADT Контейнер и его реализации, размещение
в памяти и упорядочивание объектов -
связный список и варианты его реализации
концепция пула памяти — области смежных ячеек
--> на следующей лекции
--> сложность рекурсивных алгоритмов
--> и парадигма «разделяй-и-властвуй»
};
return 0;
02->