CT Notes

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

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

Список операций, доступных для дерева поиска:

add(x)
find(x)
remove(x)

Список операций у бинарных деревьев аналогичен списку операций у куч.

Утверждение. Все работает за O(h), где h - высота дерева.

Доказательство:

add(x)

Алгоритм:
1. Стартуем алгоритм с корня
2. Если мы сейчас в вершине, сравниваем ключ, который в ней лежит и тот, что мы хотим добавить, в зависимости от этого идем в нужную сторону, чтобы выполнялось третье условие БДП.
3. Если мы покинули дерево, то создаем новую вершину в том месте, где дерево было покинуто, она и будет вершиной с новым значением, заметим что ни одно из правил не нарушилось.
find(x)

Алгоритм:
1. Стартуем алгоритм с корня
2. Если мы сейчас в вершине, сравниваем ключ, который в ней лежит и тот, что мы ищем, при равенстве мы победили и нашли искомый ключ, в противном случае идем в нужную сторону, пользуясь третьим условием БДП.
3. Если мы покинули дерево, то искомого ключа в дереве нет.
remove(x)

Алгоритм:
1. Используем алгоритм поиска, который я описал выше и находим вершину, которую нужно удалить
2. Тут есть несколько вариантов развития событий:
  1. Если вершина не имеет потомков, то просто удаляем ее
  2. Если у вершины один потомок, то мы просто вырезаем ее, а потомка привязываем к родителю вершины.
  3. Если у вершины есть оба потомка, то попытаемся свести этот случай к предыдущему, для этого найдем вершину с одним потомком, которого мы можем поменять местами с нашей, так, чтобы свойства БДП не нарушились. Оказывается такая вершина существует, мы можем спуститься в правое поддерево и в нем постоянно идти влево, что приведет нас к наименьшей вершине, большей исходной. Теперь просто меняем их местами и вырезаем желаемую вершину.

AVL-tree

AVL-дерево - бинарное дерево поиска, удовтлетворяющее свойству сбалансированности:

Для каждой вершины модуль разницы высот у поддеревьев ее сыновей не превышает 1(если сын отсутствует, считаем глубину его поддерева равной 0).

Мы поддерживаем h(x) --- количество вершин в поддереве, начинающегося с x.

h(v) = max(h(L),h(R)) + 1.

Лемма. В дереве высоты h хотя бы F_h вершин (h - ое число Фибоначчи)

Доказательство:

Пусть f(h) - min кол-во детей вершин в AVL c высотой h. Попытаемся вывести минимальное f(h), через предыдущие. У нас обязательно есть 1 корень, у него потомок глубиной хотя бы h-1, и второй, глубиной хотя бы h-2 из-за сбалансированности дерева. Получаем формулу, которая крайне похожа на формулу чисел Фибоначчи:

f(h) = f(h-1) + f(h-2) + 1

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

Балансировка AVL-tree

Предположим мы теоритически научились балансировать поддеревья для данной вершины не ломая сбалансированность потомков, как пользоваться такой суперсилой? Давайте при изменении структуры дерева, начнем из вершины, в которой это изменение произошло, будем подниматься до корня и балансировать вершину, которую проходим. Эта идея позволит вернуть сбалансированность дереву, потому что глубины остальных поддеревьев при добавлении/удалении не поменялись, а в тех вершинах, где что-то могло сломаться, мы все починили.

Ну а балансировать поддеревья сыновей фиксированной вершины нам поможет данный агрегат:

Wheel

Всего существует 4 типа поворотов, я подскажу вам как их проще всего запомнить, если вы хотите сделать глубже поддерево правого сына, то вам нужно перекинуть туда вершины с левого поддерева, то есть повернуть штурвал вправо - поворот правый, иначе влево - поворот левый. Но это только первый критерий, есть еще второй - размер вращения. Если вам надо переместить всего 2 вершины и поддеревья, то это вращение малое, если же 3 вершины и поддеревья, то большое.

Я буду показывать только левые повороты, так как левые просто симметричны. Вот схема малого поворота:

AVL Balance 1

Он подойдет вам если глубина поддерева R равна h-2. При том, даже если глубина Q будет h-3, все равно балансированность дерева не нарушиться. Проверку этого замечательного факта и схемы я оставлю читателю, тут нечего особо обсуждать.

В том случае, если глубина R внезапно оказалась равна h-3, нам придется использовать большой левый поворот:

AVL Balance 2

Тут на самом деле надо поразбирать вариантики, чему могут быть равный глубины поддеревьев Q и R, но проще заметить, что P и S всегда h-3, а мощности Q и R либо h-3, либо h-4, из чего уже становится понятно, что у полученных в результате поворота поддеревьев вершин a и b глубины действительно равны h-2. Ну а задание убедиться в том, что остальные свойства БДП выполняются при таком повороте я опять же оставлю читателю.

Последнее, что я хочу тут записать - как запомнить сами схемы поворота, попробуйте запомнить только перемещение вершин относительно друг друга, а перемещение поддеревьев восстановите автоматически.

Splay-tree

Концепция

Предположим, что у нас есть бинарное дерево поиска, и мы знаем, что запросы в нем происходят неравномерно, то есть есть вершины, к которым мы почти не обращаемся, или наоборот, есть вершины, обращений к которым очень много, так вот, splay дерево такие запросы будет обрабатывать быстрее, чем за $ O(\log n) $, но даже если запросы максимально случайные, скорость упадет всего лишь до $ O(\log n) $.

Идея

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

Операция splay

Сначала придумаем как реализовать основную операцию нашего дерева, поднимающую вершину в ее корень - splay. Вспомним про то, как мы поворачивали AVL-дерево, у нас было два типа поворотов - большие и маленькие, они нам позволяли балансировать правое и левое поддерево, теперь же нам надо проталкивать вершину в корень, заведем для этого 3 новых поворота, в чем нам поможет наш дядюшка Илон:

Elon

Zig - этот поворот мы будем использовать только в самом конце алгоритма, если вдруг, родитель вершины x и есть корень. Вот его схема:
Zigzig - этот поворот мы будем делать если у нашей вершины есть дедушка, и направление от дедушки к отцу и от отца к сыну одинаковые:
Zigzag - этот поворот мы делаем, если существует дедушка, и направление от него к отцу и отца к нашей вершине разные:

Заметим, что этих поворотов и условий для их использования достаточно, чтобы в любой ситуации однозначно понимать, какой из них надо использовать. Остается понять, почему амортизированно splay работает за $ O(\log n) $.

Доказательство скорости работы

В дальнейшем доказательстве я буду использовать такие обозначения: $ x $ - вершина, с которой мы работаем,

$ T_x $ - размер поддерева вершины $ x $

$p$ - предок $x$,

$g$ - предок $p$,

$w'(x)$ - вес после операции,

$w(x)$ - вес до операции.

Вспомним про то, как мы доказываем амортизированную оценку, нужен какой-то потенциал. Заведем функцию веса вершины $w(v) = \log(T_x)$, (на самом деле можно брать разные значения, что может помочь в доказательстве более лучших ограничений при специфичных обращениях к дереву). Тогда потенциалом $\Phi_i$ будет сумма весов всех вершин в дереве после действия $i$. Хорошо, попытаемся доказать такую верхнюю оценку на splay(x) - $3(w'(x) - w(x)) + 1$.

Zig

Эту операцию мы ограничим сверху как $w'(x) - w(x)+ 1$. За сколько операция работает? Очевидно за такое: $$\Phi_i - \Phi_{i-1} + 1 = w'(x) - w(x) + w'(p) - w(p) + 1$$ Заметим, что $w'(p) - w(p) \leq 0$. Тогда заменим и получим искомое:$$w'(x) - w(x) + w'(p) - w(p) + 1\leq w'(x) - w(x) + 1$$

Zigzig

Тут уже посложнее, мы попробуем ограничить как $3(w'(x) - w(x))$. Снова давайте преобразовывать: $$\Phi_i-\Phi_{i-1} + 2 = w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)+2$$ Тут понадобятся нетривиальные замены, поймем, что так как x стал корнем, а g был корнем, то верно $w'(x) = g(x)$, также так как x потомок p, то верно $w(x) < w(p)$, а после наоборот $w'(p) < w'(x)$. Применим: $$w'(x)+w'(p)+w'(g)-w(x)-w(p)-w(g)+2 \leq w'(x)+w'(g)-2w(x) + 2$$ Мы хотим доказать, что она меньше $3(w'(x) - w(x))$, то есть: $$w'(x)+w'(g)-2w(x) + 2\leq 3(w'(x) - w(x))\rightarrow w(x)+w'(g)-2w'(x)\leq -2$$ Хорошо, вспомним о том, как расскладывается формула веса вершины $$(w(x)-w'(x))+(w'(g)-w'(x))=(\log T_{x}-\log T_{x'})+(\log T_{g'} - \log T_{x'}) = \log \frac{T_{x}}{T_{x'}}+\log \frac{T_{g'}}{T_{x'}}$$ Заметим, что $T_x + T_{g'} = T_{x'} - 1$, А это значит, что: $$\frac{T_x}{T_{x'}}+\frac{T_{g'}}{T_{x'}} < 1$$По теореме о средних мы можем сказать, что: $$\frac{T_x}{T_{x'}} * \frac{T_{g'}}{T_{x'}} < \frac{1}{4} $$ Из чего уже следует искомое: $$\displaystyle\log\left({\frac{T_x}{T_{x'}}*\frac{T_{g'}}{T_{x'}} }\right) < -2$$

Zigzag

Все почти также, как в zigzig, сделаем все те же преобразования, что и там, за исключением $w'(p) < w'(x)$, получим такое: $$w'(p)+w'(g)-2w(x) + 2$$Ограничим это сверху как $2(w'(x)-w(x))$:$$w'(p)+w'(g)-2w(x) + 2\leq 2(w'(x)-w(x)) \rightarrow w'(p)+w'(g)-2w'(x)\leq -2$$Ну хорошо, а теперь снова посмотрим на структуру, полученную после поворота, и заметим, что $T_{p'} + T_{g'} = T_{x'} - 1$, а значит, делая аналогичные преобразования, что мы делали в zigzig, мы получим искомое.

Собираем вместе

Отлично, мы смогли найти ограничения на повороты, теперь нужно понять, какова граница времени работы всей операции splay. Огрубим оценку на zigzag, пусть он тоже работает за $3(w'(x) - w(x))$. Если теперь просто посчитать сумму работы все операций, то у нас выйдет телескопическая сумма, все члены которой сократятся, кроме первого и последнего и 1, если был zig:$$w(x_{кон}) - w(x_{нач}) + 1$$Заметим, что в конце алгоритма x - корень, а значит $w(x_{кон})=\log n$. Получаем общую сложность работы $O(\log n)$. Единственное, в чем splay дерево проигрывает AVL, это константа, потому что у splay она равна 3, а у AVL она равна 1, но обычно это нивелируется неравномерностью операций, так что зачастую splay дерево работает не хуже, а иногда даже лучше, чем AVL.

Остальные операции

Все операции внутри вызывают splay, так что работают за его скорость.

Split(x)

Чтобы сделать split(x), просто спускаемся до x, если находим, то делаем от него splay, иначе делаем splay от вершины, в которую придем. После выполнения splay отрезаем от корня нужного ребенка и получаем два дерева.

Merge(T1, T2)

Находим спуском наибольшую вершину правого дерева, делаем splay от нее, и привязываем к ней левое дерево.

Add(x)

Делаем split(x), полученные деревья становятся левым и правым поддеревом новой вершины с ключем x.

Remove(l, r)

Просто делаем 2 сплита для того чтобы в отдельное дерево вынести все значения с l по r, а далее смердживаем осавшиеся 2 куска.

Find(x)

Просто спускаемся до нужно вершины и делаем splay от нее.

Как это все писать

Написание splay-tree может доставить вам множество хлопот с правильным управлением ссылками(что уж там говорить, из нашей группы splay никто не сдал, пока мы не выпросили чекер у Первеева), а дебажить splay то еще занятие из-за его непостоянной структуры, так что лучше просто научиться его правильно писать. Для себя я вывел несколько советов :

Создайте функции add_edge и remove_edge, чтобы не заниматься изменением ссылок вручную. Именно здесь я допускал наибольшее количество ошибок. Ниже приведен код этих функций:

void add_edge(node *v, node *pr, bool is_left_edge) {
  if (pr) {
    if (is_left_edge) {
      pr->l = v;
    } else {
      pr->r = v;
    }
  }
  if (v) {
    v->p = pr;
  }
}

void remove_edge(node *v, node *pr, bool is_left_edge) {
  if (pr) {
    if (is_left_edge) {
      pr->l = nullptr;
    } else {
      pr->r = nullptr;
    }
  }
  if (v) {
    v->p = nullptr;
  }
}

Если немного присмотреться на zigzig и zigzag, то окажется, что это просто применение двух zig в некотором порядке, получается можно релизовать только zig, а в splay обмазаться зигами и получить упрощенную реализацию:

bool is_left_son(node *x) {
  if (x->p == nullptr) {
    return false;
  }
  return x->p->l == x;
}

void zig(node *v) {
  if (!v) {
    return;
  }
  auto pr = v->p;
  if (!pr) {
    return;
  }
  auto gr_pr = pr->p;
  bool is_left_v = is_left_son(v);
  bool is_left_pr = is_left_son(pr);
  node *b;
  if (is_left_v) {
    b = v->r;
  } else {
    b = v->l;
  }
  remove_edge(v, pr, is_left_v);
  remove_edge(pr, gr_pr, is_left_pr);
  remove_edge(b, v, !is_left_v);
  add_edge(v, gr_pr, is_left_pr);
  add_edge(pr, v, !is_left_v);
  add_edge(b, pr, is_left_v);
}

void splay(node *v) {
  if (!v) {
    return;
  }
  if (!v->p) {
    return;
  }
  if (!v->p->p) {
    zig(v);
    return;
  }
  if (is_left_son(v) == is_left_son(v->p)) {
    zig(v->p);
    zig(v);
    splay(v);
  } else {
    zig(v);
    zig(v);
    splay(v);
  }
}

Неявный ключ и массовые операции

Как и большинство других деревьев поиска, splay-дерево можно сделать по неявному ключу, для этого в вершине нужно хранить ее size, завести push, который мы будем применять до zig и при входе в вершину, а также update, который все нужные значения будет обновлять после zig.

Внешняя память

Мотивация: Мы жили в RAM - модели, которая считает и обращается к данным за O(1). Но по жизни скорость программы обычно упирается в скорость доступа к данным. В оперативке объем у нас примерно 10-100GB. Примерно 200 тактов, чтобы обратиться к ним. Скорость примерно 5-10 GB/s.

Есть HDD. Примерно 1/120 секунды, чтобы обратиться к нему. Разница колоссальная. Скорость примерно 100-200 MB/s.

П: Ну вы все, что вам Скаков рассказывал про HDD фигня. На самом деле там хомяк такой сидит он там крутится и арифметику считает. Вы ему говорите 2+3, хомяк там подумает-подумает и выдает ответ.

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

Модель внешней памяти

Что у нас есть:

$ M $ - размер RAM
$ N $ - размер внешней памяти(EXT MeM)
$ B $ - кусок размера B, который мы может перетащить из RAM в EXT MeM

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

Как мы будем оценивать?

Мы будем оценивать количество взаимодействий с памятью: IO complexity

Мы не будем думать о работе процессора. Грубо говоря наш процессор супер крутой, мы будем думать только о взаимодействии с памятью.

Input и Output у нас будут находится на диске.

Примеры

П: Есть крутой лектор: Максим Бабенко

Сумма массива

Дан массив n чисел. Хотим посчитать сумму. Очевидно асимптотика $\lceil \frac n B \rceil$. Эта константа дальше будет часто возникать, так что обозначим ее за $Scan(n)$.

Считаем, что 1 число - 1 ячейка памяти. Считаем $B$ чисел, потом следующие и так далее. И за $O(1)$ выводим на диск сумму.

Мерджим 2 массива

Дано 2 отсортированных массива длины n, m.

Будем мерджить массивы с помощью двух указателей, только теперь у нас вместо ячеек цельные блоки. Получается нам нужно загрузить все за $Scan(n)$ + $Scan(m)$, а потом выгрузить за $Scan(n + m)$. Суммарная сложность - $Scan(n) + Scan(m)$

Merge sort

Сделаем merge sort. Возьмем куски размера B, отсортируем и начнем делать merge. Это у нас будет работать отрабатывает за: $ O(\frac n B \log_2 \frac n B ) $

sort

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

Слить k массивов будет стоить $(k+1)B$ памяти, так как у нас оперативка ограничена M, то $ k \leq \frac M B$. Поэтому на самом деле у нас дерево не двоичное в сортировке, а k-ичное. Поэтому можно делать быстрее.

$ O(\frac n vB \log_{\frac M B} \frac n B)$, обозначим за $Sort(n)$

Стек во внешней памяти

Первая идея реализации:

Разбиваем стек на блоки размера B (размер блока для операций ввода-вывода).
Храним текущий активный блок в оперативной памяти.
Когда блок заполняется:
- Записываем его во внешнюю память.
- Создаем новый пустой блок в оперативной памяти.
Когда блок опустошается:
- Загружаем предыдущий блок из внешней памяти.

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

Вторая идея (улучшенная):

Поддерживаем два блока в оперативной памяти: текущий и буферный.
При заполнении 1.5 блоков (текущий полностью и половина буферного):
- Записываем текущий блок во внешнюю память.
- Переносим заполненную половину буферного блока в начало текущего.
- Очищаем буферный блок.
При опустошении до 0.5 блока:
- Загружаем предыдущий блок из внешней памяти в буферный.
- Переносим оставшиеся элементы текущего блока в конец буферного.
- Меняем местами текущий и буферный блоки.

Эта реализация обеспечивает амортизированную сложность $O(\frac{1}{B})$ операций ввода-вывода на одну операцию стека, так как каждый элемент участвует в операции ввода-вывода только один раз при записи блока и один раз при чтении.

Очередь

Будем делать очередь на циклическом буфере. Поддерживаем первый и последний блок. Буквально домашка № 5 по парадигмам.

List Ranking

Постановка задачи

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

Пример:

list

Несмотря на простоту задачи в RAM-моделе, во внешней памяти задача имеет нетривиальное решение. Из-за того что все данные лежат хаотично, мы не можем просто пройтись по списку, это может потребовать слишком много операций ввода-вывода.

Решение

Давайте дадим каждой вершинке вес. Пусть теперь у нас у каждой вершины есть вес $ v_i $ и ответ это сумма весов всех идущих после данной вершины в односвязном списке.

Посмотрим на 3 подряд идущие вершины. Позамечаем факты, чтобы ничего не поменялось в плане расстояние до конца, когда я удаляю вершину, я должен добавить в следующую после нее вес $ w_y $, а если наоборот добавляю, то должен присвоить вес новой $ r_z + w_z $ (см. рисунок)

list-ranking

Идея

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

Режим промежуточную задачу Join(n)

Есть 2 таблички, у нас так будут называться пары ключ - значение, лежащие подряд в памяти:

$$ k_1,v_1, k_2,v_2 , \dots, k_n, v_n $$

$$ l_1,u_1, l_2,u_2 , \dots, l_n, u_n $$

Причем $k_1, \dots , k_n$ - перестановка и $l_1, \dots , l_n$ - тоже перестановка.

Хочу получить на выходе табличку, стандартно там хранится пары ключ - пара значений из первой и второй таблицы, но можно делать почти все, что угодно, так что далее мы будем использовать $Join(n)$ и для других объединений таблиц, списков, у них даже не обязательно перестановки там будут, и может даже не по $n$, это все неважно.

Делать $Join(n)$ будем примерно так:

Отсортим обе таблицы за $Sort(n)$, а потом смерждим за $Scan(2n)$

Такая задача решается за $O(Sort(n))$.

Вернемся к решению

Заведем 2 таблицы и список:

i: $next$ - Текущий индекс - следующий индекс.
i: $v_i$ - Индекс - текущий вес.
$rem_i$ - список элементов, которые хотим удалить на текущем шаге.

Один рекурсивный шаг будем делать так:

Мы хотим удалить элементы, но из-за сложности изменения весов поставим себе ограничение, не удалять 2 вершины подряд. Будем добиваться этого следующим образом пройдемся по всем элементам, и добавим каждый в $rem_i$, с вероятность 50%. - $O(Scan(n))$
Теперь нужно убрать некоторые элементы так, чтобы не было цепочки из двух связанных элементов, удаленных на этом шаге, для этого мы сделаем Join для $rem_i$ и для $next$ (да, Join можно делать для списков, это примерно так же работает), и получим новый список, уже тех элементов, что надо убрать из списка $rem_i$. - $O(Join(n))$
Оба списка посортируем и пройдемся по ним блоками и удалим все совпадения. - $O(2Sort(n) + Scan(n))$
Теперь честно сменим веса и перепишем ссылки на следующие блоки для удаленных вершин, делается это все с помощью множества модифицированных Join, где они все выполняют функции фильтрации и суммирования, не особо сложно, не будем на этом останавливаться. - $O(Join(n))$
Отлично, мы готовы запустить следующий шаг, сделаем это, если у нас еще много неудаленных элементов, иначе просто насчитаем ответ на полученном массиве.
На этом шаге у нас уже есть ответ для существующих вершин, нужно вернуть удаленный, ну это не особо сложная задача, снова делаем много $Join(n)$, которые обратные операции делают. - $O(Join(n))$
Выходим из рекурсии с полученным ответом.

Возможно вам не очень понятно, что за $O(Join(n))$ мы делаем в 4 и 7 шаге, проще представить, что вы снова на ЕГЭ по информатике и у вас есть функция ВПР, но теперь она умеет думать, как объединять таблицы, например она может при отсутствии ключа, на его место 0 поставить, или что-то другое сделать. Так что вы просто делаете нужные объединения с правильными подсчетами внутри и получаете желанный результат.

Тут появляются вопросы нового уровня, например, за сколько это все добро работает? Ну, сначала надо понять, сколько вершин мы выбрасываем. Вероятность у вершины быть выбранной для выкидывания - $\frac{1}{4}$, потому что она равна вероятности у этой вершины быть выбранной, а у прошлой не быть выбранной. Значит выкидываться будет примерно $\frac{n}{4}$ за шаг, что на самом деле неважно, потому что на самом деле в итоговой формуле это все равно константа. Самая дорогая операция на шаге - $Sort(n)$, поэтому мы получаем что-то такое: $$T(n) = Sort(n) + T\left(\frac{3n}{4}\right)$$ Первеев все это разложил как: $$T(n) = Sort(n) * (1 + \frac{3}{4} + \frac{9}{16}\dots) = Sort(n)$$ Я ему верю.

Концепция

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

Отступление

На самом деле splay-дерево лучше чем декартово во всем, если мы будем сравнивать их как деревья поиска, так что если вы его знаете и декартач вам не нравится, или не заходит по времени, пишите splay.

Treap

Идея

Нам не важны приоритеты, которые мы даем ключам, поэтому давайте выдавать случайные приоритеты ключам. Дальше будет доказано, что в таком случае средняя глубина любой вершины будет $O(\log n)$.

Реализация

В декартовом дереве все держится на 2 операциях: split и merge, реализуем их, а потом через них все остальное.

Merge(T1, T2)

Merge - объединение двух деревьев в одно, на деревья наложены ограничения, любой ключ из левого дерева меньше, чем любой ключ из правого. Наша реализация накладывает на нас ограничение: в итоге должна получиться куча на приоритетах, значит мы точно знаем, корнем будет вершина с наибольшим приоритетом, а вторая должна быть смерджена с одним из потомков будущего корня. Сложность работы - $O(h)$.

Код

node *merge(node *l, node *r) {   
 if (l == nullptr) {    
  return r;  
 }  
 if (r == nullptr) {    
  return l;  
 }  
 if (l->y >= r->y) {   
  l->r = merge(l->r, r);     
  return l;  
 }  
 r->l = merge(l, r->l);  
 return r;
}

Split(T, x)

Split - разрез дерева на два по такому правилу: вершины с ключом, меньшим x окажутся в левом дереве, с большим - в правом(про равенство обычно не говорят, может быть там, где решит программист). Ну тут все совсем просто, начинаем алгоритм в корне, мы знаем, куда отойдет вершина, от которой мы запустились, а также знаем, куда отойдет поддерево одного из его сыновей, нужно просто запустить split от второго и привязать результат этого на место сына, от которого мы запустились. Сложность работы - $O(h)$.

Код

pair<node *, node *> split(node *root, long long x) {  
 if (root == nullptr) {  
   return {nullptr, nullptr};
 }    
 if (root->x <= x) {  
   auto res = split(root->r, x);    
   root->r = res.first;        
   return {root, res.second};  
 }  
 auto res = split(root->l, x);  
 root->l = res.second;  
 return {res.first, root}; 
}

Остальные операции

Кратко опишу логику остальных операций:

insert (в начало/конец) - merge
insert (в любое место) - split+split+merge+merge
remove (первый/последний) - split
remove (вырезание подотрезка ключей) - split+split+merge

Короче, удобно.

Математические свойства объекта

Единственность декартова дерева на заданном наборе пар ключ-значение

Начнем с более скучного факта: для заданного набора пар ключ-приоритет, в котором все ключи и приоритеты разные, декартово дерево строится единственным образом. Сам по себе факт бесполезный, но позволяет лучше понять структуру, с которой мы работаем.

Доказательство:

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

После того, как описанный выше алгоритм закончит работу, он построит декартово дерево на заданном ему наборе пар ключ-значение, так как у нас нигде не было выбора, то построенное дерево будет единственным.

Средняя глубина вершины

Давайте наконец докажем, что все операции в среднем работают за $O(\log n)$, доказав, что именно такая средняя глубина вершины в декартовом дереве.

Доказательство:

Заметим, что глубина вершины $v$ - кол-во вершин, которые являются предком вершины $v$. Тогда докажем следующую лемму.

Лемма. В декартовом дереве вершина $u$ - предок вершины $v$, если на отрезке $[min(u, v), max(u, v)]$ в массиве пар, отсортированном по ключам - у вершины $u$ максимальный приоритет.

Доказательство:

Предположим у вершины $u$ не максимальный приоритет, значит есть другая вершина на этом отрезке с большим приоритетом - $t$.
Вспомним прошлое доказательство единственности декартова дерева, в нем мы конструктивно его строили, если мы в том алгоритме остановимся на вершине $t$, что будет раньше, чем для вершин $u$ и $v$, потому что приоритет у $t$ меньше, то мы поймем, что $u$ и $v$ попадут в разные поддеревья, потому что находятся с разных сторон от $t$, а значит $u$ не может быть предком $v$. Докажем в обратную сторону:
1. Пусть у нас $u$ не предок вершины $v$, но имеет наибольший приоритет на отрезке $[min(u, v), max(u, v)]$, тогда точно есть единственная вершина $t$, для которой верно, что $u$ и $v$ ее потомки, и лежат в поддеревьях разных сыновей этой вершины.
2. Что тогда мы знаем про $t$:
  1. Она лежит между $u$ и $v$, потому что ее ключ между ключами $u$ и $v$.
  2. Ее приоритет больше, чем у $u$ и $v$.
  3. Получаем противоречие, есть вершина $t$ на отрезке $[min(u, v), max(u, v)]$ с большим приоритетом, чем у $u$.

Вернемся к основному доказательству, так как мы случайно брали приоритеты, то теперь мы знаем вероятность того, что вершина под номером $u$ - предок вершины под номером $v$ - $\frac{1}{|u - v| + 1}$. Подсчитаем эту вероятность для вершины под номером $k$: $$\sum\limits_{i=1}^{k-1}\frac{1}{k - i + 1}+\sum\limits_{j=k+1}^{n}\frac{1}{j - k + 1}\leq2*\sum\limits_{i=2}^n \frac{1}{i}=2\log{n}$$ Получили нужную нам асимптотику.

Неявное дд

Концепция

Мы хотим уметь делать то же самое, но на массиве значений, а то есть:

Быстро объединять массивы
Быстро вставлять в любое место массива подмассив
Быстро делить массив на 2 подмассива
Быстро делать массовые операции
Быстро находить по ссылке на элемент его индекс в массиве

Под быстро тут везде подразумевается асимптотика $O(\log n)$.

Идея

Заметим, что уже почти все готово, нужно просто как-то избавиться от дерева поиска по ключам, и мы получим нужную нам структуру данных. Также подметим, что из двух ключевых операций merge и split, на ключи опирается только split. Так давайте перепишем его так, чтобы теперь он переходил в сына не на основе ключа, который лежит в текущей вершине, а на основе размеров поддеревьев, и мы получим неявное дд. Неявным оно названо, потому что ключ теперь хранится неявно, и это на самом деле размер поддеревьев.

Измененный split

pair<node *, node *> split(node *root, long long k) {  
 if (!root) {  
   return {nullptr, nullptr};  
 }  
 if (size(root->l) >= k) {  
   auto res = split(root->l, k);    
   root->l = res.second;    
   upd_value(root);    
   return {res.first, root};  
 }  
 auto res = split(root->r, k - size(root->l) - 1);  
 root->r = res.first;  
 upd_value(root);  
 return {root, res.second};
}

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

int size(node *x) {  
 if (!x) {  
  return 0;  
 }  
 return x->size;
}

Ну а upd_value занимается тем, что пересчитывает все внутренние переменные через детей при изменении структуры дерева. Это крайне удобно и я очень советую писать именно так, потому что далее будет рассказано про отложенные операции и функцию push, проталкивающую их и очень легко допустить ошибку и объединить эти функции в одну, как, например, происходит в до, и получить потом TL на каком-то хорошем тесте.

void upd_value(node *x) {  
 if (!x) {    
  return;  
 }  
 x->size = 1 + size(x->l) + size(x->r);  
 // Другие обновления через сыновей
}

Ленивое распространение

Идешь в душ, делай push! - Неизвестный мудрец, 201* год

Иногда хочется делать грязь с отрезками, например делать прибавление на них, присвоение, считать сумму, максимум, минимум, реверсить и так далее. Но ручками делать это долго. На помощь придет лень, а точнее ленивое распространение. Пусть у нас есть какая-то операция на отрезке, причем ВАЖНО: для каждой вершины мы знаем все изменения в ней, если эту операцию применить. Тогда давайте пользоваться таким классным свойством, предположим у нас есть вершина дд, отвечающая за отрезок, на котором эту операцию хочется применить. Заведем флажок, который будет обозначать, что нам нужно применить операцию к поддереву этой вершины, а когда посетим эту вершину, сделаем в ней изменения, чтобы получить корректные данные для нее, а флажок протолкнем в детей. Также важно, чтобы эти изменения не обязывали высчитывать промежуточные результаты в вершинах, например, мы можем присвоить значение $x$ потомку не зная, какие изменения были в нем до, что позволяет нам проталкивать флаги нерекурсивно, а просто перезаписывая. Таким образом мы будем насчитывать реальные значения в вершинах мы будем только когда посещаем их и делаем push от них, а значит это не будет увеличивать сложность алгоритма.

Теперь чтобы в нашем неявном дд сделать прибавление на отрезке мы можем завести поле add, отвечающие за прибавление на отрезке у поддерева данной вершины, при запросе с помощью двух split'ов получать нужный отрезок, ручками менять поле у его корня и мерджить обратно. Очень удобно. Главное не забывать делать push всегда и везде. Вот его примерный код для сложения с подсчетом суммы на отрезке:

 void push(node *x) {  
  if (x == nullptr) {   
   return;  
  }
  if (x->add != 0) {
   x->sum += x->size * x->add;
   if (x->l) {
    x->l->add += x->add;
   }
   if (x->r) {
    x->r->add += x->add;
   }
   x->add = 0;
  }
  // Проталкивание других флагов
}

Персистентное дд

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

Завершение темы деревьев

Структуры данных для работы с числами

На этой лекции мы рассмотрим структуры данных, которые эффективно работают с числами в диапазоне до $ 2^w $, где w - это размер машинного слова (обычно 32 или 64 бита).

Основные операции

Мы хотим, чтобы наша структура поддерживала следующие операции:

add(x) - добавление элемента x
remove(x) - удаление элемента x
find(x) - поиск элемента x
next(x) - нахождение минимального y, такого что y > x
prev(x) - нахождение максимального y, такого что y < x

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

Мы научимся делать операции за O(w), а потом за O(log w)

Битовый бор (trie)

Мы будем хранить числа хитрым образом, используя структуру данных, называемую битовым бором или префиксным деревом (trie).

Принцип работы битового бора:

Представление чисел: Каждое число представляется в двоичной форме (добиваем ведущими нулями до размера w)
Структура дерева:
- Корень дерева представляет пустую строку.
- Каждый узел (кроме корня) соответствует одному биту (0 или 1).
- Путь от корня до листа представляет число в двоичной форме.
Хранение чисел:
- Число хранится как путь от корня до листа.
- Каждый уровень дерева соответствует позиции бита в числе.
Преимущества:
- Эффективное использование памяти для чисел с общими префиксами.
- Быстрый поиск, вставка и удаление (O(w), где w - длина числа в битах).
Операции:
- add(x): Добавляем путь для двоичного представления x.
- remove(x): Удаляем путь, соответствующий x.
- find(x): Проходим по пути, соответствующему x.
- next(x) и prev(x): Используем структуру дерева для эффективного поиска.

Пример:

trie

В данном случае мы считали, что числа не совпадают, но никто не мешает нам в листах хранить число --- количество чисел приходящих в этот лист.

Время O(w), Память O(nw).

Быстрый цифровой бор (x-fast trie)

X-fast trie - это усовершенствованная версия обычного битового бора, которая позволяет выполнять операции быстрее, за счет использования дополнительной памяти.

Как у нас работал next(x)?

Прочитать x (спуск) --- O(w)
Пойти направо (подъем + спуск в сына) --- O(w)
Идти до конца влево (спуск) --- O(w)

Мы можем это ускорить:

Основные идеи:

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

Благодаря этому мы умеем делать вторую и третью операцию у next за O(1), а первую за O(log w).

Операции:

Теперь наши операции делают еще:

find(x): O(log w)
- Используем двоичный поиск по уровням, чтобы найти наибольший существующий префикс x.
next(x) и prev(x): O(log w)
- Находим наибольший существующий префикс x.
- Используем указатели на листья для быстрого перехода к следующему/предыдущему элементу.

todo: описать функцию next_or_prev с лекции и в целом распиши поподробнее я не выкупил

add(x) и remove(x): O(w)
- Обновляем все уровни и соответствующие хеш-таблицы.

Преимущества:

Операции find, next и prev выполняются за O(log w) вместо O(w).
Сохраняет преимущества обычного бора в представлении чисел.

Недостатки:

Требует O(nw) памяти, что может быть значительно при больших n и w.
Операции вставки и удаления остаются O(w).

Сверхбыстрый цифровой бор (y-fast trie)

Y-fast trie - это дальнейшее улучшение x-fast trie, которое позволяет достичь лучшей производительности и эффективности использования памяти.

Основные идеи:

Разделение на блоки:
- Разбиваем все числа на блоки размером O(log w).
- Каждый блок представлен одним представителем
Использование сбалансированных деревьев:
- Внутри каждого блока используем сбалансированное двоичное дерево поиска (например, красно-черное дерево).
- Это позволяет эффективно управлять элементами внутри блока.
Двухуровневая структура:
- Верхний уровень: x-fast trie для репрезентативных элементов блоков.
- Нижний уровень: сбалансированные деревья для элементов внутри блоков.

Операции:

find(x): O(log w)
- Используем x-fast trie для нахождения нужного блока.
- Затем ищем элемент в сбалансированном дереве этого блока.
next(x) и prev(x): O(log w)
- Находим блок, содержащий x или следующий за ним.
- Используем сбалансированное дерево для точного поиска.
add(x) и remove(x): O(log w)
- Находим нужный блок.
- Обновляем сбалансированное дерево этого блока.
- При необходимости обновляем структуру блоков (разделение или слияние).

Преимущества:

Все основные операции выполняются за O(log w).
Значительно меньшее использование памяти по сравнению с x-fast trie: O(n) вместо O(nw).
Сохраняет эффективность для операций поиска и обновления.

Недостатки:

Более сложная реализация по сравнению с x-fast trie.
Необходимость поддержания баланса между блоками.

Сравнение с другими структурами:

Структура	Операции	Память
Битовый бор	O(w)	O(nw)
X-fast trie	O(log w) для find/next/prev, O(w) для add/remove	O(nw)
Y-fast trie	O(log w) для всех операций	O(n)

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

Дерево отрезков

Дерево отрезков (Segment Tree) — это структура данных, которая позволяет эффективно выполнять операции на отрезках массива. Основные операции, которые поддерживает дерево отрезков:

Обновление элемента массива за O(log n)
Вычисление функции (сумма, минимум, максимум и т.д.) на отрезке за O(log n)

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

RMQ - задача поиска минимума на отрезках

RSQ - задача поиска суммы на отрезках

Структура дерева отрезков

Дерево отрезков представляет собой бинарное дерево, где:

Корень дерева соответствует всему массиву [0, n-1]
Каждый узел соответствует некоторому отрезку [l, r]
Листья дерева соответствуют отдельным элементам массива.
Каждый внутренний узел имеет двух потомков: левый соответствует отрезку [l, mid], правый — отрезку [mid+1, r], где mid = (l + r) / 2

Построение дерева отрезков

Построение дерева отрезков выполняется рекурсивно:

// Массив для хранения дерева отрезков
int tree[4*MAXN];

// Функция построения дерева
void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] + tree[v*2+1]; // Для суммы на отрезке
    }
}

Именно данная функция вам поможет, как она устроена. Наше дерево занимает O(n) памяти.

Пример ДО на суммы:

segment-tree

Запрос на отрезке

// Функция запроса суммы на отрезке [l, r]
int sum(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return tree[v];
    }
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm))
         + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

Мне эта реализация не нравится, потом перепишу.

Обновление элемента

// Функция обновления элемента
void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        tree[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        tree[v] = tree[v*2] + tree[v*2+1];
    }
}

Фанфакты про дерева отрезков

Любой отрезок по l,r можно разбить на 2*log n вершин.
- Доказательство аналогично пункту 2.
Функция get делает не более 4*log n рекурсивных вызовов
- Докажем по индукции по уровням отрезков. Корень очевидно. Давайте докажем, что на каждом слое мы делаем не больше 4 уровней.
- База очевидна. В корне 1 вызов.
- ИП: На текущем уровне есть 4 вершины и докажем, что из них вызовется не более 4 вершин. Посмотрим на границы(потому что вершины слева и справа от наших границ не запустятся и то, что между ними тоже не запустится). Я могу запуститься вниз максимум только от 2 из них. Откуда и правда побеждаем. (В данном случае мы "запускаем" максимум 4 снизу)

Итого вот такая вкусная структура данных.

Lazy Операции в дереве отрезков

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

Идея

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

Пример реалиации

Пример реализации lazy операций в дереве отрезков для вычисления суммы на отрезках:

// Массив для хранения дерева отрезков
int tree[4*MAXN];
// Массив для хранения ленивых операций
int lazy[4*MAXN];

// Функция построения дерева
void build(int a[], int v, int tl, int tr) {
    lazy[v] = 0; // Инициализация ленивой операции
    if (tl == tr) {
        tree[v] = a[tl];
    } else {
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, v*2+1, tm+1, tr);
        tree[v] = tree[v*2] + tree[v*2+1]; // Для суммы на отрезке
    }
}

// Функция ленивого обновления
void apply_lazy(int v, int tl, int tr) {
    if (lazy[v] != 0) {
        tree[v] += (tr - tl + 1) * lazy[v]; // Обновление значения в узле
        if (tl != tr) {
            lazy[v*2] += lazy[v]; // Применение ленивой операции к левому потомку
            lazy[v*2+1] += lazy[v]; // Применение ленивой операции к правому потомку
        }
        lazy[v] = 0; // Сброс ленивой операции
    }
}

// Функция запроса суммы на отрезке
int sum(int v, int tl, int tr, int l, int r) {
    apply_lazy(v, tl, tr); // Применение ленивой операции
    if (l > r)
        return 0;
    if (l == tl && r == tr)
        return tree[v];
    int tm = (tl + tr) / 2;
    return sum(v*2, tl, tm, l, min(r, tm)) + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

// Функция обновления элементов на отрезке
void update(int v, int tl, int tr, int l, int r, int val) {
    apply_lazy(v, tl, tr); // Применение ленивой операции
    if (l > r)
        return;
    if (l == tl && r == tr) {
        lazy[v] += val; // Обновление ленивой операции
    } else {
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), val);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, val);
        tree[v] = tree[v*2] + tree[v*2+1]; // Обновление значения в узле
    }
}

Очевидно, что мы можем делать и другие lazy операции.

Задача

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

Пусть у нас пока все координаты ограничены справа какой-то константой C. В каждой точке прямой нам интересно сколько она покрывает прямоугольников. С помошью сканлайна (сканирующей прямой) мы умеем такое делать. А теперь прикрутим ДО с массовыми(ленивыми) операциями!!! И все задача схлопнулась до C * n + m * log m, где m - количество точек.

При этом меня интересует только границы прямоугольника. Поэтому на самом деле я могу идти только по нужным мне прямым, оптимизируя мое время до n log n +n log n+ m * log m. Тадам!!!

Но если есть константа. Так что надо оптимизировать. Но для этого нам надо сжимать декартовы координаты.

Персистентность

Мотивация

Мы хотим откатываться в прошлые состояния.

Виды персистентности

Частичная - можем изменять только последнюю версию, но читать любое прошлое состояние. Это компромисс между гибкостью и простотой реализации. Примеры: хранение истории изменений в текстовом редакторе, "undo/redo".
Полная - можем изменять любое прошлое состояние, при этом изменения создают новую версию, не влияя на исходное состояние. Это наиболее гибкий подход, позволяющий исследовать различные ветви развития данных.
Конфлюентная - полная персистентность с возможностью объединять различные версии, порождая новые. Этот вид персистентности является наиболее сложным в реализации, но открывает интересные возможности для анализа и синтеза исторических данных. Похоже на ветки в системах контроля версий (Git).

Учимся в персистентность

Персистентный стек

Пусть у нас стек — это односвязный список. В персистентной версии, каждый push создаёт новую ноду односвязного списка, разделяя часть структуры с предыдущими версиями. Таким образом, у нас есть один большой-стек дерево, и масив "указателей" на вершины каждой из версий

Реализация операции push:

Операция push(value, stack) создает новый элемент (ноду) списка, в котором:

value - значение, которое кладется на стек.
next - указатель на предыдущую версию стека stack.

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

Реализация операции pop:

Операция pop(stack) возвращает новую версию стека, полученную путем удаления первого элемента из списка stack. Предыдущая версия stack остается неизменной. pop также выполняется за O(1), так как просто возвращает указатель на следующий элемент в списке и ставит указатель в массиве версий на эту вершину

Персистентная очередь

2 персистентных стека. Версия нашей очереди характеризуется версиями 2-ух стеков. Но проблема, когда перекладываем: делая push и pop к одной версии мы каждый раз будем тратить O(n) времени на перекладку. То есть мы проигрываем в асимптотике. (частичная персистентность бы тут прокатила)

Амортизированные оценки ломаются.

Персистентный массив

Fat nodes

Каждый узел (node) структуры данных содержит историю изменений своих полей. Поиск нужной версии поля осуществляется по временной метке. Этот подход может потребовать значительного объема памяти для хранения истории.

В данном случае получилось, что мы реализовали частичную персистентность

Сдлеаем полностью персистентный массив, для этого научимс делать персистентное ДО

Персистентное ДО

Умеем минимум на отрзке и изменять значение в точке.

Применим технику Path Coping.

Общая идея Path Copying:

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

Update имеет сложность O(log n), где n - размер массива, так как он проходит только по одному пути в дереве. build имеет сложность O(n).

Память: В худшем случае, при каждом обновлении создается O(log n) новых узлов. Поэтому требуется O(m log n + n) памяти для хранения m версий дерева.

Массовые операции пишутся тоже также.

Теперь понятно, как делать перс массив.

Персистентный Декартач.

Делаем его так же, конкретнее читайте здесь.

Откаты

Хотим делать операцию: забудь про последние k операций, вернись в реальность.

Обычно просто храним стек с изменениями и всё

Деревья.

Деревья храним 2-умя образами:

Храним родителей.
Храним детей.

LCA

LCA(u,v) - Lowest Common Ancestor - это узел w, который является предком и u, и v, и находится на максимальной глубине в дереве. Другими словами, w находится ближе всего к u и v среди всех общих предков.

Более простая задача.

Давайте решим сначала более простую задачу. Я хочу понимать является ли u предком v.

У этого есть очевидное тупое решение, но мы люди не тупые => пишем умное.

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

easy-lca

Ура, мы теперь умеем решать задачу LCA за линию. Будем поднимать одну вершину наверх, пока не выполнится описанное выше условие.

Двоичные подъемы.

Двоичное поднятие (подъемы) (Binary Lifting) (O(log n) времени на запрос):

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

Предварительно вычисляется таблица up[i][node], где up[i][node] — предок узла node на расстоянии 2ⁱ. Как такое считать?
- up[0][v] = pv
- up[k][v] = up[k-1][up[k-1][v]]
Во время запроса LCA используются двоичные представления расстояний, чтобы быстро "поднимать" узлы.
Общая идея та же, что и в подходе с уровнями, но с более быстрыми операциями подъема. Этот метод отлично подходит для множества запросов LCA.

// n - высота дерева
for k = log n...0:, n
    pu = up[k][u]
    if(!isParent(pu, v)):
        u = pu

Препроцессинг	Запрос
O(n log n)	O(log n)

Эйлеров обход

Пронумеруем вершины. Запустим dfs. Каждый раз, когда мы заходим в вершину, выписываем ее номер. У каждой вершины посчитаю редом глубину.

Общая идея:

Для узлов u и v, найти их индексы первого вхождения в последовательности Эйлерова обхода (first[u] и first[v]).
Найти узел с минимальным уровнем в диапазоне [first[u], first[v]] (или [first[v], first[u]], если first[v] < first[u]) в массиве уровней. Этот узел является LCA(u, v).

Это следует из пары фактом про этот отрезкок.

На отрезке есть LCA.
У LCA min глубина.
Нет других вершин с min глубиной.

Надо научиться считать минимум на отрезке. Например с помощью ДО.

Итого:

Препроцессинг	Запрос
O(n)	O(log n)

Sparse Table.

st[k][i] = min на [i, i + 2^i)

Оно будет считаться примерно так:

st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])

Итого, искав так минус мы для LCA получаем вот такой результат:

Препроцессинг	Запрос
O(n log n)	O(1)

Алгоритм Фарах-Колтон и Бендор

Разобьем на блоки размера B. Ищем минимум на целых блоках. и на краешках.

Для каждого блока считаем префиксные и суффиксные минимумы.

FKB

Дальше идет грязь. Каждый блок у нас выглядит как массив из +-1, например так:

FKB

И теперь предподсчитаем все такие массивы из +-1. Это будет работать за 2^B B^3. Можно сделать O(n).

Все это один большой кеш мисс.

LA (Level Ancestor)

Есть дерево. Есть запросы LA(v,k) - предок v на уровне k. Уровни индексируются снизу вверх

Первое очевидное решение это двоичные подъемы.

Препроцессинг	Запрос
O(n log n)	O(log n)

Long-Path Decompostion

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

Пример:

LPD

Препроцессинг	Запрос
O(n)	O(sqrt n)

Ladder Decompostion

Возьмем LPD, но увеличим высоту пути в 2 раза. Тадам

Препроцессинг	Запрос
O(n)	O(log n)

Ladder + Двоичные

Тут все очевидно

Препроцессинг	Запрос
O(n log n)	O(1)

Micro-Macro tree

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

HLD

То же самое, что и Long -Path, только теперь по весу вершины (количеству вершин в поддереве).

Link Cut

link(u, v) - u становится сыном v, причем u корень.
cut(u, v) - отрезать ребро.
change(v, x) - поменять на вершине значение на x.
min(u, v) - минимум на пути из u в v

Как все будет работать?

Некоторые ребра выделенные. У каждой вершины не более одного выделенного ребра в сына.

Введем операцию expose(v): Выделить все ребра от v до корня. И давайте для каждого выделенного пути хранить splay дерево.

Как только научимся делать данную операцию, покажем как через нее поулчить другие:

Изначально все веришны одиночные и в каждой веришне свое splay дерево

expose

void expose(v){
    splay(v);
    while(v != root){
        u = v.parenth;
        splay(u);
        r = u.right;
        r.pathparent = u;
        отрезать поддерево r;
        u.right = v;
        v.pathparenth = null;
        v =u; 
    }   
}

То есть поднмаемся сверух вниз, отрезаем splay дерево, если надо, иначе поднимаемся выше и соединяем нужные splay

Использование expose для операций

link(u, v) — делаем expose(u), expose(v), затем присоединяем (u) к (v) как ребёнка.
cut(u) — делаем expose(u), отрезаем ребро между (u) и его родителем.
change(v, x) — делаем expose(v), обновляем значение в вершине (v) (корне splay-дерева).
min(u, v) — делаем expose(u), затем expose(v), теперь путь (u \to v) представлен в splay-дереве, на котором можно за (O(\log n)) получить минимум.

Важные моменты

Каждый splay-узел хранит агрегированную информацию о поддереве (например, минимум).
При splay-поворотах агрегаты обновляются.
pathparent — ссылка на родителя вне splay-дерева (в исходном дереве).
Вся работа со структурами происходит через splay-операции.

C++

Информация о курсе:

Поток - y2024
Группы М3138 - М3139
Преподаватель -- Иван Сорокин

Введение в ассемблер

Мотивация.

На кой мы изучаем ассемблер и работу процессора в курсе по C++? А вот тому есть сразу несколько причин:

Когда мы будем говорить про языковые конструкции, мы обсудим не только то, как они работают, но ещё и почему именно так. Почему, например, лямбды без списка захвата приводятся к указателю на функцию, а со списком — нет? Без изучения основ архитектуры компьютера, мы не сможем ответить на этот вопрос, а с этим изучением просто не сможем представить себе, как может быть иначе.
Есть более практический аспект: если вы что-то желаете ускорить, то высокоуровневые оптимизации (убрать ненужное действие, не считать что-то дважды) — это легко, а более низкоуровневые вообще нельзя сделать без знаний того, как внутри компьютер работает.
Ещё основы архитектуры компьютера пригодятся при отладке. Если программа работает не так, то для понимания, где же именно ошибка, нам требуется понимать, что внутри процессора происходит.
И наконец есть более философская полезность: если вы чем-то пользуетесь, то чем лучше вы разбираетесь, как оно работает, тем грамотнее можете этим пользоваться. То же самое с библиотеками, например (если библиотека что-то умеет, а вы не знаете об этом, вы начинаете городить костыли). Например, в x86 есть специальная инструкция с длинной арифметикой, и лучше бы писать такой код, чтобы компилятор догадался пользоваться ей.

Базовое представление об устройстве оперативной памяти.

В нашем курсе мы построим некоторую простую модель компьютера, а потом будет её изучать и уточнять по необходимости. В нашей простой модели оперативная память — массив чисел в диапазоне $[0:255]$. Вы умеете обращаться к этому массиву по индексу. Этот индекс называется адресом в памяти. Обращаться к конкретному биту вы не умеете, и притом даже не знаете, какой бит у числа в начале, а какой — в конце.

Как в этой модели исполняется программа? Следующим образом: у процессора есть регистр IP (instruction pointer), где записан адрес той инструкции, которую надо исполнять. При её исполнении значение в регистре увеличивается, тем самым начиная указывать на следующую инструкцию.

Ассемблер.

Помимо регистра IP, процессор имеет ещё 8 регистров, которые, в отличие от IP являются регистрами общего назначения (т.е. пользоваться ими вы можете как вам хочется). Эти регистры имеют название... Стоп, а зачем регистрам название? А потому что вам иногда надо прописывать процессорные инструкции руками, а запоминать последовательности байтов вы не хотите. И для этого были придуманы системы человеко-читаемых мнемоник, называемых ассемблером. При этом мнемоники различаются в зависимости от инструмента, которым вы пользуетесь, а не только в зависимости от системы. Впрочем, на одной архитектуре мнемоники в любом случае достаточно схожи.

Полезные инструменты.

Чтобы увидеть, во что ваш компилятор превращает ваш код, пишите g++ -S -masm=intel ..., после чего вам создадут .s файл с ассемблерными командами. Или можно использовать https://godbolt.org, куда можно запихнуть разные компиляторы, параметры оптимизации и прочее, и сразу увидеть результат (причём понятнее, чем в g++). Ещё, кстати, на https://godbolt.org можно навести на команду и узнать информацию по ней. Если нужно больше информации об ассемблерной инструкции — зайдите на https://felixcloutier.com/x86/.

Регистры.

Итак, помимо регистра IP, процессор имеет ещё 8 регистров, которые, в отличие от IP являются регистрами общего назначения (т.е. пользоваться ими вы можете как вам хочется). Эти регистры имеют название AX, CX, DX, BX, SP, BP, SI, DI. Каждый из них имеет 16 битную разрядность, а последние 4 ещё и некий особый смысл, к которому скоро перейдём. Помимо них также есть следующее:

8-битные версии регистров: AL, AH, BL, BH, CL, CH, DL, DH, SPL, BPL, DIL, SIL. Для регистров *X его старшие 8 бит называются *H, а младшие — *L. У оставшихся четырёх есть только младшие, получаемые дописыванием L к названию регистра.
32-битные версии регистров (since 1985): EAX, EBX, ..., EDI. (Приставка "E" обозначает "extended".) Оригинальные 16-битные регистры являются младшей частью расширенных.
64-битные версии регистров (since 2003): RAX, RBX, ..., RDI. (Приставка "R" обозначает "re-extended".) "Расширенные" 32-битные регистры являются младшей частью пере-расширенных.
Дополнительный набор регистров (x86-64): R8, R9, ..., R15, R8D, R9D, ..., R15D, R8W, R9W, ..., R15W, R8B, R9B, ..., R15B. Регистры R* имеют 64-битную ширину, R*D (от слова "dword") — младшие 32 бита соответствующего регистра, R*W (от слова "word") — младшие 16, R*B (от слова "byte") — младшие 8.

Схема устройства регистров

Команда `mov`.

mov dst, src является простым присваиванием dst = src. В качестве её аргументов могут выступать регистры, константы или даже места в памяти. По поводу последнего: если вы хотите положить в регистр AX число десять, это пишется так: mov AX, 10, а если значение в десятой ячейке памяти, то адрес берётся в квадратные скобки: mov AX, [10]. Также в квадратные скобки можно брать регистр.

Все эти разные типы аргументов команды mov на самом деле даже по-разному кодируются. Как пример, присваивание числа в регистр и регистра в регистр занимают 2 и 5 байтов соответственно:

89 C2         		mov		edx, eax	; EDX = EAX
B8 05 00 00 00		mov		eax, 5		; EAX = 5

Некоторые сочетания закодировать нельзя никак (например, mov [AX], [BX]). А если детальнее, то возможны вот такие комбинации регистров (reg) и чисел (imm):

mov reg, reg
mov reg, imm
mov reg, [reg]
mov reg, [imm]
mov [reg], reg
mov [imm], reg
mov [reg], imm
mov [imm], imm

Возникает вопрос. Регистр AX шестнадцати-битный, а адрес указывает на байт. Значит при выполнении команды mov нужно откуда-то взять ещё 8 бит. А вот читается не только тот адрес, который запросили, но ещё и следующий. Но какой из прочитанных байт старший, а какой — младший? В разных архитектурах возможны разные варианты.

Если значения в меньшем адресе являются младшими разрядами, то это называется little-endian.
Если значения в большем адресе являются младшими разрядами, то это называется big-endian.

Пример: Если в ячейке с номером 100 записан байт 0x6C, а с номером 101 — 0xAA, то в LE при чтении ячейки [100] мы получим число 0xAA6C, а в BE — 0x6CAA.

В x86 используется только little-endian.

Команды арифметики.

Базовые бинарные операции.

Процессор умеет выполнять базовые бинарные операции, которые в ассемблере называются add, sub, and, or, xor. Все они работают как комбинация операции и присваивания (т.е. соответственно +=, -=, &=, |=, ^=). Совершать операции можно только с числами одинакового размера (как и с mov). Для бинарных операций возможны такие комбинации регистров и чисел, как и для mov (см. выше).

Унарные операции.

Простые унарные операции inc, dec, not, neg также работают как операция с присваиванием (то есть соответственно, x = x + 1, x = x - 1, x = ~x, x = -x). Понятно, что в случае, когда мы оперируем с ячейками памяти, надо явно уточнить, с числами какого размера производится операция. В ассемблере это пишется, например, так inc byte [addr]. byte подразумевает 8 бит. Вместо него можно написать word, dword или qword, подразумевая соответственно 2, 4 и 8 байтов.

Умножение и деление.

Умножение принимает один аргумент, умножая его на регистр AL/AX/EAX/RAX. Результат умножения занимает вдвое больше знаков, чем аргумент и записывается либо в регистр AX (для 8-битного), либо в пары регистров DX:AX, EDX:EAX, RDX:RAX (для 16-, 32- и 64-битного соответственно). DX — старшая половина разрядов.

Несложно заметить, что в отличие от сложения и вычитания, умножение и деление разное для знаковых и беззнаковых чисел. Поэтому существуют два разных умножения (mul и imul) и два разных деления (div и idiv). Первое для беззнаковых чисел, второе — для знаковых.

Деление работает схожим образом. Оно принимает делимое из AX/DX:AX/EDX:EAX/RDX:RAX, делитель как аргумент, а частное возвращает в регистр AL/AX/EAX/RAX. Но также деление возвращает остаток, и его оно возвращает в AH/DX/EDX/RDX.

Вопрос: как поделить друг на друга числа одинакового размера? Ну, нужно преобразовать, например, 16-битное число в 32-битное. В случае, если числа беззнаковые, надо просто обнулить DX (обычно регистр обнуляется при помощи xor DX, DX, потому что эта инструкция занимает меньше памяти, нежели mov DX, 0). Те, кто знают, как работает дополнение до 2, также знают, что нужно делать в знаковом случае. Нужно заполнить DX знаковым битом AX. Для этого в x86 есть специальная инструкция cwd. Для того чтобы сделать то же самое с EDX и RDX, есть инструкции cdq и cqo соответственно.

Хорошо, про деление мы знаем уже почти всё, кроме того, что будет, если мы поделим на 0. Или если результат в нужные регистры не поместится. Обе эти ситуации приводят к системным прерываниям, которые работают следующим образом: процессор имеет массив IDTR (Interrupt Descriptor Table Register), в котором для каждого типа прерывания сказано, что с ним делать. Этот массив при запуске подготавливает операционная система.

Сдвиги.

Ещё в x86 есть

SHL/SAL — сдвиг влево
SHR — логический сдвиг вправо (оставляет на пустых местах нули)
SAR — арифметический сдвиг справа (на пустые места пихает знаковый бит).

В C++ для беззнаковых используется SHL и SHR, а для знаковых — SAL и SAR.

Оптимизации компилятора.

Давайте забьём в https://godbolt.org следующий код:

int foo(int a, int b) {
    return a + b;
}
int bar(int a, int b) {
    return a - b;
}

В результате увидим нечто неизвестное:

f(int, int):
    lea     EAX, [RDI+RSI]
    ret
g(int, int):
    mov     EAX, EDI
    sub     EAX, ESI
    ret

Несложно догадаться, что обе функции получают свои аргументы в регистрах EDI и ESI, а возвращают — в EAX. Но непонятно, что такое LEA.

Команда `LEA`.

LEA расшифровывается как "load effective address" и вторым её аргументом всегда является адрес памяти. Именно этот адрес присваивается в первый аргумент инструкции. Здесь она используется как альтернатива ADD+MOV.

Как несложно заметить, в качестве адреса можно писать сумму значений в регистрах. А что ещё можно? А вот что: [reg+i*reg+const] где i равно 1, 2, 4 или 8.

Еще LEA не трогает флаги, в отличие от ADD. Что такое флаги — смотри дальше. Детальнее про LEA можно почитать здесь (первые 2 ответа).

Как избегается оптимизируется деление:

Деление занимает много больше тактов, чем другие арифметические операции, а во время его вычисления весь конвейер стоит. Компиляторы стараются избегать операции деления, если это возможно. Например, мы знаем, что беззнаковое деление или умножение на $2^k$ можно легко заменить на сдвиг на $k$. Поэтому следующий код на C++:

unsigned foo(unsigned a) // беззнаковый тип
{
    return a / 2;
}

Может быть оптимизирован компилятором до

foo(unsigned int):
    mov     EAX, EDI
    shr     EAX
    ret

А вот просто сдвинуть знаковое число вместо деления нельзя, потому что у этих двух операций округления в разные стороны. Поэтому тот же код, но с сигнатурой int foo(int a) скомпилируется так:

foo(int):
	mov     EAX, EDI
	shr     EAX, 31  ; Оставляем от числа только старший (знаковый) бит.
	add     EAX, EDI ; Если число отрицательное, то добавляем 1 (чтобы при a = -1 всё работало).
	sar     EAX      ; Арифметический сдвиг вправо на 1 бит.
ret

А что будет с беззнаковым делением на 3? А тут есть другие хаки:

foo(unsigned int):
    mov     EAX, EDI
    mov     EDX, 2863311531 ; 0xAAAAAAAB или 2^33/3
    imul    RDX
    shr     RAX, 33
    ret

Почему это лучше? Как мы уже обсудили, деление дорогое, а константу можем посчитать при компиляции, получая выигрыш в эффективности.

Почему это работает? Потому что при арифметике с переполнением деление на константу можно выполнить через умножение: $$\frac a3=\frac{a\cdot(2^{33}/3)}{2^{33}} = (a\cdot2863311531) \gg 33$$ А в общем случае компиляторы пытаются подобрать $n$ (равное тут $33$), чтобы такая замена работала как требуется. Больше подобного рода трюков можно почитать в книжке Hacker's Delight.

Control-flow.

Мы уже понимаем, что компилятор делает с арифметическими выражениями, а значит линейный код мы уже можем перевести на ассемблер руками. А вот ветвления и циклы — пока нет. Как они идейно работают? У процессора есть команды, которые называются branch’ами. Самая простая из них — jmp (своего рода goto). Её аргументом является число, которое нужно прибавить к IP, чтобы перейти на адрес новой инструкции. В ассемблере, однако, это вместо этого пишется метка, по которой и осуществляется переход.

.loop: ; метка
    inc     AX
    jmp     .loop

Помимо jmp есть conditional branch (то есть переход, если выполнено какое-то условие). Осуществляются они комбинацией команды cmp и какой-то из команд je, jg, jl или подобной. Первая команда (пока непонятным нам образом) сравнивает два регистра, а потом вторая получает результат этого сравнения и совершает переход только в определённом случае. В таблице ниже перечислены условия для каждой из команд:

Команда	Эквивалент	Расшифровка
`je`	`left == right`	jump if equal
`jg`	`(signed)left > (signed)right`	jump if greater
`jl`	`(signed)left < (signed)right`	jump if less
`ja`	`(unsigned)left > (unsigned)right`	jump if above
`jb`	`(unsigned)left < (unsigned)right`	jump if below
`jne`	`left != right`	jump if not equal
`jng`	`(signed)left <= (signed)right`	jump if not greater
`jnl`	`(signed)left >= (signed)right`	jump if not less
`jna`	`(unsigned)left <= (unsigned)right`	jump if not above
`jnb`	`(unsigned)left >= (unsigned)right`	jump if not below

Регистры флагов (FLAGS Registers).

Теперь давайте всё же поговорим, как работает cmp? Для этого нам нужно поговорить о такой штуке как регистр флагов. Он содержит, собственно, битовые флаги. Из их большого набора нас интересуют

CF — carry flag.
ZF — zero flag.
SF — sign flag.
OF — overflow flag.

В процессе своей работы разные инструкции устанавливают различные флаги (какие-то инструкции на определённые флаги не влияют, у каких-то инструкций эти флаги имеют свое значение, поэтому читайте документацию). А мы рассмотрим, как с ними работают инструкции add и sub. Они выставляют:

ZF — если результат равен 0.
SF — если результат отрицательный.
CF — если произошёл перенос в сложении/заимствование в вычитании беззнаковых чисел.
OF — если знаковая операция вызвала переполнение.

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

Или есть ещё команды перехода, основанные на флагах:

jz — jump if ZF.
js — jump if SF.
jc — jump if CF.
jo — jump if OF.
jnz — jump if not ZF.
jns — jump if not SF.
jnc — jump if not CF.
jno — jump if not OF.

Как работают арифметические условные переходы.

cmp устанавливает флаги так же, как это делает вычитание. Отсюда посмотрим, какие флаги проверяются какими условными переходами.

Про je, jb и ja всё понятно. je выполняется при ZF, jb — при CF, ja — если ZF и CF оба ложны. А что с jl и jg, сейчас обсудим.

Давайте рассмотрим числа из 3 бит простоты и наглядности ради, и пометим цветом те места, где CMP задаёт определённые флаги. ZF — очевидно.

CMP-ZF

Теперь посмотрим на SF. Если мы вычитаем из маленького числа число чуть побольше, то результат будет отрицательным. Но если мы, например, из $-8$ вычитаем что-то, то происходит переполнение, и результат получается положительным. Аналогично если мы из положительного числа вычитаем большое отрицательное, может произойти переполнение в обратную сторону, и результат станет отрицательным. Учитывая это, имеем, что SF задан в этой области:

CMP-SF

А ещё мы уже обсудили переполнение, и можем сказать, где задан OF:

CMP-OF

Ветвление	Условие
`je`	`ZF`
`jg`	`(SF == OF) && !ZF`
`jl`	`SF != OF`
`ja`	`!CF && !ZF`
`jb`	`CF`

Кстати, несмотря на то, что в ассемблере есть je и jz, по сути они делают одно и то же, и даже одинаковым набором байт обозначаются (поэтому если вы будете ассемблировать-дизассемблировать код, учтите, что в коде ASM je может замениться на jz или наоборот).

Помимо cmp есть ещё одна инструкция, которая не делает ничего, кроме расстановки флагов — test. Она делает побитовое "И" аргументам и ставит:

ZF, если результат равен нулю.
SF, если результат отрицательный.
CF, никогда (всегда ставится в false).
OF, никогда (всегда ставится в false).

Пример:

	test	AX, AX ; проверка на 0
	jz		label

Иногда ни test, ни cmp не нужны, потому что многие инструкции ставят флаги, и иногда так, как вам нужно. Пример:

.loop:
	mov		DX, AX
	add		AX, BX
	mov		BX, DX
	dec		CX
	jnz		.loop

Работа с функциями.

Основы работы со стеком.

Вопрос на засыпку: как реализовать рекурсию? Да и в принципе, вызов функций? Мы выходим только из той функции, в которую зашли последней. Это, барабанная дробь, стек. Стек — это кусочек памяти, его вершина имеет меньший адрес, а дно — больший. На вершину стека указывает регистр SP, название которого так и расшифровывается — stack pointer.

Процессор предоставляет две базовые функции работы со стеком — push и pop. Несложно догадаться, что push src равносильно

    sub     RSP, 8
	mov     [RSP], src

А pop dst —

    mov     dst, [RSP]
    add     RSP, 8

Ещё есть две "более высокоуровневые" инструкции — call и ret. Первая принимает своим единственным аргументом метку (адрес функции, которую нужно вызвать), кладёт на стек адрес следующей инструкции и делает переход по метке. Вторая берёт со стека адрес и переходит по нему. Несложно заметить, что именно так функции и работают. Честно написать, чему эти инструкции равносильны, невозможно, потому что нельзя лёгким образом получить доступ к IP.

Передача параметров в функцию.

Быстрее и проще всего положить параметры в регистры (например, EDI и ESI). Но регистров у нас конечное число, поэтому если параметров много, то может не хватить. В таком случае параметры можно передавать через стек. И чтобы получить их, мы делаем mov RAX, [RSP+8] или mov RAX [RSP+16]. Но после возвращения из функции, у нас параметры всё ещё на стеке, надо, чтобы кто-то его почистил. Можем сделать так, чтобы вызывающая функция почистила стек, прибавляя константу к RSP каждый раз после вызова. Но не лучше ли запихнуть это в вызываемую функцию? Ну, идейно да, но надо куда-то сохранить возвращаемое значение... В x86 вообще есть ret n, который берёт значение, сдвигает RSP на n и возвращается. Это называется «вызываемая функция чистит стек». Осталось понять, что делать с локальными переменными? А, их можно положить выше на стек после адреса возврата.

ABI

Хорошо, а кто определяет, как передавать параметры? А этим занимается ABI - application binary interface. ABI содержит вообще всю информацию, необходимую для взаимодействия, например, вас с операционной системой.

Выравнивание и размеры типов данных.
Соглашение о передаче параметров, о том, кто чистит стек, о том, в каком порядке параметры на стек кладутся.
Как выполняются системные вызовы.
Наличие red zone (например, она есть на 64-битных линуксах)

Что такое red zone? Это кусок памяти ниже указателя стека, который никто, кроме нас, не имеет права использовать. На 64-битных линуксах размер этого куска — 128 байт. То есть можно безопасно использовать 128 байт ниже стека, никто ничего с ними не сделает при системном прерывании.

Заметим, что на x86 Windows red zone'ы нет.

А почему нельзя использовать память ниже стека, если нет red zone? Потому что не гарантируется, что память ниже стека никто не будет использовать. Например, обработчик прерываний использует стек, кладёт туда свои данные.

Всё это — ABI. Обычно он привязан к ОС.

Windows из данного правила является исключением: в нём есть целая табличка о том, какой из миллиона (cdecl, stdcall, thiscall, fastcall, ...) способов передавать параметры, что делает. И можно в коде прямо на функции явно написать, какой способ использовать. Даже свой собственный можете сделать.

А кто, кстати, обычно чистит стек? Вызывающая функция. Почему так, это же, вроде как, неудобно? Потому что существуют variadic-функции. Когда вы делаете printf, компилятор просто пихает параметры на стек, а вызываемая функция не знает, сколько их. Поэтому чистит вызывающая, которая знает.

Системные вызовы.

syscall - интерфейс взаимодействия процесса программы с ядром ОС. Например, это чтение/запись в файл/терминал, завершение программы с кодом ошибки и т.д.

Стековый фрейм.

Можно заметить, что под GCC код

int foo(char const*);

int bar()
{
    char arr[40];
    return foo(arr) + 1;
}

с флагами -O2 -fno-omit-frame-pointer компилируется во что-то такое:

bar():
	push	RBP
	mov		RBP, RSP
	sub		RSP, 48

    lea     RDI, [RBP-48]
    call    foo(char const*)

	mov		RSP, RBP
	pop		RBP
	ret

Нам интересна обёртка push RBP, mov RBP, RSP, ..., pop RBP. Зачем это? Посмотрим, что делает этот код. Он сохраняет старое значение RBP на стек. А при вызове рекурсивной функции в RBP будет RSP. То есть во внутренней функции мы запихаем на стек адрес первой. И так далее. То есть на стеке есть односвязный список значений RBP от нового к старому. Поэтому пойдя по RBP, можем напечатать весь стек (это называется unwind — раскрутка стека). Буквально так очень давно работали отладчики. В наше время этот режим менее актуален, поэтому генерировать эти инструкции избыточно. Вместо этого компиляторы вместе с кодом генерируют отладочную информацию как раз о том, какие команды каким строкам кода соответствуют, как раскручивать стек и подобное. gcc генерирует стековый фрейм только с некоторым ключом. MSVC генерирует его по умолчанию. Возможно, это потому, что рандомная опубликованная exe'шка может в отладочных данных содержать секретики. Их вы публиковать не хотите, поэтому только стековые фреймы. К чему это всё для нас? Если вы пользуетесь какими-то инструментами, которые снимают стек (отладчик или профилировщик), убедитесь, что у вас есть отладочные символы, и отлаживаете вы тоже согласно им. Либо и то, и другое по стековому фрейму.

Выделение памяти:

void f(char const*);

void g()
{
    char arr[113];
    f(arr);
}

Компилируется в:

g():
    sub     RSP, 136
    mov     RDI, RSP
    call    f(char const*)
    add     RSP, 136
    ret

К локальным переменным обращаемся через RSP, лежат на стеке. Размер стека - переменная на уровне операционной системы (вроде).

Обратим внимание на то, что если изменить размер массива на 112, то этот код скомпилируется в:

g():
    sub     RSP, 120
    mov     RDI, RSP
    call    f(char const*)
    add     RSP, 120
    ret

Почему 136 изменилось на 120? Этот эффект называется выравниванием (alignment).

В качестве основной единицы работы с памятью используется машинное слово, размер которого обычно составляет несколько байт. Так называемый unaligned access сложен в реализации на аппаратном уровне, поэтому обращения по произвольному адресу либо не поддерживаются (и вызывают исключение процессора), либо поддерживаются, но работают медленно. Обычно компилятор выравнивает данные по границам машинных слов, в нашем случае 8 + 16 * k.

ОС, процессор и память

Прерывания

Почему программа с вечным циклом не повесит нам весь компьютер, даже если у нас всего одно ядро? Как ОС работает с устройствами? Всё это завязано на прерываниях.

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

Polling — процессор сам опрашивает устройства, когда считает нужным.
Interrupt (прерывание) — устройство само говорит об изменении, процессор вызывает обработчик прерываний.

С точки зрения программы это выглядит так: ОС её прерывает, выполняет что-то, после чего возобновляет выполнение там, где прервала. И сама заботится о том, чтобы программа не видела изменения регистров, например. То есть

Значения регистров текущего процесса дампаются в оперативную память.
Подгружаются значения регистров другого процесса, и исполнение передаётся ему.

Такая схема называется вытесняющей многозадачностью.

Если вам хочется посмотреть на прерывания глазками, вам нужен файл /proc/interrupts. Там вы можете посмотреть все типы прерываний с процессами и описаниями. Например, при нажатии на кнопку и отжатии кнопки на клавиатуре посылается специальное прерывание, с тачпадом то же самое и т.п. Сейчас нас интересуют два типа:

Local timer interrupt — прерывания по таймеру, своё у каждого ядра ЦП. ОС заводит таймер, когда таймер срабатывает, провоцируется прерывание, и ОС получает управление в обработчике прерываний. На самом деле, всё сложнее, потому что постоянно работающие таймеры это неэкономно, поэтому он, например, отключается, если на ядре ничего не исполняется.
Rescheduling interrupts — прерывания, использующиеся для перепланировки (миграции) процесса на другое ядро в целях распределения нагрузки. Реализованы с помощью IPI.

Работа программы с памятью

Что будет, если мы возьмём рандомное число, кастанём его в char*, после чего запишем по нему букву? Будет SEGFAULT. Что это такое вообще? Чтобы ответить на этот вопрос, надо понять, как в одной памяти живут программы. В процессоре есть механизм, который позволяет операционной системе делать две вещи:

Hardware abstraction — программа не знает, что с точки зрения железа происходит. Например, мышка может быть подключена по-разному, но программе всё равно. В случае с памятью программа не знает, что происходит с её памятью, с её точки зрения вся память — её память.
Isolation process — программа не может повлиять на другие программы (записать в их память). Если вы это специально не захотите, конечно.

Как конкретно это работает? В нашей прошлой модели память — пронумерованные ячейки. Мы будем называть физической памятью то, что у нас в жизни в оперативке (какие-то квадраты с какими-то открытиями/закрытиями строк). Этот уровень недоступен даже ядру ОС, максимум можно догадываться, что там. Вместо этого вы обращаетесь к памяти по другим адресам (виртуальная память), которые процессором преобразуются (транслируются) в физический адрес, по которому он и обращается. У вас нет способов этого избежать, максимум (если вы в ядре) — слабо повлиять. И суть в том, что пересчёт разный для разных программ, поэтому в разных программах одно и то же число адреса — разные ячейки физ. памяти. Трансляция адресов реализуется в специальном блоке процессора, называемом MMU.

Дальше будет рассматриваться 32-битная система, а потом будет сказано, чем 64-битная отличается.

Страничная адресация

Это способ организации виртуальной памяти, при котором виртуальные адреса отображаются на физические постранично (обычно 1 страница = 4 KB). Процессор может настроить механизм так, чтобы произвольная страница виртуальной памяти транслировалась в произвольную физической. При этом память процесса может лежать в физической памяти в любом порядке:

Memory Disorder

В принципе, ОС ничего не мешает сделать две страницы виртуальной памяти и направить их в одну страницу физической. Работать это будет так, как вы думаете. Если делать это из разных программ, они смогут общаться. Ещё мы можем запрещать какие-то страницы (помечая их как отсутствующая). То есть считается, что эта страница никуда не транслируется. Именно поэтому и происходят SEGFAULT'ы. Соответственно, процессор даёт эту информацию ОС, а она даёт программе ошибку.

В 32-битных системах система страничной адресации основана на вот таких штуках:

Memory Disorder

Сначала адрес, затем разные флаги. Например, R — read only или нет. W — write through — про кеширование, прочие флаги содержат другие данные для ОС. В 64-битных системах имеем то же самое, но адрес побольше, и сама структура занимает 64 бита, а не 32.

Если подойти к хранению таких структур наивно, то получится набор страниц, для каждой храним 32-битное число. То есть имеем массив таких структурок. Это работает, но имеет одну проблему: в 32-битном режиме имеем 4ГБ памяти, то есть нужно 4МБ памяти на процесс. Это слишком много, особенно учитывая то, что в древности 4МБ — это типовой размер был. А в наше время в 64-битном режиме на одну программу понадобится 32ПБ. Поэтому заметили, что бо́льшая часть программ используют меньше 4ГБ памяти. А значит бо́льшая часть страниц недоступна. Поэтому давайте вместо 1048576 элементов хранить табличку 1024×1024. То есть вместо массива на много элементов храним массив (каталог страниц) размера 1024 из указателей на массивы размерами по 1024 (таблицы страниц). И тогда мы можем сразу в каталоге пометить, что его элемент никуда не ссылается.

Это выглядит как-то так:

Page Table

CR3 с картинки — специальный регистр, где хранится корень дерева. Подробнее можно прочитать тут.

Механизм адресации на уровне процессора:

Пример адреса: Virtual address - 0x123456789A

Младшие 12 бит виртуального адреса: смещение внутри страницы. Следующие 10 бит - индекс в таблице страниц, старшие 10 бит - индекс в каталоге страниц.

typedef uint32_t page_table_element;
typedef uint32_t virtual_address;
struct page_directory
{
     uint32_t translate(virtual_address);
     private:
     	page_table_element data[1024];
};

Альтернатива известна лишь одна: хеш-таблица, но она плохо взаимодействует с кэшем. Использовалась в PowerPC.

Страничная адресация на 64-битной системе

Всё выше было про 32-битную архитектуру. На 64-битной

Виртуальный адрес сильно больше (64 бита, собственно).
Больше физической памяти.
Размер «структурки» также удваивается, а значит структурок в одном массиве теперь 512, а не 1024. То есть адрес мы уже делим на кусочки по 9 бит, а не по 10.

Но так даже с тремя уровнями вместо двух остаётся куча лишних байт (на адрес расходуется 39 бит, куда девать остальные — не понятно). В таком случае считается, что «лишние» биты должны совпадать со старшим «не-лишним». Более современные процессоры поддерживают и 4 уровня в дереве (т.е. теперь адрес эффективно 48-битный), а новейшие Intel'ы — 5 уровней, что позволяет адресовать 128ПБ. Пример с тремя уровнями выглядит так:

Page Table

Ещё связанные с этой темой такие технологии как TLB и Huge Pages, но это смотрите в ~~следующих сериях~~ следующем файле.

Нестандартные использования страничной адресации

Во-первых, есть memory-mapped файлы. Это просьба операционной системе загрузить файл с диска в ваше адресное пространство. Для программы при этом создаётся иллюзия, что она напрямую обращается в этот файл.
В некотором смысле антиподом memory-mapped файлов являются файлы подкачки (swap). Ситуация тут обратная — есть вы хотите сожрать больше памяти, чем вам могут дать, то лишнюю память выгружают на диск, а при использовании подчитывают.
А ещё мы уже обсудили, что можно направить виртуальные адреса у двух разных программ в одну физическую страницу, чтобы реализовать базовое взаимодействие между ними. Это называется «разделяемой памятью». (Из более высокоуровневых технологий есть такая штука как PIPE.)

Stack guard page

Стек — зарезервированный кусок памяти определённого размера. Как тогда проверять, что произошёл stack overflow?

Может случиться, что сразу снизу заполненного стека (напомним, что стек увеличивается сверху вниз, то есть в сторону уменьшения адреса) лежит какой-то отмапленный файл. Тогда вызов push x не приведёт к ошибке — этот сегмент памяти же доступен, мы запишем что-то в этот файл и повредим его. Такие ситуации легли в основе уязвимости Stack Clash.

В Linux и Windows для предотвращения этого сразу снизу стека зарезервировали специальную страницу, называемую stack guard page. Теперь, если мы перешли за границу стека, то мы обращаемся к guard page, она недоступна и мы получаем SIGSEGV. Данные в безопасности! :)

Вот только не совсем. Stack guard page легко перепрыгнуть, достаточно сделать функцию с тысячами локальных переменных.

В Linux эту проблему решили следующим образом — размер stack guard page просто увеличили до 1 мегабайта. Формально проблема осталась, но её уже гораздо сложнее воспроизвести.

В Windows решили воспользоваться тем, что страницы выделяются не сразу, а только после обращения к ним. Требуется, чтобы страницы стека page fault'ились подряд, иначе мы словим access violation. Теперь перепрыгнуть невозможно, ведь для этого нужно пропустить страницы, а это, в свою очередь, вызывает ошибку.

Более точная (и оптимизированная) модель работы процессора.

Optimize for data first, then code. Memory access is probably going to be your biggest bottleneck.

Нам надо знать, как оптимизировать программы, а для этого надо понимать, какие операции в процессоре дешёвые, а какие — дорогие. Скорее всего, наш ассемблерный код, если переписать его в плюсы, а потом скомпилировать, заработает сильно быстрее.

Мы рассмотрим несколько примеров, которые в нашу текущую модель не укладываются вообще, разберёмся в них и уточним модель. При этом мы не стремимся получить максимальную детализацию. Во-первых, если у нас есть эффект, дающий нам $0.01%$ прироста скорости, он нам не очень критичен. Во-вторых, чтобы анализировать и делать выводы, нам придётся нашу модель сделать проще. Физики вон, упрощают реальный мир, чтобы делать свои предсказания.

Сначала разберёмся, о каких процессорах мы будем говорить. Ответ — в каком-то смысле обо всех современных (последние 17 лет). Причём вне зависимости от архитектуры. И это не заговор разработчиков, просто в течение 40 лет все думали, как процессоры сделать быстрее и энергоэффективнее, и то, что оптимизации поддавалось, то оптимизировали. А то, что поддавалось оптимизации сложно, то оставалось медленным. Например, операция деления занимает много больше времени, чем, скажем, сложение. И это не потому, что разработчики процессоров дураки или лентяи, а потому что есть внутренняя сложность.

Работа с памятью.

Кэш-память.

Одинаково ли по времени будут работать следующие два кода?

for (i = 0; i < N; i++)         for (i = 0; i < N; i++)
	for (j = 0; j < N; j++)         for (j = 0; j < N; j++)
		a[i][j] = 0;                    a[j][i] = 0

А вот вообще нет. Разница во времени работы будет весьма ощутимой по вине процессорного кэша. Первый цикл обращается к памяти последовательно, а второй "скачет" по ней. Поэтому первый цикл как подгружает кэш-линию, так к ней и обращается, а второй — подгружает-выгружает. С ростом N видна разница между уровнями кэша на графике времени обработки одного элемента:

Cache Hit Graph

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

Кэш реализован через хэш-таблицы (дискретного размера), где ключ - адрес в памяти. Линии кэша обычно занимают 64 байта и разделены на группы (buckets), размеры которых называются ассоциативностью кэша.

Зачем существует кэш вообще? Как мы знаем, согласно закону Мура, мощность процессоров от времени зависит экспоненциально. Так вот памяти — тоже. Но скорость памяти растёт сильно медленнее (сейчас процессор делает по 4 простые операции за такт, а обращение к памяти занимает 200+).

Зависимость производительности процессоров и памяти со временем

Это никуда вообще не годится, поэтому на процессорах появились кэши. Занимают они чуть ли не половину кристалла, и так было что в пентиумах, что во всех современных процессорах. Типовое время обращения к памяти — 4, 12, 36 и 230 тактов для L1, L2, L3 и RAM соответственно. Поэтому сначала надо оптимизировать данные, а уже потом код.

Подробнее про кэш можно прочитать в конспектах по ЭВМ или в других конспектах по ЭВМ.

Префетчинг.

Prefetching — это метод, при помощи которого заранее определяется, к каким областям памяти в будущем пойдут обращения. Если много кэш-промахов, заранее подгрузить в кэш запросы очень полезно. Кстати, работает это на уровне кэш-подсистемы процессора, а не компилятора/ОС.

Осуществляется префетчинг, например, при помощи улавливания последовательных обращений к памяти (если вы сначала обращаетесь к первой ячейке, а потом — ко второй, то можно заранее начать обращение к третьей, вдруг вы туда обратитесь). В современных процессорах есть аж целых 4 разных префетчера: два для L1 и по одному для L2 и L3. Идейно префетчинг позволяет тратить ресурсы процессора на то, чтобы ускорять память, что полезно всё по той же причине — память медленнее.

Промежуточные выводы (best practices) касательно памяти.

Иногда выгоднее будет что-то пересчитать, чем хранить всё в памяти (процессор быстрее же).
Если вы знаете, в каком порядке вы будете обращаться к данным, важно правильно их положить (тоже последовательно).
Хранить «горячие» и «холодные» данные нужно в разных местах. «Горячие» — это которые вам часто нужны, «холодные» — которые не очень. Почему в разных? Потому что иначе у вас в кэше будут лежать и «горячие», и «холодные» данные, вместо того, чтобы забить его «горячими» полностью.

Пример: Как правильно реализовать хранение хэш-таблицы с открытой адресацией. Два варианта:

Hash-Table

А вот что лучше, зависит от hit rate'а нашей таблицы:

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

Работа с указателями.

Indirection.

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

Указатели в структурах данных.

Вы, возможно, не знали, но ваша программа процентов на 80 состоит из них. Так, std::vector — это три указателя, std::list — два указателя и одно число размером с указатель, std::set и std::map — один указатель и одно число. При этом указатели на x86-64 здоровые, 64 бита занимают. А ведь вам обычно не нужны 64-битные указатели, вам хватит и 32 бит, а значит памяти они занимают вдвое больше, чем могли бы. Поэтому Intel сделали ABI x32. Для ОС это выглядит как 64-битная программа, но внутри она имеет 32-битные указатели. Во всём остальном она ~~верблюд~~ x86-64. Конвенции вызова там точно такие же, вещественная арифметика — тоже, количество регистров — 15 целочисленных и 16 вещественных. Этот ABI не очень прижился, что довольно грустно.

Но что интересно, на целочисленных тестах x32 было на 5–8% быстрее, чем x86-64 (просто из-за того, что данных меньше), на floating-point данных разницы нет, а на одном специфичном бенчмарке (там просто куча указателей) ускорение достигало 40%. А в сравнении с x86, ускорение было соответственно в 7–10% и 5–11% для целых и floating-point тестах, а специфичный бенчмарк был с 64-битной арифметикой (и тоже имел 40% ускорение).

Translation lookaside buffer.

Давайте вспомним про виртуальную память. Имея нашу древовидную структуру, на каждое обращение к памяти в программе нам придётся делать 4 (или 5, если уровней 4) обращения в память внутри процессора (чтобы пройтись по дереву). Это треш, поэтому результат трансляции виртуальной памяти в физическую также кэшируется. Буфер, в который кэшируется, называется TLB (translation lookaside buffer). А это значит, что если наша программа обращается к реально большому объёму памяти, то мы платим ещё и за трансляцию, а не только за этот факт сам по себе.

Huge pages.

Что ещё может улучшить неприятную ситуацию с трансляцией? Страницы по 4 KB достаточно маленькие, и заниматься администрированием их довольно накладно. Поэтому в процессоре есть механизм Huge pages, который позволяет нам на промежуточном уровнем дерева установить специальный бит, который говорит, что этот промежуточный элемент хранит не ссылку на следующий, а сразу страницу данных.

Huge pages tree

И тогда страница будет иметь размер 2 MB, если брать предпоследний уровень, или вообще 1 GB, если третий снизу. Это экономит и время трансляции, и место в TLB.

Но использовать Huge pages тяжело, так как с ними тяжело делать swap (подкачку страниц). Например, в Windows требуются специальные права, чтобы выделять не-swappable память.

Конвейер (Pipelining).

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

Branch prediction.

Спекулятивное исполнение: условные переходы дорогие, поэтому мы предсказываем переход, выполняем, а если не угадали, то откатываемя. В общем, ничего нового. Также это называется branch prediction. Можем как выиграть, так и проиграть от этого. Например, в некоторых программах на отсортированном массиве предсказание может улучшить время работы в несколько раз.

Касательно предсказаний, процессор умеет предсказывать много различных паттернов, поэтому искусственно составить что-то, что будет сложно предсказываться, довольно проблемно. Но это не единственное, что процессор умеет. Давайте рассмотрим генератор случайных битов, который называется линейный регистр сдвига с обратной связью. (Раз биты случайные, то предсказываться должно просто отвратительно.) Он работает примерно так:

unsigned lfsr = 0xace1;
for (unsigned i = 0; i != 1000000000; i++)
{
      unsigned lsb = lfsr & 1;
      lfsr >>= 1;
      if (lsb)
            lfsr ^= 0xb400;
}

Видим здесь условный переход. Попытается его поправить двумя путями. Раз:

unsigned lfsr = 0xace1;
for (unsigned i = 0; i != 1000000000; i++)
{
      unsigned lsb = lfsr & 1;
      lfsr >>= 1;
      lfsr ^= 0xb400 * lsb;
}

Два:

unsigned lfsr = 0xace1;
for (unsigned i = 0; i != 1000000000; i++)
{
      unsigned lsb = lfsr & 1;
      lfsr >>= 1;
      lfsr ^= 0xb400 & -lsb;
}

Если сравнить время работы этих программ, то они будут отличаться так, как ожидается (первая самая долгая, третья — самая быстрая), но ненамного. Но вот если проанализировать программу какими-нибудь прошаренными средствами, то можно заметить, что неверные предсказания дают нам $0.01%$ от всех предсказаний. То есть проблема не в условных переходах. А знаете, почему?

А потому что в процессоре есть такие инструкции как cmovne. Если скомпилировать первый вариант с оптимизациями, получим комбинацию из test и cmovne. Как несложно догадаться, последняя инструкция совершает присваивание в том случае, если не задан флаг ZF. Без условного перехода.

Хорошо, но всё же что будет, если правда сделать условный переход? Для этого компилятору надо дать ключи -fno-if-conversion -fno-if-conversion2, которые заставят его не использовать cmovne, и вот тогда уже всё замедлится намного сильнее.

Спекулятивное взаимодействие с памятью.

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

int f(int a, int b, int c, int d)
{
 return a * b * c * d;
}

может скомпилиться в следующий код, чтоб уменьшить количество зависимых умножений: (a * b) * (c * d)

 imul		edi, esi
 imul		edx, ecx
 imul		edx, edi
 mov		eax, edx
 ret

То же самое очень хочется делать с обращениями к памяти. По-хорошему, нельзя читать до того, как закончат выполняться записи, потому что в случае, если мы читаем то, что писали, хочется прочитать то, что записано, а не что-то левое. Но процессор выполняет операции спекулятивно, в надежде на отсутствие коллизий. Поэтому код:

void count_huffman_weights(char const* src, size_t size)
{
     uint32_t count[256] = {0};
     for (size_t i = 0; i != size; ++i)
         ++count[src[i]];
}

Будет работать тем быстрее, чем более разные данные в src (если данные одинаковые, процессор спекулятивно запускает несколько инкрементов за раз, потом понимает, что они инкрементят одно и то же и откатывает все, кроме одного; в результате не только простаивает superscalar, но и происходят откаты туда-обратно). Вот как выглядит граф зависимостей в этом коде:

Dependencies

Чтобы это пофиксить, можем сделать 8 разных массивов-счетчиков. Такая реализация используется в библиотеке Zstandart:

void count_huffman_weights_improved(char const* src, size_t size)
{
      uint32_t count[8][256] = {};
      size = size / 8 * 8;
      for (size_t i = 0; i < size;)
      {
            ++count[0][src[i++]]; ++count[1][src[i++]];
            ++count[2][src[i++]]; ++count[3][src[i++]];
            ++count[4][src[i++]]; ++count[5][src[i++]];
            ++count[6][src[i++]]; ++count[7][src[i++]];
      }
}

Полезные книжки по теме.

J. Shen, M. Lipasti — Modern Processor Design: Fundamentals of Superscalar Processors.
J. Hennessy, D. Patterson — Computer Architecture: A Quantitative Approach.

Они сильно выходят за рамки нашего курса, но тем не менее интересны.

Мы наконец-то начинаем говорить про C++. Начать, разумеется, надо с базовых вещей, которые появились ещё в C. И вообще текущая тема может быть по праву названа как введением в C, так и введением в C++.

Однако C и C++ — это разные языки:

Их разрабатывают разные люди с разными целями.
Они имеют разные компиляторы, несмотря на то, что обычно компании, имеющие компиляторы C++ также имеют компилятор C. Эти компиляторы имеют общий код, но они всё же не одинаковы — этот самый общий код также используется и для Go, и для D, и для Ada... Исключением из этого правила является Clang, где просто if'ами различаются C и C++. Правда, там ещё и Objective-C и нечто ещё...
Стили программирования на C и C++ кардинально отличаются, если вы пишете на них одинаково - вы дурачок.
C не является подмножеством C++, случайная программа на C вообще не факт что будет корректна в C++. Правда, обычно придётся менять её не очень сильно. Примером такого отличия является код вида a ? b : c = 42. В C — это (a ? b : c) = 42, а в C++ — a ? b : (c = 42).

Целочисленные типы записываются так:

Размер	знаковый	беззнаковый
short	short	unsigned short
(обычный)	int	unsigned
long	long	unsigned long
long long	long long	unsigned long long

Причем порядок записи не имеет значения: int signed, signed int, int - одно и то же.

Размер	32 bit	win64	linux64
`char`	1 байт	1 байт	1 бай
`short`	2 байта	2 байта	3 байта
`int`	4 байта	4 байта	4 байта
`long`	4 байта	4 байта	8 байт
`long long`	8 байт	8 байт	8 байт

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

вот мне надо 4 байта - возьму int, а теперь мне надо 8 байт - возьму long.

Нужно использовать хедер cstdint

Он предоставляет типы:

int8_t, uint8_t
int16_t, uint16_t
int32_t, uint32_t
int64-t, uint

Какой тип использовать для индексации в массиве, поэтому мы пишем:

for(size_t   i = 0; i < 100; i++){
    do_something();
}

формально можно сказать, что у этой структурки только 5 полезных байт. В sizeof мы дополняем до 8

короч я ушел спать

Процесс компиляции программ

Запись лекции y2019:

Запись лекции y2024:

TODO

Зачем нам нужно это изучать?

У студентов часто возникают с этим проблемы — когда компилятор пишет ошибку, а студент не понимает, что она значит

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

Процесс компиляции C++ программы

Программы на C++ компилируются с помощью компилятора. Один из популярных компиляторов - g++:

g++ hello.cpp

Сам g++ по себе ничего не делает, а вызывает другие команды, которые выполняют компиляцию по частям. На linux, если использовать strace -f -e trace = execve

То он запускает:

Пройдем код:

hello world insert

Разберем процесс компиляции поэтапно

Препроцессинг

Препроцессор - это первый этап компиляции. Он обрабатывает директивы препроцессора, такие как #include, #define, #ifdef и т.д. Чтобы увидеть результат работы препроцессора, можно использовать следующую команду:

g++ -E -P hello.cpp > hello.i

Эта команда создаст файл hello.i, который будет содержать код после обработки препроцессором. В этом файле вы увидите:

Раскрытые макросы
Вставленный код из заголовочных файлов
Удаленные комментарии
Обработанные условные директивы (#ifdef, #ifndef и т.д.)

#include — директива препроцессора, которая тупо вставляет указанный файл в то место, где написан инклуд.

Пример:

Трансляция

Она делает комманду:

g++ -s -masm=intel -02 hello.i

Она переводит C++ программу в язык ассемблера.

Выполняется при помощи g++ -S, выходной файл обычно имеет расширение .s. Если передать параметр -masm=intel, можно уточнить, в какой именно ассемблер переводить (как было сказано в asm, ассемблеры отличаются в зависимости от инструмента).

Ассемблирование

Берем ассемблерный код переводим в машинный код:

as -o hello.o hello.s

Выполняется специальной утилитой as, выходной файл обычно имеет расширение .o (и называется объектным файлом). На данном этапе не происходит ничего интересного — просто инструкции, которые были в ассемблере, перегоняются в машинный код. Поэтому файлы .o бесполезно смотреть глазами, они бинарные.

Для того, чтобы смотреть бинарники есть утилита objump:

objdemp -drC -Mintel hello.o

Линковка

g++ -o hello.o

Нужна, если файлов несколько: мы запускаем препроцессор, трансляцию и ассемблирование независимо для каждого файла, а объединяются они только на этапе линковки. Независимые .cpp файлы называют единицами трансляции. Разумеется, только в одной единице должен быть main. В этом main'е, кстати, можно не делать return 0, его туда вставит компилятор.
Сто́ит сказать, что информация о линковке верна до появления модулей в C++20, где можно доставать данные одного файла для другого. Там появляется зависимость файлов друг от друга, а значит компилировать их надо в определённом порядке.

Классическая схема этапов компиляции выглядит так:

Compilation graph

Есть похожая статья на хабре по теме.

Объявление и определение.

Код редко пишется в одном фале и хочется делать что-то типо такого:

// a.cpp:
int main() {
	f();
}

// b.cpp:
#include <cstdio>

void f() {
	printf("Hello, world!\n");
}

Это не компилируется, а точнее ошибка происходит на этапе трансляции a.cpp. В тексте ошибки написано, что f не определена в области видимости. Всё потому, что для того, чтобы вызвать функцию, надо что-то про неё знать. Поэтому на этапе трансляции нужно знать сигнатуру функции. Чтобы указать эту сигнатуру, в C++ есть объявления:

// a.cpp:			
void f();

int main() {
	f();
}

Когда мы пишем функцию и точку с запятой — это объявление/декларация (declaration). Это значит, что где-то в программе такая функция есть. А когда мы пишем тело функции в фигурных скобках — это определение (definition).

Кстати, написать объявление бывает полезно даже если у нас один файл. Например, в таком файле:

#include <cstdio>

int main() {
	f();
}

void f() {
	printf("Hello, world\n");
}

Это не компилируется, и дело в том, что компилятор читает файл сверху вниз, и когда доходит до вызова функции f внутри main, он ещё не дошёл до её определения(которое находится снизу). Тут можно переставить функции местами, да, но если у нас есть взаиморекурсивные функции, то там переставить их не получится — только написать декларацию.

Ошибки линковки. Инструменты nm и objdump. Ключевое слово `static`.

Рассмотрим такой пример:

// a.cpp
#include <cstdio>

void f()
{
	printf("Hello, a.cpp!\n");
}

// b.cpp
#include <cstdio>

void f()
{
	printf("Hello, b.cpp!\n");
}

// main.cpp
void f();

int main()
{
	f();
}

Тут вам на этапе линковки напишут, что функция f() определяется дважды. Чтобы красиво посмотреть, как это работает, можно использовать утилиту nm. Она показывает символы внутри объектника. Когда вы сгенерируете a.o и вызовете nm -C a.o, то увидите что-то такое:

                 U puts
0000000000000000 T f()

Что делает ключ -C, оставим на потом. На то что тут находится puts вместо printf, тоже обращать внимание не надо, это просто такая оптимизация компилятора — когда можно заменить printf на puts, заменяем.
А обратить внимание надо на то, что puts не определена (об этом нам говорит буква U), а функция f() — определена в секции .text (буква T). У main.cpp, понятно, будет неопределённая функция f() и определённая main. Поэтому, имея эти объектные файлы, можно слинковать main.cpp и a.cpp. Или main.cpp и b.cpp. Без перекомпиляции. Но нельзя все три вместе, ведь f() будет определена дважды.

objdump

Если мы хотим посмотреть на объектные файлы поподробнее, нам понадобится утилита objdump Вот некоторые из ее основных возможностей:

Дизассемблирование (-d): Позволяет увидеть машинный код в виде ассемблерных инструкций. Это полезно для анализа того, как компилятор преобразовал ваш исходный код в машинные инструкции.
Отображение релокаций (-r): Показывает информацию о релокациях - это места в коде, которые нужно будет изменить при загрузке программы или при связывании с другими объектными файлами. В общем случае релокация — информация о том, какие изменения нужно сделать с программой, чтобы файл можно было запустить.
Отображение символьной информации (-t): Выводит таблицу символов, включая имена функций и переменных.
Отображение заголовков секций (-h): Показывает информацию о различных секциях в объектном файле (например, .text для кода, .data для инициализированных данных).
Полный вывод (-x): Комбинирует несколько опций для вывода максимально подробной информации об объектном файле.

Если рассматривать на примере выше, то когда мы вызовем objdump -dr -Mintel -C main.o, мы увидим, что на месте вызова функции f находится call и нули. Потому что неизвестно, где эта функция находится, надо на этапе линковки подставить её адрес. А чтобы узнать, что именно подставить, есть релокации, которые информацию об этом и содержат.

static

Ключевое слово static в C++ имеет несколько важных применений:

Для глобальных переменных и функций:

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

Пример: Пусть в нашем файле определена функция f(). И где-то по случайному совпадению в другом файле также определена функция f(). Понятно, что оно так не слинкуется. Но мы можем иметь в виду, что наша функция f нужна только нам и никому снаружи. Поэтому мы сделаем ее static и все будет хорошо.

Если сделать на такие функции nm, то можно увидеть символ t вместо T, который как раз обозначает локальность для единицы трансляции.

Если говорить по-научному, то static функции имеют внутреннюю линковку, а не static - внешнюю.

Важно отметить, что функции, локальные для одного файла, стоит помечать как static в любом случае, так как это помогает компилятору выполнять дополнительные оптимизации. Компилятор может быть уверен, что такая функция не будет вызвана из других единиц трансляции, что открывает возможности для более агрессивной оптимизации, включая возможность полного встраивания (inlining) функции.
Для членов класса:

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

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

Глобальные переменные.

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

extern int x; // Объявление.

int x;        // Определение.

И точно также в глобальных переменных можно писать static, как и было сказано ранее. А теперь пример:

// a.cpp
extern int a;

void f();

int main()
{
	f();
	a = 5;
	f();
}

// b.cpp
#include <cstdio>

int a;

void f()
{
	printf("%d\n", a);
}

В первый раз вам выведут 0, потому что глобальные переменные инициализируются нулями (по стандарту гарантируется), во второй раз 5. Локальные переменные хранятся на стеке, и там какие данные были до захода в функцию, те там и будут. А глобальные выделяются один раз, и ОС даёт вам их проинициализированные нулём (иначе там могут быть чужие данные, их нельзя отдавать).

Декорирование имён. `extern "C"`.

Обсуждённая нами модель компиляции позволяет использовать несколько разных языков программирования. Пока ЯП умеет транслироваться в объектные файлы, проблемы могут возникнуть только на этапе линковки. Например, никто не мешает вам взять уже готовый ассемблерник и скомпилировать его с .cpp файлом. Но в вызове ассемблера есть одна проблема. Тут надо поговорить о такой вещи как extern "C". В языке C всё было так: имя функции и имя символа для линковщика — это одно и то же. Если мы скомпилируем файл

// a.c <-- C, не C++.
void foo(int)
{
	// ...
}

То имя символа, которое мы увидим в nm будет foo. А в C++ появилась перегрузка функций, то есть void foo(int) и void foo(double) — это две разные функции, обе из которых можно вызывать. Поэтому одно имя символа присвоить им нельзя. Так что компилятор mangle'ит/декорирует имена, то есть изменяет их так, чтобы символы получились уникальными. nm даже позволяет их увидеть. Пример:

function	name mangling
`void test(){}`	`_Z4testv`
`void test(int){}`	`_Z4testi`
`void test(char const *)`	`_Z4testPKc`

Но у вас есть и возможность увидеть их по-человечески: для этого существует уже упомянутый ключ -C, который если передать программе nm, то она раздекорирует всё обратно и выдаст вам имена человекочитаемо. objdump'у этот ключ дать тоже можно. А ещё есть утилита c++filt, которая по имени даёт сигнатуру. Например вызов c++filt _Z4testiii вернет test(int, int, int)

Так вот, extern "C" говорит, что при линковке нам не нужно проводить декорацию. И если у нас в ассемблерном файле написано fibonacci:, то вам и нужно оставить имя символа как есть:

extern "C" uint32_t fibonacci(uint32_t n);

У функций, имеющих разные сигнатуры, но помеченных как extern "C", после компиляции не будет информации о типах их аргументов, поэтому это слинкуется, но работать не будет (ну либо будет, но тут UB, так как, например, типы аргументов ожидаются разные).

<---сделал до сюда--->

Линковка со стандартной библиотекой.

Возьмём теперь объявление printf из cstdio и вставим его объявление вручную:

extern "C" int printf(const char*, ...);

int main() {
	printf("Hello, world!");
}

Такая программа тоже работает. А где определение printf, возникает вопрос? А вот смотрите. На этапе связывания связываются не только ваши файлы. Помимо этого в параметры связывания добавляются несколько ещё объектных файлов и несколько библиотек. В нашей модели мира хватит информации о том, что библиотека — просто набор объектных файлов. И вот при линковке вам дают стандартную библиотеку C++ (-lstdc++), математическую библиотеку (-lm), библиотеку -libgcc, чтобы если вы делаете арифметику в 128-битных числах, то компилятор мог вызвать функцию __udivti3 (деление), и кучу всего ещё. В нашем случае нужна одна — -lc, в которой и лежит printf. А ещё один из объектных файлов, с которыми вы линкуетесь, содержит функцию _start (это может быть файл crt1.o), которая вызывает main.

Headers (заголовочные файлы). Директива `#include`.

Если мы используем одну функцию во многих файлах, то нам надо писать её сигнатуру везде. А если мы её меняем, то вообще повеситься можно. Поэтому так не делают. А как делают? А так: декларация выделяется в отдельный файл. Этот файл имеет расширение .h и называется заголовочным. По сути это же происходит в стандартной библиотеке. Подключаются заголовочные файлы директивой #include <filename>, если они из какой-то библиотеки, или #include "filename", если они ваши. В чём разница? Стандартное объяснение — тем, что треугольные скобки сначала ищут в библиотеках, а потом в вашей программе, а кавычки — наоборот. На самом деле у обоих вариантов просто есть список путей, где искать файл, и эти списки разные.

Но с заголовками нужно правильно работать. Например, нельзя делать #include "a.cpp". Почему? Потому что все определённые в a.cpp функции и переменные просочатся туда, куда вы его подключили. И если файл у вас один, то ещё ничего, а если больше, то в каждом, где написано #include "a.cpp", будет определение, а значит определение одного и того же объекта будет написано несколько раз. Аналогичный эффект будет, если писать определение сразу в заголовочном файле, не надо так.

К сожалению, у директивы #include есть несколько нюансов.

Предотвращение повторного включения.

Давайте поговорим про структуры. Что будет, если мы в заголовочном файле создадим struct, и подключим этот файл? Да ничего. Абсолютно ничего. Сгенерированный ассемблерный код будет одинаковым. У структур нет определения по сути, потому что они не генерируют код. Поэтому их пишут в заголовках. При этом их методы можно (но не нужно) определять там же, потому что они воспринимаются компилятором как inline. А кто такой этот inline и как он работает — смотри дальше. Но со структурами есть один нюанс. Рассмотрим вот что:

// x.h:
struct x {};

// y.h:
#include "x.h"

// z.h:
#include "x.h"

// a.cpp:
#include "y.h" //    -->    `struct x{};`.
#include "z.h" //    -->    `struct x{};` ошибка компиляции, повторное определение.

Стандартный способ это поправить выглядит так:

// x.h:
#ifndef X_H // Если мы уже определили макрос, то заголовок целиком игнорируется.
#define X_H	// Если не игнорируется, то помечаем, что файл мы подключили.

struct x {};

#endif // В блок #ifndef...#endif заключается весь файл целиком.

Это называется include guard. Ещё все возможные компиляторы поддерживают #pragma once (эффект как у include guard, но проще). И на самом деле #pragma once работает лучше, потому что не опирается на имя файла, например. Но его нет в стандарте, что грустно.

Есть один нюанс с #pragma once'ом. Если у вас есть две жёстких ссылки на один файл, то у него проблемы. Если у вас include guard, то интуитивно понятно, что такое разные файлы — когда макросы у них разные. А вот считать ли разными файлами две жёстких ссылки на одно и то же — вопрос сложный. Другое дело, что делать так, чтобы источники содержали жёсткие или символические ссылки, уже довольно странно.

Forward-декларации.

// a.h
#ifndef A_H
#define A_H

#include "b.h" // Nothing, then `struct b { ... };`

struct a {
	b* bb;
};
#endif

// b.h
#ifndef B_H
#define B_H

#include "a.h" // Nothing, then `struct a { ... };`

struct b {
	a* aa;
};
#endif

// main.cpp
#include "a.h" // `struct b { ... }; struct a { ... };`
#include "b.h" // Nothing.

Понятно, в чём проблема заключается. Мы подключаем a.h, в нём — b.h, а в нём, поскольку мы уже зашли в a.h, include guard нам его блокирует. И мы сначала определяем структуру b, а потом — a. И при просмотре структуры b, мы не будем знать, что такое a.

Для этого есть конструкция, называемая forward-декларацией. Она выглядит так:

// a.h
#ifndef A_H
#define A_H

struct b;

struct a {
	b* bb;
};
#endif

// b.h
#ifndef B_H
#define B_H

struct a;

struct b {
	a* aa;
};
#endif

Чтобы завести указатель, нам не надо знать содержимое структуры. Поэтому мы просто говорим, что b — это некоторая структура, которую мы дальше определим.

Вообще forward-декларацию в любом случае лучше использовать вместо подключения заголовочных файлов (если возможно, конечно). Почему?

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

Пока структуру не определили, структура — это incomplete type. Например, на момент объявления struct b; в коде выше, b — incomplete. Кстати, в тот момент, когда вы находитесь в середине определения класса, он всё ещё incomplete. Все, что можно с incomplete типами делать — это объявлять функции с их использованием и создавать указатель. Incomplete тип становится полным типом после определения. Пока что информация об incomplete-типах нам ни к чему, но она выстрелит позже.

Правило единственного определения.

А теперь такой пример:

// a.cpp
#include <iostream>

struct x {
	int a;
	// padding
	double b;
	int c;
	int d;
};

x f();

int main() {
	x xx = f();
	std::cout << xx.a << " "
	          << xx.b << " "
	          << xx.c << " "
	          << xx.d << std::endl;
}

// b.cpp
struct x {
	int a;
	int b;
	int c;
	int d;
	int e;
};

x f() {
	x result;
	result.a = 1;
	result.b = 2;
	result.c = 3;
	result.d = 4;
	result.e = 5;
	return result;
};

Тут стоит вспомнить, что структуры при линковке не играют никакой роли, то есть линковщику всё равно, что у нас структура x определена в двух местах. Поэтому такая программа отлично скомпилируется и запустится, но тем не менее она является некорректной. По стандарту такая программа будет работать неизвестно как, а по жизни данные поедут. А именно 2 пропадёт из-за выравнивания double, 3 и 4 превратятся в одно число (double), а 5 будет на своём месте, а x::e из файла a.cpp будет просто не проинициализирован. Правило, согласно которому так нельзя, называется one-definition rule/правило единственного определения. Кстати, нарушением ODR является даже тасовка полей.

Inlining.

int foo(int a, int b) {
	return a + b;
}

int bar(int a, int b) {
	return foo(a, b) - a;
}

Если посмотреть на ассемблерный код для bar, то там не будет вызова функции foo, а будет return b;. Это называется inlining — когда мы берём тело одной функции и вставляем внутрь другой как оно есть. Это связано, например, со стилем программирования в текущем мире (много маленьких функций, которые делают маленькие вещи) — мы убираем все эти абстракции, сливаем функции в одну и потом оптимизируем что там есть.

Но есть один нюанс...

Модификатор `inline`.

// a.c
void say_hello();

int main() {
	say_hello();
}

// b.c
#include <cstdio>

void say_hello() {
	printf("Hello, world!\n");
}

Тут не произойдёт inlining, а почему? А потому что компилятор умеет подставлять тело функций только внутри одной единицы трансляции (так как inlining происходит на момент трансляции, а тогда у компилятора нет функций из других единиц).

Тут умеренно умалчивается, что модель компиляции, которую мы обсуждаем — древняя и бородатая. Мы можем передать ключ -flto в компилятор, тогда всё будет за'inline'ено. Дело в том, что при включенном режиме linking time optimization, мы откладываем на потом генерацию кода и генерируем его на этапе линковки. В таком случае линковка может занимать много времени, поэтому применяется при сборке с оптимизациями. Подробнее о режиме LTO — сильно позже.

Но тем не менее давайте рассмотрим, как без LTO исправить проблему с отсутствием inlining'а. Мы можем написать в заголовочном файле тело, это поможет, но это, как мы знаем, ошибка компиляции. Хм-м, ну, можно не только написать функцию в заголовочном файле, но и пометить её как static, но это даёт вам свою функцию на каждую единицу трансляции, что, во-первых, бывает просто не тем, что вы хотите, а во-вторых, кратно увеличивает размер выходного файла.

Поэтому есть модификатор inline. Он нужен для того, чтобы линковщик не дал ошибку нарушения ODR. Модификатор inline напрямую никак не влияет на то, что функции встраиваются. Если посмотреть на inline через nm, то там увидим W (weak) — из нескольких функций можно выбрать любую (предполагается, что все они одинаковые).

По сути inline — указание компилятору, что теперь за соблюдением ODR следите вы, а не он. И если ODR вы нарушаете, то это неопределённое поведение (ill-formed, no diagnostic required). ill-formed, no diagnostic required — это ситуация, когда программа некорректна, но никто не заставляет компилятор вам об этом говорить. Он может (у GCC есть такая возможность: если дать g++ ключи -flto -Wodr, он вам об этом скажет), но не обязан. А по жизни линковщик выберет произвольную из имеющихся функций (например, из первой единицы трансляции или вообще разные в разных местах):

// a.cpp
#include <cstdio>

inline void f() {
	printf("Hello, a.cpp!\n");
}

void g();

int main() {
	f();
	g();
}

// b.cpp
inline void f() {
	printf("Hello, b.cpp!\n");
}

void g() {
	f();
}

Если скомпилировать этот код с оптимизацией, обе функции f будут за'inline'ены, и всё будет хорошо. Если без, то зависит от порядка файлов: g++ a.cpp b.cpp может вполне выдавать Hello, a.cpp! два раза, а g++ b.cpp a.cpp — Hello, b.cpp! два раза.

Если нужно именно за'inline'ить функцию, то есть нестандартизированные модификаторы типа __forceinline, однако даже они могут игнорироваться компилятором. Inlining функции может снизить производительность: на эту тему можно послушать доклад Антона Полухина на C++ Russia 2017.

Остальные команды препроцессора.

#include обсудили уже вдоль и поперёк. Ещё есть директивы #if, #ifdef, #ifndef, #else, #elif, #endif, которые дают условную компиляцию. То есть если выполнено какое-то условие, можно выполнить один код, а иначе — другой.

Определение макроса.

И ещё есть макросы: определить макрос (#define) и разопределить макрос (#undef):

#define PI 3.14159265
double circumference(double r) {
    return 2 * PI * r;
}

Текст, который идет после имени макроса, называется replacement. Replacement отделяется от имени макроса пробелом и распространяется до конца строки. Все вхождения идентификатора PI ниже этой директивы будут заменены на replacement. Самый простой макрос — object-like, его вы видите выше, чуть более сложный — function-like:

#define MIN(x, y) x < y ? x : y

printf("%d", MIN(4, 5));

Что нам нужно про это знать — макросы работают с токенами. Они не знают вообще ничего о том, что вы делаете. Вы можете написать

#include <cerrno>

int main() {
	int errno = 42;
}

И получить отрешённое от реальности сообщение об ошибке. А дело всё в том, что это на этапе препроцессинга раскрывается, например, так:

int main() {
	int (*__errno_location()) = 42;
}

И тут компилятор видит более отъявленный бред, нежели называние переменной так, как нельзя.

Что ещё не видит препроцессор, так это синтаксическую структуру и приоритет операций. Более страшные вещи получаются, когда пишется что-то такое:

#define MUL(x, y) x * y

int main() {
	int z = MUL(2, 1 + 1);
}

Потому что раскрывается это в

int main() {
	int z = 2 * 1 + 1;
}

Это не то, что вы хотите. Поэтому когда вы такое пишите, нужно, во-первых, все аргументы запихивать в скобки, во-вторых — само выражение тоже, а в-третьих, это вас никак не спасёт от чего-то такого:

#define max(a, b) ((a) < (b) ? (a) : (b))

int main() {
	int x = 1;
	int y = 2;
	int z = max(x++, ++y);
}

Поэтому перед написанием макросов три раза подумайте, нужно ли оно, а если нужно, будьте очень аккуратны. А ещё, если вы используете отладчик, то он ничего не знает про макросы, зачем ему знать. Поэтому в отладчике написать «вызов макроса» Вы обычно не можете. См. также FAQ Бьярна Страуструпа о том, почему макросы — это плохо.

Ещё #define позволяет переопределять макросы.

#define STR "abc"
const char* first = STR; // "abc".
#define STR "def"
const char* second = STR; // "def".

Replacement макроса не препроцессируется при определении макроса, но результат раскрытия макроса препроцессируется повторно:

#define Y foo
#define X Y   // Это не `#define X foo`.
#define Y bar // Это не `#define foo bar`.
X             // Раскрывается `X` -> `Y` -> `bar`.

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

#define M { M }
M   // Раскрывается в { M }.

Ещё пример:

#define A a{ B }
#define B b{ C }
#define C c{ A }
A // a{ b{ c{ A } } }
B // b{ c{ a{ B } } }
C // c{ a{ b{ C } } }

Условная компиляция. Проверка макроса.

Директивы #ifdef, #ifndef, #if, #else, #elif, #endif позволяют отпрепроцессировать часть файла, лишь при определенном условии. Директивы #ifdef, #ifndef проверяют определен ли указанный макрос. Например, они полезны для разной компиляции:

#ifdef __x86_64__
typedef unsigned long uint64_t;
#else
typedef unsigned long long uint64_t;
#endif

Директива #if позволяет проверить произвольное арифметическое выражение.

#define TWO 2
#if TWO + TWO == 4
// ...
#endif

Директива #if препроцессирует свой аргумент, а затем парсит то, что получилось как арифметическое выражение. Если после препроцессирования в аргументе #if остаются идентификаторы, то они заменяются на 0, кроме идентификатора true, который заменяется на 1.

Одно из применений #ifndef — это include guard, которые уже обсуждались ранее.

Константы.

Понадобилась нам, например, $\pi$. Традиционно в C это делалось через #define. Но у препроцессора, как мы знаем, есть куча проблем. В случае с константой PI ничего не случится, вряд ли кто-то будет называть переменную так, особенно большими буквами, но всё же.

А в C++ (а позже и в C) появился const. Но всё же, зачем он нужен, почему нельзя просто написать глобальную переменную double PI = 3.141592;?

Во-первых, константы могут быть оптимизированы компилятором. Если вы делаете обычную переменную, компилятор обязан её взять из памяти (или регистров), ведь в другом файле кто-то мог её поменять. А если вы напишете const, то у вас не будет проблем ни с оптимизацией (ассемблер будет как при #define), ни с адекватностью сообщений об ошибках.
Во-вторых, она несёт документирующую функцию, когда вы пишете const с указателями. Если в заголовке функции написано const char*, то вы точно знаете, что вы передаёте в неё строку, которая не меняется, а если char*, то, скорее всего, меняется (то есть функция создана для того, чтобы менять).
В-третьих, имея const, компилятор может вообще не создавать переменную: если мы напишем return PI * 2, то там будет возвращаться константа, и никакого умножения на этапе исполнения.

Кстати, как вообще взаимодействует const с указателями? Посмотрим на такой пример:

int main() {
	const int MAGIC = 42;
	int* p = &MAGIC;
}

Так нельзя, это имеет фундаментальную проблему: вы можете потом записать *p = 3, и это всё порушит. Поэтому вторая строка не компилируется, и её надо заменить на

	const int* p = &MAGIC;

Но тут нужно вот на что посмотреть. У указателя в некотором смысле два понятия неизменяемости. Мы же можем сделать так:

int main() {
	const int MAGIC = 42;
	const int* p = &MAGIC;
	// ...
	p = nullptr;
}

Кто нам мешает так сделать? Да никто, нам нельзя менять содержимое p, а не его самого. А если вы хотите написать, что нельзя менять именно сам указатель, то это не const int*/int const*, а int* const. Если вам нужно запретить оба варианта использования, то, что логично, const int* const или int const* const. То есть

int main() {
	int* a;
	*a = 1;      // ok.
	a = nullptr; // ok.

	const int* b;       // Синоним `int const* b;`
	*b = 1;      // Error.
	b = nullptr; // ok.

	int* const c;
	*c = 1;      // ok.
	c = nullptr; // Error.

	const int* const d; // Синоним `int const* const d;`
	*d = 1;      // Error.
	d = nullptr; // Error.
}

Теперь вот на что посмотрим:

int main() {
	int a = 3;
	const int b = 42;

	int* pa = &a;        // 1.
	const int* pca = &a; // 2.
	int* pb = &b;        // 3.
	const int* pcb = &b; // 4.
}

Что из этого содержит ошибку? Ну, в третьем точно ошибка, это мы уже обсудили. Также первое и четвёртое точно корректно. А что со вторым? Ну, нарушает ли второе чьи-то права? Ну, нет. Или как бы сказали на парадигмах программирования, никто не нарушает контракт, мы только его расширяем (дополнительно обещая неизменяемость), а значит всё должно быть хорошо. Ну, так и работают неявные преобразования в C++, вы можете навешивать const везде, куда хотите, но не можете его убирать.

Константными могут быть и составные типы (в частности, структуры). Тогда у этой структуры просто будут константными все поля.

Классы, абстракция данных

Запись лекции y2019:

Запись лекции y2024:

TODO

Методы.

Как бы мы с нашими текущими знаниями реализовали структуру для комплексных чисел? Ну, как-то так:

struct complex {
	double re;
	double im;
};
void conjugate(complex* c) {
	c->im = -c->im;
}

Это корректный и хороший C'шный код. Но в C++ позволили писать функции внутри класса. Они, как в Java принимают неявный параметр this, который указатель на «себя». При этом this-> можно опустить везде, где он есть. То есть в C++ код выше был бы написан так:

struct complex {
	double re;
	double im;

	void conjugate() {
		im = -im;     // this->im = -this->im;
	}
};

Компилятор генерирует один и тот же код для программы в C'шном стиле и для программы в C++ стиле.

Также важный момент: когда вы хотите указать, что this имеет тип const complex* const (а не complex* const), вы пишете const после закрывающей скобки аргументов функции.

Вопрос: А зачем нам 2 разных варианта, в каких случаях мы хотим первый вариант, а в каких второй?

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

Немного про компиляцию классов.

Кстати. Можно написать сначала метод, а потом поля, это ни на что не влияет. Почему? А потому что компилятор откладывает разбор тел функций на конец класса. Но тут же возникает вопрос, почему так не делали с обычными функциями?

По историческим причинам. Когда у компьютеров было мало памяти, такие штуки компиляторы вообще никак не могли себе позволить. Поэтому по развитию GCC можно посмотреть, что сначала он оптимизировал только одну функцию за раз, потом только одну единицу трансляции, а теперь уже у нас есть LTO. Понятно, что если с LTO компилировать что-то огромное, вам нужно будет гигов этак двадцать.
Второй аргумент — хочется прекомпилировать заголовки. Прекомпиляция заголовков — это когда вы проходитесь по заголовку один раз, сохраняете состояние компилятора и потом загружаете его, чтобы не разбирать заголовок снова. И если бы заголовки зависели от того, что после них, такое было бы невозможно.

Кстати, это поясняет, почему методы можно определять сразу внутри класса. Ранее было упомянуто, что класс в середине его определения всё ещё считается incomplete type. Кажется, это должно запретить нам использовать класс в определении его методов. Но методы разбираются после класса, потому нет.

А вообще обычно пишут объявления функций в class.h, а определения в class.cpp. Если определение функции сделано внутри класса, то она неявно помечается как inline, но мы не всегда хотим этого (дольше время компиляции из-за зависимостей).

// struct.h:
struct complex {
	void conjugate();
private:
	double re;
	double im;
};

// struct.cpp:
void complex::conjugate() {
	im = -im;
}

Права доступа.

А в чём глобально разница между внешней функцией и методом? Ну, во внешнюю функцию можно передать nullptr, но это легко исправляется ссылками (см. дальше), они тоже не бывают nullptr. А вот что действительно важно — права доступа. Как и в Java, вы можете показывать и скрывать поля и методы класса ключевыми словами public и private соответственно: к public полям и методам могут обращаться все вообще, а к private — только методы того же класса. Ещё есть модификатор protected, он тоже как в Java, и о нём попозже. Итого такой код:

struct complex {
private:
	double re;
	double im;

public:
	void conjugate() {
		im = -im;
	}
};

Скомпилируется, а если сделать conjugate внешней функцией — то нет.

Что должно быть `private`, а что `public`? Инварианты класса.

На кой нам вообще private? А вот есть у вас двоичное дерево поиска:

struct node {
	node* left;
	node* right;
	node* parent;
	int value;
};

struct binary_search_tree{
    node *root;
};

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

if (left) assert(left->parent == this);
if (right) assert(right->parent == this);

for each node n in the left subtree:
    assert(n.value < value);
for each node n in the right subtree:
    assert(n.value > value);

Посмотрим еще например инвариант двусвязного списка:

struct node
{
	node* prev;
	node* next;
	int32_t value;
};

struct doubly_linked_list
{
	node* first;
};

В данном случае инвариант будет например:

assert(prev.next  == this);
assert(next.prev == this);

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

Инварианты класса, кстати, не всегда очевидны. Вот есть у вас дробь:

struct rational {
	int32_t num;
	int32_t denom;
};

Какой у неё инвариант? А вот есть два варианта:

denom != 0.
denom > 0 && gcd(num, denom) == 1.

Самое грустное, что оба варианта верны — в зависимости от выбора изменятся реализации функций. Например, в случае denom != 0 будет сложение попроще писать в коде, а сравнение посложнее. И, что грустно, зачастую понять инвариант вы можете только по коду (а код ещё и ошибки может содержать).

Поэтому полезно бывает в отладочных целях писать метод void check_invariant() const, после чего на тестировании вставлять его до и после каждого публичного метода. Была даже история о том, как чуваки взяли много проектов по красно-чёрным деревьям из GitHub, повставляли в них проверку инварианта и нашли кучу ошибок. А единственные проекты, где не нашли, уже содержали проверку. А дело в том, что красно-чёрное дерево может не сломаться полностью, если допустить в нём ошибку — вы можете ошибиться так, что оно всё ещё будет деревом поиска, всё ещё сможет добавлять и удалять элементы, но оно будет работать медленнее, чем должно теоретически, потому что будет неправильно покрашено. И в этом случае вам проверка инварианта и поможет.

Но есть грустный момент: иногда инвариант проверить невозможно. Скажем, мы пишем контейнер, у него должны быть capacity выделенных байт, первые size из которых проинициализированы. Ну, фиг мы это проверим. Мы можем теоретически написать какой-то умный аллокатор, который имеет проверку первого, а разломав компилятор сможем проверить второе. Но это никто делать не будет, увы:(

Теперь вернёмся к основному вопросу (для чего private)

Вспомним про структуру complex:

struct complex {
	double re;
	double im;
};

Можем ли мы делать в классе complex поля доступными всем? По идее да, ведь инвариант не меняется. Но мы можем хранить числа в полярной форме, а вещественную и мнимую часть считать в методах (полный кринж, но все же). Есть аргумент получше: компилятор GCC, например, имеет встроенные комплексные числа через ключевое слово __complex__. И использует в реализации std::complex он именно их, а не два double'а. К чему этот пример? Даже такая простая вещь, как комплексное число, может реализовываться разными вариантами. Поэтому есть распространенное явление - обычно все данные в классе делают private, для того, чтобы в случае чего поменять реализацию (даем простор для модификаций).

Проверять инварианты можно ассертами (assert), про них в отдельном файле будет.

Итого, модификаторы доступа нужны для:

защита инварианта класса
спрятать детали реализации, для дальнейших возможных модификаций

Конструкторы.

Все публичные методы класса предполагают, что инвариант выполнен до вызова, и после выхода из метода инвариант класса выполняется. Поэтому когда мы создаём новый объект, хотелось бы, чтобы он выполнялся с самого начала. Для этого есть специальные методы — конструкторы:

struct string {
private:
	char* data;
	size_t size;
	size_t capacity;
	/* Инвариант:
	 * 1) `capacity` байт выделено в `data`.
	 * 2) `size <= capacity` из них заполнено.
	 * 3) `data` — корректный указатель либо `nullptr` (если `capacity == 0`), data[0], data[size-1] инициализированы
	 */

public:
	// Вот это конструктор.
	// Он обеспечивает исполнение инварианта в начале.
	string() {
		data = nullptr;
		size = capacity = 0;
	}
};

Конструктор без аргументов называется конструктором по умолчанию. Конструкторы вызываются компилятором (и только им) всегда, когда вы создаёте объект. Вы можете явно указать, какой конструктор вызвать вот так:

struct complex {
private:
	double re;
	double im;

public:
	complex() {
		re = im = 0;
	}
	complex(double re, double im) {
		// Так называть параметры можно. Можно и ещё круче, но в разделе про списки инициализации.
		this->re = re;
		this->im = im;
	}
};
void main() {
	complex a1;
	complex a2();
	complex a3 = complex();
	complex a4{};

	complex b1(1, 2);
	complex b2 = complex(1, 2);
	complex b3{1, 2};
}

Первые 4 определения равносильны. Как и последние 3. Кстати, выражение вида complex(1, 2) может как оно есть в функцию передаваться — тогда создастся временный объект и передастся. Этот временный объект, кстати, является rvalue.

Теперь давайте внимательнее посмотрим на a3 и b2. Там мы вроде как сначала создаём объект, а потом присваиваем его куда-то. Так вот да, но нет. У компилятора есть такое понятие как избегание копирования: если правый аргумент — rvalue, то он ничего не копирует, а просто вызывает конструктор на a3/b2.

Есть синтак

Неявные конструкторы.

struct complex
{
private:
	double re;
	double im;

public:
	complex() { /*...*/ }
	complex(double re, double im) { /*...*/ }
	complex(double re) {
		this->re = re;
		this->im = 0;
	}
};

void foo(complex) { /*...*/ }

void main() {
	complex a = 42;
	foo(42.0);
}

Такой код неявно преобразует 42.0 в complex и вызовет от него функцию. В случае с complex это оправдано, но если у вас контейнер инициализируется количеством элементов, то так неявно делать странно. Поэтому если вы такого не хотите, напишите перед конструктором слово explicit: тогда вы запретите ещё complex a = 42, можно будет только complex a(42).

Деструкторы.

Помните struct string? Там же нам надо освободить данные при удалении объекта. А вот для конструкторов есть парные функции — деструкторы, которые автоматически вызываются, когда объект уничтожается:

struct string {
private:
	char* data;
	size_t size;
	size_t capacity;

public:
	// ...
	~string() {
		free(data);
	}
}

void foo() {
	string s;
} // Вызовется деструктор `s` при выходе из функции.

Когда происходит уничтожение?

Обычные переменные умирают когда наступает фигурная скобка блока, где вы объявили переменную. Совершенно не важно, каким образом вы покидаете блок, return у вас, break, throw или даже goto. Только если longjmp вы используете, тогда вы не знаете, вызовутся деструкторы или нет. Мораль — не используйте longjmp, потому что он всё равно корректно работает только вверх по стеку, а вверх по стеку можно заменить на throw-catch.
Временные объекты умирают по концу выражения, где они созданы.
Для глобальных переменных конструктор вызывается до main, а деструктор — после него.
Для полей класса конструктор вызывается до конструктора этого класса, а деструктор — после его деструктора.

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

Операторы.

Для класса complex очень хочется иметь арифметические операции, и не хочется как в какой-то помойной Java называть их add или mul. Чтобы так можно было, в C++ есть ключевое слово operator. Они пишутся как обычные функции, только называются как operator+, operator- и тому подобное.

Как и обычные функции, операторы могут быть внешними или внутренними (правда, не все):

complex operator+(complex a, complex b) {
	return complex(a.real() + b.real(), a.imag() + b.imag());
}

Или

class complex {
	// ...
	complex operator+(complex other) const {
		return complex(re + other.re, im + other.im);
	}
};

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

Если вы пишете оператор, то хотя бы один из его элементов должен быть пользовательским типом (нельзя переопределить оператор для int, int, но можно, например, для std::vector<int> и int).

Если есть желание почитать поподробнее, то почитайте cppreference.

Оператор `->`.

Особо нужно посмотреть на ->. Его обычно перегружают, когда пишут какие-то свои указатели. И выглядят это вот так:

struct my_ptr {
	// Что-то.
	complex* operator->() {
		return /* Что-то */;
	}
};

Можно было бы подумать, что -> — это бинарный оператор (у него есть то, у чего мы берём поле/метод и имя этого самого поля/метода). Но правая штука — это не выражение. В C++ нет рефлексии. Поэтому -> — это унарный оператор. Если вы возьмёте my_ptr x и вызовете x->im, то это преобразуется в (x.operator->())->im. Поскольку operator-> возвращает complex*, к нему нормально можно применить ->. А ещё можно из оператора -> вернуть что-то другое, к чему применим оператор ->. И тогда они будут вызываться по цепочке, пока не дойдём до обычного указателя.

Ссылки.

Операторы подводят нас к вопросу, что делать с += и подобными? Точнее, как перегрузить его вне класса? Совершенно точно не так:

void operator+=(complex a, complex b) {
	a.set_real(a.real() + b.real());
	a.set_imag(a.imag() + b.imag());
}

Есть идеологически неверное, но всё же рабочее решение:

void operator+=(complex* a, complex b) {
	a->set_real(a->real() + b.real());
	a->set_imag(a->imag() + b.imag());
}
int main() {
	complex x, y;
	&x += y;
}

Сделать такое можно, используя ссылки. О них можно думать, как о константных указателях со специальным синтаксисом:

T a;                         T a;

T* const ptr = &a;           T& ref = a;
foo(*ptr);                   foo(ref);
ptr->bar;                    ref.bar;

Ещё ссылки нельзя перенаправлять на другие объекты (раз уж это неизменяемый указатель), и ссылка не бывает nullptr, (ну, правда, зачем вам константный указатель на nullptr).

И теперь мы можем увидеть, как делать нужно:

complex& operator+=(complex &a, complex b) {
	return a = a + b;
}

Во всех присваиваниях (хоть =, хоть @=) возвращаемое значение — это левый аргумент, чтобы было консистентно со строенными типами.

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

//       Вот сюда смотреть:     vvvvv        v
complex& operator+=(complex &a, const complex& b) {
// Или так, смысл такой же:     complex const& b
	return a = a + b;
}

Если функция принимает const&, то в неё можно передавать временный объект (rvalue). Если же она принимает обычную ссылку, то только lvalue.
Также возвращая по ссылке, возвращаем lvalue, а по значению — rvalue.

Немного best practices (until C++23).

Сто́ит посмотреть, что делать, если вы реализуете свою строку. Вам хочется оператор []. По-хорошему он выглядит так:

struct string {
private:
	char* data;
	size_t size;
	size_t capacity;
public:
	// ...
	char& operator[](size_t index) {
		return data[index];
	}
};

Но на самом деле вы хотите вызывать этот оператор на неизменяемой строке тоже, а от неё указанный оператор не вызывается (нельзя кастовать const string* const this в просто string* const this). Поэтому вам придётся написать ещё один вариант этого же оператора:

	const char& operator[](size_t index) const {
		return data[index];
	}

Почему const char&, а не char? Чтобы от константности строки не зависело, lvalue у вас или rvalue. А const char& — это lvalue, у него есть адрес.

Продолжение темы операторов.

Перегрузка операторов внутри класса и снаружи.

Операторы можно перегружать как функции (снаружи класса) и как методы (внутри класса). Соответственно, у операторов, перегруженных как методы, первым аргументом будет неявный this.

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

struct complex {
	// ...
	/* implicit */ complex(double re) { /*...*/ }

	complex operator-(const complex& other) const {
	return complex(re - other.re, im - other.im);
}
};
complex operator+(const complex& a, const complex& b) {
	return complex(a.real() + b.real(), a.imag() + b.imag());
}
void main() {
	complex a;
	a + 42; // ok, operator+(a, 42).
	a - 42; // ok, a.operator+(42).
	42 + a; // ok, operator+(42, a).
	42 - a; // Error, `42.operator-(a)` у int нет методов.
}

Мораль: перегружайте операторы внешне. Если первый аргумент — это ваш тип, то проблема уже описана выше, а если не ваш, то внутренне его вообще не перегрузить.

Vector operator*(double d, Vector const& v);

Некоторые операторы необходимо перегружать только внутри класса: (type), [], (), ->, ->*, =. С ними не возникает проблем с конверсией первого аргумента (если вы хотите неявно преобразовывать аргумент этих операторов куда-то, что-то вы делаете не так). Но с присваиванием есть еще одна проблема.

struct complex {
	// ...
	complex& operator=(const complex& other) { /*...*/ }
};

complex foo() { /*...*/ }

int main() {
	foo() = complex(1, 2);
}

Бредятина какая-то. А дело в том, что никто не знает, что operator= должен принимать не временный объект первым аргументом. Если бы можно было перегрузить его внешне, то такой проблемы бы не было (там было бы явно указано complex& left). И эта проблема в C++11 правится так:

struct complex {
	// ...
	complex& operator=(const complex& other) & { /*...*/ }
	//          Вот сюда смотреть:           ^
};

Increment и decrement.

Кстати, надо сразу рассказать, как перегружать ++ и --, ведь у вас два таких. Тут синтаксический костыль — постфиксные операторы принимают второй аргумент int, который не используется. Неиспользуемый — dummy. Когда вызывается постфиксный оператор, всегда передаётся аргумент, хотя можно и вручную вызвать оператор как функцию и передать любое значение: a.operator++(2).

struct big_integer {
     big_integer& operator++() { // prefix
        // ...
        return *this;
     }
     big_integer operator++(int) { // postfix
        big_integer tmp(*this);
        ++(*this);
        return tmp;
     }
};

C-style cast.

struct string {
	// ...

	// Приведение к `bool`.
	operator bool() const {
		return size_ != 0;
	}

	// Приведение к `char const*`.
	operator char const*() const {
  		if (*this) { // Тут используется приведение к `bool`.
    		return data_;
    	} else {
    		return "";
   	 	}
	} 
}

У операторов приведения, как и у конструкторов, можно указывать модификатор explicit и запрещать неявное приведение.

Некоторые ограничения:

Операторы &&, || при перегрузке теряют своё специальное поведение и ведут себя как обычные функции.
Операторы += и подобные лучше перегружать внутри класса, а + снаружи через +=. Тогда для + будет работать приведение типов. При этом любое присваивание выглядит так: T& T::operator@=(const T& other) &;
Операторы сравнений стоит определять одновременно и согласованно: если определили какой-то один из них, принято определить и все остальные так, чтобы они не противоречили друг другу. При этом принято, чтобы сингнатуры у них были одинаковые. Так, либо ни одна, либо все должны быть noexcept.
Хорошим тоном считается соблюдать стандартный смысл операторов: не перегружать оператор + как умножение.
Приоритет операторов остаётся стандартным.
Перегружать операторов, которых нет изначально, нельзя.
Перегружать ::, ?:, . и .* нельзя.

Special function member функции.

Копирование и присваивание.

Давайте посмотрим на такой код:

int main() {
    string s = "Hello";
    string t = s;
}

Wait a second, мы же не написали как строки копировать. Почему компилятор их копирует? И самое главное, как? А вот покомпонентно. Если покомпонентно нас не устраивает (а в данном случае не устраивает, потому что мы два раза освободим скопированный указатель), надо написать свой конструктор копирования. И в пару ему оператор присваивания, который легко пишется из предыдущего:

string& operator=(string other) & {
//Внимание!       ^^^ копия ^^^
    std::swap(other, *this); // Как работает std::swap, оставим за кадром. Пока что.
    return *this;
}

Это называется swap-trick, и его мы ещё обсудим в контексте исключений. Кстати, оператор присваивания также генерируется компилятором. Также покомпонентный. То, что компилятор генерирует сам, называется специальными функциями-членами класса. Это:

Метод	Когда генерируется	Что делает по умолчанию
Конструктор по умолчанию	Не написан ни один конструктор	Конструирует по умолчанию все поля
Деструктор	Не написан деструктор	Удаляет все поля
Копирующий конструктор	Не написан копирующий конструктор	Инициализирует объект копиями всех полей
Оператор присваивания	Не написан оператор присваивания	Присваивает всем полям поля того, что присваиваем

`= default;` и `= delete;`.

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

my_string& operator=(my_string const&) = delete;
my_string(my_string const&) = delete;

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

my_string() = default;

Так ещё может быть полезно писать, чтобы явно документировать, что функция-член класса вам подходит.

Отличается ли чем-то пустой конструктор от дефолтного? А вот да: пустой конструктор — это user-defined конструктор. Класс с default конструктором — это trivially constructible. Для них, например, при создании массива не будут вызываться конструкторы.

Если = default писать в определении в какой-нибудь из единиц трансляции, то другие единицы трансляции во время компиляции не будут знать, что класс trivially constructible.

Списки инициализации.

Посмотрим вот на что:

struct string {
    // ...
    string() {
        data = strdup("");
        size = capacity = 0;
    }
    string(const char* str) { /*...*/ }
    string(const string& other) { /*...*/ }
    string& operator=(const string& other) & { /*...*/ }
    ~string() {
        free(data);
    }
};
struct person {
    string name;
    string surname;
    person() {
        name = "Eric";
        surname = "Adams";
    }
};
int main() {
    person p;
}

Сколько тут будет аллокаций и деаллокаций памяти? А вот 6. Почему? Давайте аккуратно считать.

0. Мы вызываем конструктор класса person.
2. У двух string'ов вызывается конструктор по умолчанию, каждый из которых выделает память (strdup).
4. Неявно вызываются конструкторы string("Eric") и string("Adams"), которые тоже выделяют память.
6. Два раза выполняется присваивание, которые выделяют и освобождают память.

Можно ли это оптимизировать? Компилятор теоретически может, конечно, но срабатывают эти оптимизации настолько редко и ненадёжно, что надеяться на них нельзя. Как это оптимизировать программисту? При помощи списков инициализации — хочется указать, что мы сразу вызываем конструктор name и surname от строки, а не по-умолчанию. Это делается при помощи такого синтаксиса:

struct person {
    string name;
    string surname;
    person() : name("Eric"), surname("Adams")
    {}
};
int main() {
    person p;
}

И тут аллокаций будет 2, как и ожидается. Кстати, если есть объект, который не имеет конструктора по-умолчанию, то без списков инициализации просто невозможно.

Что сто́ит сказать про это? А то что списки инициализации — это не только (и не столько) оптимизация, сколько по смыслу не то же самое, что мы написали сначала. Только для встроенных типов разницы особой нет, но вообще списки инициализации обычно и для них используются, потому что это гораздо более идиоматический код. А ещё сто́ит сказать, что если в списке инициализации не написано ничего для некоторого поля, то для него используется конструктор по-умолчанию.

Поскольку деструктор у нас один, разрушаются поля в определённом порядке. А в конструкторе вы, вроде как, можете в разном написать. Так вот нет, потому что список инициализации всегда вызывает конструкторы в порядке расположения полей структуры. И лучше бы вам писать список инициализации в этом же порядке, чтобы не путать людей. И, кстати, в инициализации некоторого поля можно использовать то, что было создано ранее. Аналогично с использованием this в списке инициализации — можно, но осторожно, надо понимать, что конструктор this ещё недовыполнился. Аналогично осторожным быть надо в деструкторе по той же причине. Подробнее про порядок инициализации здесь.

Кроме того, конструкторы можно делегировать:

person() : person("Ivan", "Sorokin") {}

Сначала вызовется конструктор от двух char const*, а затем будет выполнять тело текущего конструктора.

Ещё немного best practices.

Давайте вот ещё на что посмотрим. Наш класс string вызывает в конструкторе по умолчанию аллокацию памяти. Так вот, вообще считается, что это кринж, так делать не надо.

А ещё при присваивании C-строки в нашу строку мы сначала конструируем, а потом присваиваем, давайте вместо этого явно пропишем operator=(const char*), и будет также меньше аллокаций.

`new` и `delete`.

Итак, мы обсудили, когда вызываются конструкторы и деструкторы. А если вы хотите вызывать их в произвольный момент, конструируя объект тогда, когда захочет пользователь? Тогда есть new и delete. Вы пишете Type* p = new Type(...); — это конструирует вам объект в куче, а delete p; разрушает вам этот объект.

Как это работает? В C есть malloc и free, они выделяют память на куче в тот момент, когда вы её попросите (опять же, в рандомный момент). Выделение на куче, кстати, немного дороже, чем на стеке.

    void* p = malloc(42); // Выделяет 42 байта.
    free(p); // Чистит память, выделенную ранее.
    free(p); // Освобождать то, что уже освободил, нельзя.

    free(nullptr); // Так можно, ничего не произойдет.

Двойной free вызывает UB или даже уязвимость.

Разница между ними и new—delete (упрощённо) в том, что второй вариант гарантирует вызов конструкторов и деструкторов. И в большинстве new просто является комбинацией из malloc'а и вызова конструктора на выделенной памяти. Аналогично delete вызывает деструктор и free.

Ещё есть new[] и delete[] — менеджмент массива. На всём массиве вызываются конструкторы по умолчанию:

person* p = new person("Ivan", "Sorokin");
delete p;

person* p = new person[10];
delete[] p;

При этом ни в коем случае нельзя освобождать объект другим способом, нежели он был выделен. Это в любом случае undefined behaviour, даже если, вроде как, не должно быть:

person* p = new person("Ivan", "Sorokin");

p->~person();
free(p);

Идиома PImpl

Представим, что у нас есть большой проект/библиотека и мы хотим как-то изменить заголовочный файл. Тогда надо перекомпилировать все файлы, которые зависят от него. А это будет занимать много времени, ведь даже при небольших изменениях приходится ждать, пока всё перекомпилируется. На помощь приходит идиома PImpl, которая позволяет отделить интерфейс класса от его реализации. Её идея в том, чтобы перенести приватные поля в отдельный класс и обращаться к ним через указатель. Пример:

// container.h
struct Container {
public:
    Container(size_t size);
    Container(const Container &other);

    ~Container();

    size_t size();

private:
    struct Impl;
    std::unique_ptr<Impl> pimpl;
};

// container.cpp 
struct Container::Impl {
    Impl(size_t size) : size(size){}
    size_t size;
};

Container::Container(size_t size) : pimpl(new Impl(size)) {}
Container::~Container() = default;
Container::Container(const Container &other) : pimpl(new Impl(*other.pimpl)) {}
size_t Container::size() {
    return pimpl->size;
}

//main.cpp 
int main() {
    Container c;
}

Теперь все изменения будут вноситься в container.cpp и пользователю не надо перекомпилировать другие единицы трансляции — только перелинковаться.

Мы вынесли деструктор. А что будет, если так не сделать? Будет ошибка компиляции в main.cpp. При генерации дефолтного деструктора Container будет инстанцироваться деструктор unique_ptr<Impl>, который в свою очередь вызывает деструктор Impl, но Impl в этот момент incomplete, а значит непонятно, какой код генерировать в деструкторе unique_ptr<Impl>.

Примеры кода на ассемблере

На этой практике мы потрогаем ассемблер.

Hello World

Справа вы можете видеть код:

section .text
global _start

_start:
    mov rax, 1
    mov rdi, 1
    mov rsi, msg
    mov rdx, msg_size
    syscall

    mov rax, 60
    xor rdi, rdi
    syscall

section .rodata
msg: db "Hello, world!", 0x0a
msg_size: equ $ - msgbash

Давайте сперва покажем, как компилировать программу на ассемблере:

nasm -felf64 hello.asm

nasm - сам компилятор, -felf64 - формат кодирования для 64-битного линукса и название файла.

Теперь, если вы заметите, то у вас появился файл hello.o - объектный файл.

Чтобы создать файлик, который мы можем запускать, мы должны написать:

ld hello.o

ld - ссылочный компилятор, hello.o - объектный файл, который мы создали ранее. Пока вы не знаете, что это такое, но позже по курсу узнаете. Так вот, эта команда создаст файл a.out, который уже можно будет запустить и он выведет наш "Hello, World".

Теперь давайте говорить про код:

В этом коде мы видим section:

Исполняемые файлы в нынешнее время большинство имеют отдельное место под код (условно говоря .text), отдельное место для неизменяемой памяти (.rodata) и другие.
Когда наша программа компилируется, она будет запускаться из функции _start.
global _start нужен для того, чтобы линковщик мог к ней обратиться (иначе файл бы не запустился, т.к. не видел бы начало программы).
Мы распихиваем с помощью mov в какие-то регистры какие-то числа, а потом делаем syscall. Что делает syscall? Просит ядро операционной системы вызвать какую-то команду в зависимости от значения на регистре rax. Какую вы можете посмотреть сюда: Linux_System_Call_Table (https://en.wikipedia.org/wiki/System_call#Linux_kernel)

Когда мы хотим сделать какой-то системный вызов, мы читаем rax и в зависимости от него делаем команду.
Рассмотрим эту часть кода:
```
mov rax, 1
mov rdi, 1
mov rsi, msg
mov rdx, msg_size
syscall
```
Что у нас происходит? Мы кладем в rax - 1, откуда это команда write, потом в rdi кладем 1, в rsi кладем указатель на сообщение, а в rdx передаем msg_size, как от нас и требуется по Linux_System_Call_Table и вызываем syscall.

И мы побеждаем!

Вот мы и разобрали весь код HelloWorld. Это очень простой пример, но он показывает основные концепции ассемблера.

Подсчет новых строк в тексте

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

section .text
global _start

SYS_EXIT: equ 60
SYS_WRITE: equ 1
STDOUT: equ 1
BUFFER_SIZE: equ 4096
EXIT_FAILURE: equ 1

_start:
    sub rsp, BUFFER_SIZE   ; Создаем место на стеке для буфера
    xor ebx, ebx           ; Вводим регистр, который будет считать количество новых строчек
    mov rsi, rsp           ; И ставим указатель на место в буфере в регистр rsi 
.read_loop:
    xor eax, eax           ; Очищаем rax, чтобы подготовиться к вызову системного вызова sys_read
    xor edi, edi           ; Устанавливаем дескриптор файла (STDIN) для системного вызова sys_read
    mov rdx, BUFFER_SIZE   ; Устанавливаем размер буфера (BUFFER_SIZE) для системного вызова sys_read
    syscall                ; Считываем BUFFER_SIZE байт из stdin  на адрес выделенный памяти (rsi)
    ; syscall возвращает в регистр rax количество байт, которые он считал. 
    ;Подробнее читайте в документации на Linux_System_Call_Table

    test rax, rax          ; Проверяем, вернул ли sys_read 0 (EOF)
    jz .quit               ; Если да, переходим к .quit
    js .error              ; Если вернул отрицательное значение - что-то сломалось
    ; Поэтому надо перейти в .error

    xor ecx, ecx           ; Очищаем rcx
                           ; Сейчас у нас в коде будет что-то типо цикла:
                           ; for(rcx = 0; rcx < rax; rcx++) 
.count_newlines:
    cmp byte [rsp + rcx], 0x0a  ; Сравниваем текущий символ с символом перехода строки
    jne .skip                   ; Если не равны, переходим к .skip
    inc rbx                     ; Если равны, увеличиваем счетчик переводов строки (rbx)
.skip:
    inc rcx                     ; Увеличиваем счетчик цикла (rcx)
    cmp rcx, rax                ; Сравниваем счетчик цикла с количеством прочитанных байт
    jb .count_newlines          ; Если меньше, переходим обратно к .count_newlines

    jmp .read_loop             ; Переходим обратно к .read_loop, чтобы прочитать еще данные

.quit:
    ; Сюда мы попадаем, когда выходим из цикла и все данные прочитаны корректно
    ; Теперь нам осталось вывести наше число в десятичном виде
    mov rax, rbx               ; Перемещаем счетчик переводов строк (rbx) в rax для деления
    lea rcx, [write_buffer + write_buffer_size - 1]  
    ; Устанавливаем адрес буфера (rcx) для записи результата
    mov byte [rcx], 0x0a       ; Добавляем символ новой строки в конец буфера
    mov rbx, 10                ; Устанавливаем основание для деления (rbx) в 10

.print_num:
    xor edx, edx               ; Очищаем rdx, чтобы подготовиться к делению
    div rbx                    ; Делим rax на rbx
    add rdx, '0'               ; Преобразуем остаток в ASCII
    dec rcx                    ; Уменьшаем адрес буфера (rcx)
    mov byte [rcx], dl         ; Сохраняем ASCII-символ в буфер
    test rax, rax              ; Проверяем, является ли частное число 0
    jnz .print_num             ; Если нет, переходим обратно к .print_num

    mov rax, SYS_WRITE         ; Устанавливаем номер системного вызова для sys_write
    mov rdi, STDOUT            ; Устанавливаем дескриптор файла (STDOUT) для sys_write
    mov rsi, rcx               ; Устанавливаем адрес буфера (rcx) для sys_write
    lea rdx, [write_buffer + write_buffer_size]  ; Устанавливаем размер буфера для sys_write
    sub rdx, rcx               ; Вычисляем количество байт для записи
    syscall                    ; Выводим результат на экран

    mov rax, SYS_EXIT          ; Устанавливаем номер системного вызова для sys_exit
    xor rdi, rdi               ; Устанавливаем статус выхода (0) для sys_exit
    syscall                    ; Выходим

.error:
    ; О нет, вы проиграли
    mov rax, SYS_WRITE         ; Устанавливаем номер системного вызова для sys_write
    mov rdi, STDOUT            ; Устанавливаем дескриптор файла (STDOUT) для sys_write
    mov rsi, err_msg           ; Устанавливаем адрес сообщения об ошибке (err_msg) для sys_write
    mov rdx, err_msg_len       ; Устанавливаем длину сообщения об ошибке (err_msg_len) для sys_write
    syscall

    mov rax, SYS_EXIT          ; Устанавливаем номер системного вызова для sys_exit
    mov rdi, EXIT_FAILURE      ; Устанавливаем статус выхода (EXIT_FAILURE) для sys_exit
    syscall

section .rodata
err_msg: db "Read Error", 0x0a  ; Сообщение об ошибке для системного вызова sys_write
err_msg_len: equ $ - err_msg    ; Длина сообщения об ошибке

section .bss
write_buffer_size: equ 21      ; Размер буфера для записи результата
write_buffer: resb write_buffer_size  ; Буфер для записи результата

Данную практику писал Чепелин Вячеслав. Скопирован файл Алисы с нашей практики и на нем объяснен код

Работа с файлами C++. Введение.

На прошлой домашке мы поработали с syscall в линуксе. А сейчас хочется писать кросс - платформенный код.

Мы пользовались: sys_read(fd, buffer, size)

Сегодня мы будем говорить про файловые комманды. Например про:

Примеры комманд вывода:

write

Например если пользоваться пользовательскими вызовами:

#include <unistd.h>

int main() {
    const char(&arr)[6] = "hello";
    const char * str = arr;
    write(1, str, 5);
}

Данная программа выведет hello.

fwrite

#include <cstdio>

int main() { 
    // Используем std::fwrite для вывода строки "hello"
    // 1-й аргумент: указатель на данные для записи
    // 2-й аргумент: размер каждого элемента (1 байт для char)
    // 3-й аргумент: количество элементов для записи (5 символов)
    // 4-й аргумент: поток вывода (stdout для вывода на консоль)
    std::fwrite("hello", 1, 5, stdout);
}

Еще один пример использования std::fwrite:"

    int arr[] = {'a','b','c'};
    std::fwrite(&arr, sizeof(int), std::size(arr), stdout);

Важно отметить, что строки в C и C++ обычно нультерминированы. Это означает, что в конце строки стоит символ '\0' (нулевой байт). Этот нулевой символ служит признаком конца строки.

Например, строковый литерал "hello" на самом деле занимает 6 байт в памяти: 'h', 'e', 'l', 'l', 'o', '\0'. Как мы и писали ранее.

#include <cstdio>
#include <iterator>

int main() {
    int arr[] = {'a' * 256 + 'z', 'b', 'c'};
    std::fwrite(&arr, sizeof(int), std::size(arr), stdout);
}

Оно выведет za b c, из-за политики little-endian у нас z выведится первым, так и должно быть.

fputs, puts

signed main() {
    std::fputs("hello\n",stdout);
}

У него есть аналог puts - выводит в stdout. При этом puts добавляет еще перенос строки.

Примеры комманд ввода:

fread

size_t fread(void* ptr, size_t size, size_t count, FILE* stream);

Параметры:

ptr: указатель на блок памяти, в который будут записаны прочитанные данные.
size: размер каждого элемента в байтах.
count: количество элементов, которые нужно прочитать.
stream: указатель на объект FILE, представляющий файл, из которого читаются данные.

"hello"; //not const char*
         //const char(&)[6]

Примеры кода:

Вывод из ввода консоли:

#include <cstdio>

int main(int argc, char **argv) {
    for (int i = 0; i < argc; i++) {
        std::puts(argv[i]);
    }
}

Это программа при вводе aboba aboba aboba выведет:

path\practice1.exe
aboba aboba aboba

Причина, по которой программа выводит "path\practice1.exe" в первой строке, заключается в том, что имя файла и путь к нему включаются в аргументы командной строки при запуске программы. Конечно, какой-то плохой человек может передать 0 аргументов, но на то это и плохой человек :)

Это гарантируется вызовом execve, можете в мануале про него почитать.

Прочитать из файлика и построчно вывести:

#include <cstdio>

int main(int argc, char **argv) {
    std::FILE *fd = std::fopen(argv[1], "r");
    int current = std::fgetc(fd);
    while (current != EOF) {
        std::putchar(current);
        current = std::fgetc(fd);
    }
    return 0;
}

Лучше писать return 0 в конце программы.

Но теперь наша программа может вылетать с ошибками, обработаем их:

#include <cstdio>

int main(int argc, char **argv) {
    if (argc != 2) {
        std::fputs("Wrong number of arguments\n", stderr);
        return 1;
    }

    const char *file_path = argv[1];

    std::FILE *fd = std::fopen(file_path, "r");
    if (fd == nullptr) {
        std::fprintf(stderr, "Could not open file: %s\n", file_path);
        /*
        Или аналогично:
        std::fputs("No such file:", stderr);
        std::fputs(file_path, stderr);
        std::fputs("\n", stderr);
        */
        return 1;
    }
    int current = std::fgetc(fd);
    while (current != EOF) {
        std::putchar(current);
        current = std::fgetc(fd);
    }

    if (std::ferror(fd)) {
        std::fputs("Read error\n", stderr);
        std::fclose(fd);
        return 1;
    }
    std::fclose(fd);
    return 0;
}

Что делать если fclose завершился с ошибкой - вопрос философский.

Но теперь у нас слабенькие выводы ошибок, давайте поменяем:

#include <cstdio>
#include <cstring>
#include <cstdlib>


int main(int argc, char **argv) {
    if (argc != 2) {
        std::perror("Wrong number of arguments\n");
        return EXIT_FAILURE;
    }

    const char *file_path = argv[1];

    std::FILE *fd = std::fopen(file_path, "r");
    if (fd == nullptr) {
        std::fprintf(stderr, "Could not open file: %s: %s\n", file_path, std::strerror(errno));
        return EXIT_FAILURE;
    }
    int current = std::fgetc(fd);
    while (current != EOF) {
        std::putchar(current);
        current = std::fgetc(fd);
    }

    if (std::ferror(fd)) {
        std::perror("Read error\n");
        std::fclose(fd);
        return EXIT_FAILURE;
    }
    std::fclose(fd);
    return EXIT_SUCCESS;
}

Совпадение содержимого файла со строчкой

#include <cstdio>
#include <cstring>
#include <memory>

int main(int argc, char **argv) {
    // Проверка правильного количества аргументов
    if (argc != 3) {
        std::fprintf(stderr, "Expected 2 arguments, got %d\n", argc - 1);
        return 1;
    }

    const char *filename = argv[1];  // Имя файла из первого аргумента
    std::FILE *f = std::fopen(filename, "r");  // Открытие файла для чтения
    if (!f) {
        std::fputs("File not opened!\n", stderr);
        return 1;
    }

    bool equals = true;  // Флаг совпадения содержимого
    const char *const pattern = argv[2];  // Строка для сравнения из второго аргумента
    size_t len = std::strlen(pattern);  // Длина строки для сравнения

    // Посимвольное сравнение содержимого файла со строкой
    for (size_t i = 0; i < len; ++i) {
        int c = std::fgetc(f);  // Чтение символа из файла
        if (c == EOF) {  // Если достигнут конец файла раньше времени
            equals = false;
            break;
        }
        unsigned char cc = static_cast<unsigned char>(c);
        char ccc = static_cast<char>(cc);
        if (ccc != pattern[i]) {  // Если символы не совпадают
            equals = false;
            break;
        }
    }

    // Проверка на ошибки чтения
    if (std::ferror(f)) {
        std::fputs("Error while reading\n", stderr);
        std::fclose(f);
        return 1;
    }

    // Проверка, что файл не содержит дополнительных символов
    if (std::fgetc(f) != EOF) {
        equals = false;
    }

    // Вывод результата
    std::fputs(equals ? "Yes\n" : "No\n", stdout);

    std::fclose(f);  // Закрытие файла
    return 0;
}

Данную практику писал Чепелин Вячеслав. Скопирован файл Артема и Льва с нашей практики и на нем объяснен код

Структура --- обертка над данными Класс --- обратная тема.

class Matrix
{
    Matrix(size_t rows, size_t cols)
        : _rows(rows)
        , _cols(cols)
        , _data(new int[rows*cols])
    {}
private:
    size_t _rows;
    size_t _cols;
    int* _d

Приватные чаще называют как-то необычно:

rows_
_rows
m_rows

Надо добавить деструктор

    ~Matrix()
    {
        delete[] _data;
    }

Заполним нулями и тогда наш класс выглядит

class Matrix {
    Matrix(size_t rows, size_t cols)
            : _rows(rows), _cols(cols), _data(new int[rows * cols]{}) {}

    ~Matrix() {
        delete[] _data;
    }


private:
    size_t _rows;
    size_t _cols;
    int *_data;
};

Хотим дефолтный конструктор. Обычно дефолтный конструктор ничего не аллоцирует. Поэтому:

Matrix() : _rows(0), _cols(0), _data(nullptr) {}

Можно подумать, что нам надо менять деструктор из-за nullptr. Но нам не надо менять его, ведь delete проверяет на nullptr.

Хочу member функции:

копирование
присваивание

Matrix(const Matrix &other) : _rows(other._rows), _cols(other._cols), _data(new int[_rows * _cols]) {
        for (size_t i = 0; i < _rows * _cols; i++) {
            _data[i] = other._data[i];
        }
    }

 Matrix &operator=(const Matrix &other) {
        if (this == &other) { // взятие внутрь
            return *this;
        }

        delete[] _data;
        _rows = other._rows;
        _cols = other._cols;
        _data = new int[_rows * _cols];
        for (size_t i = 0; i < _rows * _cols; i++) {
            _data[i] = other._data[i];
        }

        return *this;
    }

Парадигмы программирования

Информация о курсе:

Поток - y2024
Группы М3132 - М3139
Преподаватель -- Корнеев Георгий Александрович

2 семестр

Основной конспект.

Clojure Basics

Основы

Везде, где можно поставить пробел, можно поставить и запятую

(println "Hello, Clojure!")

(println (+ 1 2 3 4))
(println (type 1))
(println (type 1/2))
(println (type 1.45))

(println (not "hello"))
(println (not nil))
(println (not false))

Данный код выведет:

Hello, aboba228!
10
java.lang.Long
clojure.lang.Ratio
java.lang.Double
false
true
true

Тут есть аналог больших чисел:

(println (+ 10N 20N))                                       ; Big Int тип

Функции и переменные

(def add +)                                               ; умеем задавать
(println (add 10 20 30))


; def - специальная форма
(def x (* 30 40))                                           ; переменная
(println x)

(defn square [x] (* x x))                                   ; функция
(println (square x))

(println ((fn [x] (+ x x)) 10))                             ; функции могут быть анонимными

(defn twice [f] (fn [x] (f (f x))))                         ; функции могут быть от функций
(println ((twice square) 10))
(println (#(+ %1 %2) 10 30))

Рекурсия

(defn rec-fib [n]
  (cond (== 0 n) 1
        (== 1 n) 1
        :else (+ (rec-fib (- n 1)) (rec-fib (- n 2)))       ; сюда вместо else можно написать арбуз
        )
  )
(println (mapv rec-fib (range 1 10)))

Как и ожидается данная функция будет работать, как числа фиббоначи.

(def rec-fib2
  (fn [n] (cond (== 0 n) 1
                (== 1 n) 1
                :else (+ (rec-fib2 (- n 1)) (rec-fib2 (- n 2)))
                ))
  )
(println (mapv rec-fib2 (range 1 10)))

Улучшим и теперь наша функция будет сохранять результат вычислений

(def rec-fib3
  (memoize (fn [n] (cond (== 0 n) 1N
                         (== 1 n) 1N
                         :else (+ (rec-fib3 (- n 1)) (rec-fib3 (- n 2)))
                         ))
           ))
(println (mapv rec-fib3 (range 1 10)))
(println (rec-fib3 100))

memoize внутри себя честно кеширует. Но у нас стек заканчивается и тильт

Всякие приколы

(defn iter-fib' [n a b]
  (if (== 0 n)
    a
    (iter-fib' (- n 1) b (+' a b)))
  )

(defn iter-fib [n]
  (iter-fib' n 1 1))

(println (mapv iter-fib (range 1, 10)))

Мы можем это заменить

(defn iter-fib [n]
  (letfn [(rec [n a b]
     (if (== 0 n)
       a
       (recur (- n 1) b (+' a b))))]
  (rec n 1 1)))

(println (mapv iter-fib (range 1, 10)))

Синтаксический сахар

(defn iter-fib [n']
  (loop [n n' a 1 b 1]
     (if (== 0 n)
       a
       (recur (- n 1) b (+' a b)))))

(println (mapv iter-fib (range 1, 10)))

Pred Post

(defn power
  "Raises a to b-th power"
  [a,b]
  {:pre[(<= 0 b)]
   :post[(or (== b 0) (zero? a) (zero? (mod % a)))]}
  (cond
    (zero? b) 1
    (even? b) (power (* a a) (quot b 2))
    (odd? b) (* a (power a (dec b)))
    )
  )
(println (power 2 10))

Стандартная библиотека

(list 10 20 30)
(list? (list 10 20 30)) ; предикат для списка
(count (list 10 20 30)) ; 3

Это список. Бывает пустой. Круглые скобки - пустой

Листы реализованы связными списками.

[10 20 30] ; вектор
(count [10 20 30]) ; 3

Есть пару веселых функций:

(conj [10 20 30] 100 200) ; => [10 20 30 100 200]

Вектор ведет себя как стек, лист как стек сначала.

(mapv) честно вернет вектор от того, что вы просили

(identity 30) ; => 30

((constatly 30) 34892312 213512 3120913) => 30

((comp square inc) 10) ; обычная композиция

Лекция 2

Мы умеем вводить из консоли:

(defn hello []
  (let [input (read-line)]
    (println "Hello, " input)))
(hello)
;Aboba228
;Hello,  Aboba228

Умеем много вводить из консоли:

(defn hello []
  (let [input (read-line)]
    (if (= "." input) nil
                      (do (println "Hello, " input) (recur)))))
(hello)
; hello
; Hello,  hello
; clojure
; Hello,  clojure
; .
;
; Process finished with exit code 0

Умеем считать более умные штуки:

(defn rsum []
  (loop [sum 0]
    (let [input (read-line)]
      (if (= "." input)
        sum
        (let [sum' (+ sum (read-string input))]
          (println "sum = " sum')
          (recur sum')
          )
        ))
    ))
(rsum)
; 10
; sum =  10
; 20
; sum =  30
; 30
; sum =  60
; .

; Process finished with exit code 0

Вот так произвольные штуки

(defn io [f input output]
  (spit output (f (slurp input))))

Пользоваться иожем так:

(io (fn [input] (apply str (mapv #(str "Hello, " % "\n") (clojure.string/split-lines input))))
    "data/hello.in"
    "data/hello.out"
    )
; "hello.in"
; Aboba 
; hi hi
; 
; "hello.out"
; Hello, Aboba  
; Hello, hi hi

(type (read-string "10")) ;Java.lang.Long
(type (read-string "(+ 10 x (* x y))")) ;clojure.lang.PersistentList
(mapv type (read-string "(+ 10 x (* x y))")) ;clojure.lang.Symbol java.lang.Long clojure.lang.PersistentList

read-string читает в кложурские формы

'y - обозначает символ y

(def expr (read-string "(+ 10 x (* x y))"))
(def x 10)
(def y 20)
(eval expr) ;220
(def y 200)
(eval expr) ;2020

(defn trace [value]
    (println "\t\t" value)
    value)
(defn add [x y]
    (trace "add")
    (+ x y ))
(add (trace 10) (trace 20))
; 10
; 20
; add
; Аппликативный порядок
(defn add [x y]
    (trace "add")
    (+ (eval x) (eval y) ))
(add '(trace 10) '(trace 20))
;add 
;10
;20 
; оно может несколько раз считать одно и то же
; Нормальный порядок

; Есть ленивый порядок!
(defn add [x y]
    (trace "add")
    (+ (force x) (force y) ))
(add (delay(trace 10)) (delay(trace 20)))

ГК: сейчас мы будем наглеть

;мы ушли в свой неймспейс ks
(defn cons [h t] [h t])
(defn first [[h t]] h)
(defn rest [[h t]] (force t))
(def empty nil)
(defn empty? [stream] (= empty stream))
(defn count [stream]
    (if (empty? stream) 0) 0 (inc (count (rest stream))))
(defn to-list [stream]
    (if (empty? stream) () 
    (c/cons (first stream)
    (to-list (rest stream))
    ))
)
(defn map [f stream]
    (if (empty? stream) empty)
    (c/cons (f (first stream))
        (map (rest stream))
        ) 
    )
(defn filter [p? stream]
(if (empty? stream) empty 
    (let [tail (filter p? (rest stream))] 
    (if (p? (first stream))
        (cons (first stream) tail)
        tail))))

(defn take [n stream]
    (cond (empty? stream) empty 
          (pos? n) (cons (first stream) (take (dec n) (rest stream)))
          :else empty))

(defn take-while [p? stream]
    (cond (empty? stream) empty 
          (p? (first-stream)) (cons (first stream) (take-while p? (rest stream)))
          :else empty))

(defn some [p? stream]
    (cond (empty? stream) false 
          (p? (first-stream)) true
          :else (some p? (rest stream))))

(defn every [p? stream]
    (cond (empty? stream) true
          (p? (first-stream)) (every p? (rest stream))
          :else false))

Создадим всякие приколы:

(def ones (ks/cons  1 (delay ones)))

(defn ints [n]
    (ks/cons s (ints (inc n))))

Получили бесконечную структуру данных!

(def primes 
    letfn(prime? [n]
          (not (ks/some #(zero? (mod n %) )
            (ks/take-while #(>= n (* % %)) primes)
          )))
          (ks/cons 2 (ks/filter prime? (ints 3))))
; ГК забыл делей у функций в  cs
(def lazy-ints [n] (lazy-seq n (lazy-ints (inc n))))

(def primes 
    letfn(prime? [n]
          (not (some #(zero? (mod n %) )
            (take-while #(>= n (* % %)) primes)
          )))
          (lazy-seq 2 (filter prime? ())))

(apply vector (take 30 primes ))

Есть отображение:

{"x" 1 "y" 2}
(type {"x" 1 "y" 2}) ; clojure.lang.PersistentArrayMap
(map? {"x" 1 "y" 2}) ; true
(empty? {"x" 1}) ;false
(contains? {"x" 1} "x") ; true
(contains? {"x" 1} "y") ; false
(contains? {"x" 1} 1) ; false
(count {"x" 1 "y" 2}) ; 2
(get {"x" 1 "y" 2} "x") ;1
(get {"x" 1 "y" 2} "z") ;nil
(keys {"x" 1 "y" 2} ) ; (x y)
(vals {"x" 1 "y" 2}) ; (1 2)
(assoc {"x" 1 "y" 2} "z" 3) ; добавило z
(assoc {"x" 1 "y" 2} "z") ; убавило я

Объекты на clojure

JavaScript - style

(def point {:x 10 :y 20})

(def spoint {:prototype point :dx 1 :dy 2 :y 200})

Пока магии нет. Сделаем магию:

(defn proto-get
  "Returns object property respecting the prototype chain"
  ([this key] (proto-get this key nil))
  ([this key default]
   (cond
     (contains? this key) (this key)
     (contains? this :prototype) (proto-get (this :prototype) key default)
     :else default)))

Теперь магия работает.

(def point {
    :x 10 
    :y 20
    :getX (fn [this] (proto-get this :x))
    :getY (fn [this] (proto-get this :y))
    :setX (fn [this value] (assoc this :x value))
    :setY (fn [this value] (assoc this :y value))
    :add (fn [this a b] ( + a b))})
(def spoint {
    :prototype point 
    :dx 1 
    :dy 2
    :getX (fn [this] (+ (proto-get this :x) (proto-get this :dx)))
    :getY (fn [this] (+ (proto-get this :y) (proto-get this :dy)))
    })

(defn proto-call
  "Calls object method respecting the prototype chain"
  [this key & args]
  (apply (proto-get this key) this args))

Синтаксис выглядит не самым хорошим образом. JS-like objects.

(defn field
  "Creates field"
  [key] (fn
          ([this] (proto-get this key))
          ([this def] (proto-get this key def))))

(defn method
  "Creates method"
  [key] (fn [this & args] (apply proto-call this key args)))

(defn constructor
  "Defines constructor"
  [ctor prototype]
  (fn [& args] (apply ctor {:prototype prototype} args)))

Если честно, то это выглядит очень страшно и этим настолько страшно пользоваться, что я не хочу это

(section "Syntactic sugar")

(example "Field declaration"
         (defn field
           "Creates field"
           [key] (fn
             ([this] (proto-get this key))
             ([this default] (proto-get this key default)))))
(example "Method declaration"
         (defn method
           "Creates method"
           [key] (fn [this & args] (apply proto-call this key args))))
(example "Fields"
         (def __x (field :x))
         (def __y (field :y))
         (def __dx (field :dx))
         (def __dy (field :dy)))
(example "Methods"
         (def _getX (method :getX))
         (def _getY (method :getY))
         (def _setX (method :setX))
         (def _setY (method :setY))
         (def _add (method :add)))

(example "Points"
         (def point
           {:x 10
            :y 20
            :getX __x
            :getY __y
            :setX (fn [this x] (assoc this :x x))
            :setY (fn [this y] (assoc this :y y))
            :add (fn [this a b] (+ a b))
            })
         (def shifted-point
           {:prototype point
            :dx 1
            :dy 2
            :getX (fn [this] (+ (__x this) (__dx this)))
            :getY (fn [this] (+ (__y this) (__dy this)))
            }))
(example "Fields usage"
         (__x point)
         (__x shifted-point)
         (__dx shifted-point)
         (__dx point 100))
(example "Methods usage"
         (_getX point)
         (_getX shifted-point)
         (_getX (_setX shifted-point 1000))
         (_add shifted-point 2 3))


(section "Constructors")

(example "Constructor declaration"
         (defn constructor
           "Defines constructor"
           [ctor prototype]
           (fn [& args] (apply ctor {:prototype prototype} args))))

(example "Supertype"
         (declare _Point)
         (def _distance (method :distance))
         (def _length (method :length))
         (def _sub (method :sub))
         (def PointPrototype
           {:getX __x
            :getY __y
            :sub (fn [this that] (_Point (- (_getX this) (_getX that))
                                         (- (_getY this) (_getY that))))
            :length (fn [this] (let [square #(* % %)] (Math/sqrt (+ (square (_getX this)) (square (_getY this))))))
            :distance (fn [this that] (_length (_sub this that)))
            })
         (defn Point [this x y]
           (assoc this
             :x x
             :y y))
         (def _Point (constructor Point PointPrototype)))

(example "Subtype"
         (def ShiftedPointPrototype
           (assoc PointPrototype
             :getX (fn [this] (+ (__x this) (__dx this)))
             :getY (fn [this] (+ (__y this) (__dy this)))))
         (defn ShiftedPoint [this x y dx dy]
           (assoc (Point this x y)
             :dx dx
             :dy dy
             ))
         (def _ShiftedPoint (constructor ShiftedPoint ShiftedPointPrototype)))

(example "Instances"
         (def point (_Point 10 20))
         (def shifted-point (_ShiftedPoint 10 20 1 2))
         (_getX point)
         (_getX shifted-point)
         (__x point)
         (__x shifted-point)
         (__dx shifted-point)
         (_length (_Point 4 3))
         (_sub (_Point -1 -2) (_Point 2 2))
         (_distance (_Point -1 -2) (_Point 2 2)))

Java style

Интерфейсы:

(definterface IPoint
  (^Number getX [])
  (^Number getY []))

Имплементация:

(deftype JPoint [x y]
  IPoint
  (getX [this] (.-x this))
  (getY [this] (.-y this)))
(deftype JShiftedPoint [x y dx dy]
  IPoint
  (getX [this] (+ (.-x this) (.-dx this)))
  (getY [this] (+ (.-y this) (.-dy this))))


(def point (JPoint. 10 20))
point
(type point)
(def shifted-point (JShiftedPoint. 10 20 1 2))
shifted-point
(type shifted-point)

CT Notes y2024