1Архитектура от А до Я

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

┌─────────────────────────────────────────────────┐
│  Пользователь:  m.insert({1, "hello"})           │  ← публичный API
└─────────────────────────────────────────────────┘
                       ▼
┌─────────────────────────────────────────────────┐
│  cpp_lab::MapTree<K, T, Tree, Compare>            │
│  Фасад: at, operator[], try_emplace,             │
│         insert_or_assign + проброс <using>        │
└─────────────────────────────────────────────────┘
                       ▼ (private inheritance)
┌─────────────────────────────────────────────────┐
│  cpp_lab::RBTree<K, T, C>  ИЛИ  AVLTree<K, T, C>   │
│  Конкретные алгоритмы балансировки:              │
│  emplace, link_and_fix, unlink_and_fix,          │
│  rotate_left, rotate_right                       │
└─────────────────────────────────────────────────┘
                       ▼ (public CRTP)
┌─────────────────────────────────────────────────┐
│  tree_detail::OrderedTreeBase<Derived,...>        │
│  Общий API: begin/end, find, insert, erase,      │
│  extract, merge, swap, copy/move/= default       │
└─────────────────────────────────────────────────┘
                       ▼
┌─────────────────────────────────────────────────┐
│  tree_detail::TreeIterator<V, IsConst>            │
│  ++, --, *, ->, паспорт итератора                │
└─────────────────────────────────────────────────┘
                       ▼
┌─────────────────────────────────────────────────┐
│  tree_detail::NodeBase                           │
│  parent / left / right / is_header               │
│        ▲                  ▲                      │
│        │                  │                      │
│  Node<Value>        (value)                       │
│        ▲                  ▲                      │
│        │                  │                      │
│  RBNode (red)      AVLNode (height)              │
└─────────────────────────────────────────────────┘

1.1 Полный путь m.insert({1, "hello"})

Разберу весь путь по шагам — от самого вызова до того, что в итоге вернётся пользователю.

1.2 Полный путь m[5] = "hello"

1.3 Полный путь m.erase(5)

2Теория · то, что реально гоняют на защите

2.1 Шаблоны (templates)

Что это. Шаблон — это образец, по которому компилятор автоматически генерирует конкретный код под нужные типы. Один код — работает с int, string, твоим классом.

Чем шаблон отличается от макроса

• Макрос — тупая текстовая подстановка препроцессором, без проверки типов. Можно подсунуть что угодно — потом ошибки в странных местах.
• Шаблон — компилятор полностью разбирает описание шаблона: проверяет типы, перегрузки, корректность операций. Ошибка вылезет понятная (хоть и многословная).

Шаблонные параметры — что бывает

• Тип: template<typename T> — самое частое. Подставляется тип.
• Константа времени компиляции (non-type): template<int N>. Так делают, например, факториал — см. бонусные задачи.
• Шаблон шаблона (template template): template<template<typename> class C>. У тебя в MapTree так передаётся Tree.
• Variadic: template<typename... Args> — пакет произвольного числа типов.

template <typename T1, typename T2, typename T3>
struct Triple {
    T1 first;
    T2 second;
    T3 third;
};

Triple<int, int, int> point = {-1, 3, 2};
Triple<std::string, std::string, int> words = {"hi", "world", 42};

Компилятор генерирует ДВЕ никак не связанные структуры — это разные типы.

Специализация шаблона

• Полная — указываются ВСЕ параметры: template<> void max<int>(...). Работает для функций и классов.
• Частичная — указываются НЕ ВСЕ параметры. Работает только для классов, для функций — ошибка function template partial specialization is not allowed.

Шаблонные классы и методы

Методы шаблонного класса тоже шаблонные. Можно описывать вне класса:

template <typename T1, typename T2, typename T3>
struct Triple {
    T1 first;  T2 second;  T3 third;
    T1 sum();
};

template <typename T1, typename T2, typename T3>
T1 Triple<T1, T2, T3>::sum() {
    return first + second + third;
}

Дружественные функции

friend внутри шаблонного класса даёт указанной функции доступ к private/protected. У тебя в коде friend Base; в RBTree — позволяет базе вызывать твои приватные методы (reinsert, erase_one, detach).

Затрудняют ли шаблоны разработку?

1. Ошибки многословные и диагностируются не там, где сделаны, а в шаблоне.
2. Сложно писать разные реализации для разных категорий типов (приходится использовать SFINAE, концепты).

Как работают шаблоны при компиляции и линковке

Шаблон — это рецепт, а не код. Реальный код появляется на этапе компиляции, когда шаблон инстанцируется (подставляются конкретные типы).

1. Компиляция .cpp: при каждом vector<int>, vector<string> компилятор генерирует отдельный код этого класса.
2. Несколько .cpp видят один шаблон → дубликаты: если в a.cpp и b.cpp есть vector<int>, оба сгенерируют этот класс. На этапе линковки линкер должен слить их в один (через специальный механизм — weak symbols или comdat sections).
3. Поэтому шаблоны живут в .h-файлах: иначе один .cpp не увидит определение шаблона. Если хочешь вынести в .cpp — нужна явная инстанциация: template<> int max<int>(int, int);

2.2 Категории значений · lvalue / rvalue / xvalue / prvalue / glvalue

В современном C++ каждое выражение имеет: тип + категорию значений.

             expression
            /          \
       glvalue         rvalue
        /    \         /    \
    lvalue  xvalue  xvalue  prvalue
   'имею    'вот-   (общее с
    адрес'  вот     glvalue,
            умру'   но движимое)

lvalue (locator value, «локативное значение»)

Имеет имя, имеет адрес в памяти, продолжает жить.

int var;       // var — lvalue
var = 4;        // слева может стоять только lvalue
std::string name = "Alice";  // name — lvalue

// Функция, возвращающая lvalue-ссылку:
int& foo() { return globalvar; }
foo() = 10;     // OK: foo() — lvalue, ему можно присваивать

prvalue (pure rvalue, «чистое rvalue»)

Временное, без идентичности. Литералы, результаты операций, временные объекты.

42, true, nullptr            // все — prvalue
str.substr(1, 2)              // результат функции по значению — prvalue
int x + 1                     // результат арифметики — prvalue

// нельзя:
4 = var;     // ERROR: prvalue не может быть слева от =
&42;          // ERROR: нет адреса у prvalue

xvalue (eXpiring value, «истекающее»)

Временный объект, который вот-вот умрёт, но ИМЯ всё ещё имеет. Получается из std::move(x) и при возврате rvalue-ссылки из функции.

std::string s = "hello";
std::move(s);   // xvalue: имя есть (s), но компилятор понимает
                // "хозяин обещал больше им не пользоваться, можно красть"

Двойной амперсант && — rvalue-ссылка

Привязывается только к rvalue. Это «приёмник временного, у которого можно забрать ресурсы».

Где в твоей лабе видно

// tree_base.h:447-448
std::pair<iterator, bool> insert(const value_type& v);  // для lvalue → копия
std::pair<iterator, bool> insert(value_type&& v);       // для rvalue → move

// std::move — преобразует свой аргумент в xvalue:
m.insert(std::move(pair));   // идёт во вторую перегрузку

2.3 Правило 5 · правило 3 · правило 0

Что это и что объединяет

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

Где что лучше

• Правило 0 — идеал. Большинство классов должны его использовать, потому что современные стандартные контейнеры сами всё умеют.
• Правило 3 — старый C++ или классы без move-семантики (легаси-код). Работает, но теряет оптимизации move.
• Правило 5 — правильный путь для классов, владеющих ресурсами (память, файлы, сокеты). Это твой случай — дерево владеет узлами в куче.

Почему у нас правило 5, а не 3

• Без move-конструктора std::vector<MapTree> при росте будет копировать деревья (медленно, может быть в 100 раз дольше). С move — крадёт содержимое за O(1).
• Без noexcept-move стандартные контейнеры всё равно выберут копирование. Поэтому noexcept на move-операциях обязателен.

Что объединяет правило 5

Все пять методов отвечают на один вопрос: «как мой объект создаётся, копируется и уничтожается». Это полный жизненный цикл объекта. Они объединены тем, что обрабатывают владение ресурсами.

Где в твоём коде

// tree_base.h:370-418  (база)
OrderedTreeBase() noexcept(...);                                // 1. default-ctor
OrderedTreeBase(const OrderedTreeBase& o);                    // 2. copy-ctor
OrderedTreeBase(OrderedTreeBase&& o) noexcept(...);            // 3. move-ctor
~OrderedTreeBase();                                              // 4. dtor
OrderedTreeBase& operator=(const OrderedTreeBase& o);          // 5. copy=
OrderedTreeBase& operator=(OrderedTreeBase&& o) noexcept(...);  // 6. move=

Связанные именованные требования

• CopyConstructible — есть копи-конструктор, создающий независимую копию.
• CopyAssignable — есть operator=(const T&).
• MoveConstructible — есть move-конструктор, оставляющий источник в «valid but unspecified» состоянии.
• MoveAssignable — есть operator=(T&&).
• Destructible — есть деструктор, корректно освобождающий ресурсы.

Это те самые имена, которые проверяет твой раздел TEST(NAMED_REQS, ...) в тестах.

2.4 this и как его скопировать без лямбды

Что такое this

this — это указатель на текущий объект внутри метода класса. В нестатических методах он всегда неявно есть. Через него ты обращаешься к полям и методам.

class A {
    int x;
    void show() {
        std::cout << this->x;   // явно
        std::cout << x;         // эквивалентно
    }
};

Тип this

• В обычном методе: A*
• В const-методе: const A*

Поэтому если ты в const-методе пытаешься менять поля — ошибка: «нельзя через const A*».

Где в твоей лабе видно

// tree_base.h:262  (CRTP-каст)
Derived& self() noexcept {
    return *static_cast<Derived*>(this);
    // this имеет тип OrderedTreeBase*,
    // мы кастуем его до RBTree* (наследник),
    // разыменовываем и возвращаем как ссылку
}

// tree_base.h:401  (защита от self-assignment)
OrderedTreeBase& operator=(const OrderedTreeBase& o) {
    if (this != &o) { ... }   // сравниваем адреса — мы не сами себе?
}

Как скопировать this без лямбды

Вопрос намекает на захват this в лямбде. Без лямбды есть три способа:

class A {
    int x = 5;

    void copy_self_1() {
        A copy = *this;          // 1) разыменовать и присвоить
                                  // вызовется копи-конструктор
    }

    void copy_self_2() {
        A copy(*this);          // 2) явное конструирование
    }

    void copy_self_3() {
        auto copy = this;        // 3) скопировать УКАЗАТЕЛЬ
                                  // (это не копия объекта, а копия адреса!)
    }
};

Тут нюанс: «скопировать this» может означать две разные вещи:

• Скопировать сам объект (всё, на что указывает this): A copy = *this;
• Скопировать указатель: A* ptr = this;

2.5 Итераторы

Что такое и зачем

Итератор — это обобщённый «палец», указывающий на элемент контейнера. Через него STL-алгоритмы работают с любым контейнером, не зная его внутренней структуры. Это превращает проблему N×M (N контейнеров × M алгоритмов) в N+M.

Пять категорий — от слабого к сильному

Какой у тебя — bidirectional

В коде это явно объявлено:

// tree_base.h:111
using iterator_category = std::bidirectional_iterator_tag;

Почему не random access? Потому что в дереве элементы НЕ лежат подряд в памяти. Прыгнуть на «5-й справа» нельзя за O(1) — пришлось бы делать 5 шагов.

Паспорт итератора

5 обязательных using-полей, по которым STL-алгоритмы понимают, что с итератором можно делать:

using iterator_category = std::bidirectional_iterator_tag;
using value_type        = Value;
using difference_type   = std::ptrdiff_t;
using reference         = Value&;     // или const Value& у const_iterator
using pointer           = Value*;

Без них алгоритмы STL твой итератор не примут.

2.6 Лямбды

Что это

Лямбда — это анонимный объект-функция, который можно объявить прямо в месте использования. Под капотом компилятор превращает её в класс с operator().

Полный синтаксис

[capture-list] (args) specifiers exception -> return-type { body }

• capture-list — что захватываем из окружения (по копии [=], по ссылке [&], конкретные переменные).
• args — аргументы, как у функции.
• specifiers — например, mutable (разрешает менять захваченные по копии переменные).
• exception — например, noexcept.
• return-type — обычно компилятор сам выводит (как auto).

Лямбда == класс

// Лямбда:
[]() { std::cout << "Hello" << std::endl; }

// Компилятор разворачивает в:
class __Lambda1234 {
public:
    auto operator()() const {
        std::cout << "Hello" << std::endl;
    }
};

У лямбды:

• Есть конструкторы по правилу 5.
• НЕТ операторов присваивания.
• Есть operator() — вызов функции.
• Если ничего не захватывает — можно сконвертировать в указатель на функцию.

Способы захвата

int i = 10;

[] {};            // без захвата
[i] {};           // i по копии
[&i] {};          // i по ссылке
[=] {};           // всё что использую — по копии
[&] {};           // всё — по ссылке
[=, &i] {};       // всё по копии, кроме i — по ссылке
[this] {};        // захватить указатель на объект
[*this] {};       // (C++17) захватить КОПИЮ объекта

Где можно использовать

• Аргумент алгоритма: std::sort(v.begin(), v.end(), [](auto a, auto b){return a>b;});
• Предикат: std::find_if, std::count_if, твой erase_if.
• Колбэк в асинхронном коде, у потоков, в GUI.
• Локальная мини-функция внутри другой функции (как в OrderedTreeBase::swap — лямбда fix чинит указатели).
• Сохранить в переменной через std::function.

std::function — обёртка над лямбдой

std::function<int(int, int)> func;
func = flag ? [](int a, int b) { return a + b; }
            : [](int a, int b) { return a - b; };
func(2, 3);   // 5 или -1 в зависимости от флага

Лямбда в твоём коде

// tree_base.h:572  в swap
auto fix = [](NodeBase& h) noexcept {
    if (!h.parent) h.left = h.right = &h;
    else h.parent->parent = &h;
};
fix(header_);
fix(o.header_);

2.7 std::less, функторы, компараторы, предикаты

Что такое функтор (FunctionObject)

Это объект с перегруженным operator(), который можно вызвать как функцию. Это именованное требование C++ называется FunctionObject.

В STL есть готовые функторы в <functional>:

• Арифметические: plus, minus, multiplies, divides, modulus, negate
• Логические: logical_and, logical_or, logical_not
• Сравнения (предикаты): equal_to, not_equal_to, less, greater, less_equal, greater_equal

Что такое предикат

Это функтор, возвращающий bool. Используется как «условие» в алгоритмах. std::less — бинарный предикат «меньше».

Что сравнивает std::less

Два значения через <. По умолчанию используется ассоциативными контейнерами для упорядочения ключей:

template <class T>
struct less {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

Особенности std::less

• Требует, чтобы у типа был operator<.
• Является «строгим частичным порядком» (strict weak ordering) — нужно для деревьев и сортировок.
• В C++14 появилась специализация std::less<void> = transparent comparator, может сравнивать разные типы.

Пример своего компаратора

// Сравнение строк без учёта регистра
struct CaseInsensitiveLess {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char x, char y) {
                return std::tolower(x) < std::tolower(y);
            });
    }
};

// Использование:
MapTree<std::string, int, RBTree, CaseInsensitiveLess> m;
m["Hello"] = 1;
m["hello"];          // тот же ключ, потому что регистр игнорируется

Использование std::greater

// сортировка по убыванию через предикат
std::sort(v.begin(), v.end(), std::greater<int>());

// твой тест с обратным MapTree
MapTree<int, int, RBTree, std::greater<int>> m;

2.8 using, typedef, typename

typedef (старый способ)

typedef unsigned long long u64;
u64 x = 42;

using (новый способ, с C++11)

using u64 = unsigned long long;
u64 x = 42;

using лучше, потому что:

• Читается слева направо: «using имя = тип».
• Может быть шаблонным (typedef не может!): template<typename T> using Vec = std::vector<T>;

using ещё используется для импорта имён из namespace

using cpp_lab::MapTree;
using std::cout;
using namespace std;  // импортировать ВЕСЬ namespace (не рекомендуется в .h)

using для проброса методов в private-наследовании

class MapTree : private RBTree {
    using base::begin;   // делает begin публичным методом MapTree
    using base::end;
};

typename — зачем

Используется внутри шаблонов, чтобы сказать компилятору: «вот это — тип, а не значение». Компилятор не может догадаться сам, потому что зависит от параметров шаблона.

template <typename Container>
void foo() {
    typename Container::iterator it;
    // без typename компилятор не знает,
    // iterator — это тип или статическое поле
}

Где у тебя в коде

// MapTree.h:21-37 — массовый проброс из базы
using typename base::iterator;
using typename base::value_type;
using typename base::size_type;
// ...

// MapTree.h:53-78 — проброс методов
using base::begin;
using base::end;
using base::find;
// ...

2.9 BST, AVL, RB

BST (Binary Search Tree) — двоичное дерево поиска

Для любого узла: в левом поддереве — меньшие ключи, в правом — бо́льшие. Это правило выполняется рекурсивно для всех узлов.

            [50]
           /    \
        [30]    [70]
        /  \    /  \
     [20] [40][60] [80]

Дает O(log n) поиск, вставку, удаление — при условии что дерево сбалансировано. Если вставлять ключи по возрастанию — дерево вырождается в список, и операции становятся O(n).

AVL-дерево

Названо по фамилиям советских математиков Адельсон-Вельский и Ландис (1962). Балансируется строго по высоте: разница высот левого и правого поддерева не больше 1.

• Хранит в узле: int height
• Высота ≤ 1.44·log(n+2) — почти идеально сбалансировано
• При вставке/удалении — балансируется через одинарные или двойные вращения
• Поиск чуть быстрее RB; вставка/удаление медленнее
• Применение: базы данных, индексы с редкими изменениями

Red-Black tree (красно-чёрное дерево)

Балансируется через цвета (Байер 1972, Гибас-Седжвик 1978).

5 правил RB:

1. Каждый узел красный или чёрный.
2. Корень всегда чёрный.
3. NIL-листы (nullptr) считаются чёрными.
4. У красного узла НЕТ красных детей (нет двух красных подряд).
5. От любого узла до его NIL-потомков на всех путях — одинаковое число чёрных узлов.

          50
         /    \
     30      70
     /  \     /  \
   20 40 60 80

• Хранит в узле: bool red
• Высота ≤ 2·log(n+1) — чуть менее идеально
• Меньше вращений → быстрее вставка/удаление
• Применение: std::map, std::set, JVM TreeMap, ядро Linux (планировщик CFS)

Сравнение

2.10 Все способы удалить узел в BST

Три классических случая. Тот же алгоритм применяется в AVL и в RB (с последующей балансировкой).

Случай 1 — у узла НЕТ детей (лист)

   до:                 после удаления [40]:

      [30]                   [30]
      /  \                   /
   [20] [40]              [20]

Просто отцепляем узел от родителя, родителю выставляем nullptr в соответствующее поле.

Случай 2 — у узла ОДИН ребёнок

   до:                 после удаления [40]:

      [30]                    [30]
      /  \                    /  \
   [20] [40]              [20] [45]
            \
            [45]

Ребёнок поднимается на место удаляемого узла.

Случай 3 — у узла ДВА ребёнка (сложный)

Нельзя просто отцепить — куда тогда деть детей? Находим successor — минимум правого поддерева (это «следующий по порядку» ключ). Заменяем удаляемый узел на него.

   до:                            после удаления [50]:

        [50]                            [60]
       /    \         successor         /  \
    [30]   [70]       это [60]       [30]  [70]
           /  \       (min справа)          \
        [60]  [80]                          [80]

Где в твоём коде

• RBTree: в unlink_and_fix — все три случая в одной функции через переменные y и x. Если узел чёрный — добавочный цикл с «двойным чёрным».
• AVLTree: в erase_target. Случаи 1-2 — одной строкой (возвращает уцелевшего ребёнка). Случай 3 — через erase_min для поиска successor + перенос.

Дополнительный сценарий — extract

В C++17 есть extract: узел отцепляется от структуры, но НЕ удаляется физически. Его можно положить в другой контейнер через node_handle. У тебя это делается через detach — тот же unlink_and_fix, но без delete.

3Любимые вопросы Богдана

int x = 5;       // x — lvalue
std::string s;    // s — lvalue
arr[3];           // элемент массива — lvalue
foo();            // если foo возвращает T& — lvalue

42;              // литерал — prvalue
x + 1;           // результат арифметики — prvalue
foo();            // если foo возвращает T — prvalue
std::move(x);    // xvalue (rvalue с именем)

struct NodeBase {                    // базовый — только связи
    NodeBase* parent = nullptr;
    NodeBase* left = nullptr;
    NodeBase* right = nullptr;
    bool is_header = false;
};

template<typename Value>
struct Node : NodeBase {              // + поле value
    Value value;       // pair<const Key, T>
};

template<typename Value>
struct RBNode : Node<Value> {        // + цвет
    bool red = true;
};

template<typename Value>
struct AVLNode : Node<Value> {       // + высота
    int height = 1;
};

A copy = *this;        // разыменовать и присвоить → копи-ctor
A copy(*this);         // явное конструирование

A* ptr = this;          // просто копия указателя

void foo(const std::string& s);   // для lvalue → копируем
void foo(std::string&& s);        // для rvalue → крадём

foo(name);                    // 1-я перегрузка (name — lvalue)
foo("hello");                 // 2-я перегрузка (литерал — prvalue)
foo(std::move(name));         // 2-я перегрузка (xvalue)

// лямбда
int y = 10;
auto f = [y](int x) { return x + y; };

// компилятор разворачивает в:
class __Lambda1234 {
    int y;
public:
    __Lambda1234(int y_) : y(y_) {}
    int operator()(int x) const { return x + y; }
};

template <typename T>
struct my_less {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

// Использование с std::sort:
std::vector<int> v = {5, 2, 8, 1};
std::sort(v.begin(), v.end(), my_less<int>());
// результат: 1, 2, 5, 8

struct ByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size();
    }
};

MapTree<std::string, int, RBTree, ByLength> m;
m["a"] = 1;       // длина 1
m["hi"] = 2;      // длина 2
m["hello"] = 3;   // длина 5
// упорядочено по длине ключа

template<typename T>
class vector { ... };

vector<int> v;

template<template<typename> class Container>
class Adapter {
    Container<int> data;   // Container — это шаблон,
                          // его ещё надо инстанцировать
};

Adapter<vector> a;     // vector — шаблон, не конкретный тип

template<typename Key, typename T,
         template<typename, typename, typename> class Tree,
         typename Compare = std::less<Key>>
class MapTree : private Tree<Key, T, Compare> { ... };

// max.cpp
template<> int max<int>(int a, int b);
template<> float max<float>(float a, float b);

    [30]            [30]
    /  \    →       /
 [20] [40]        [20]   (удалили 40)

    [30]             [30]
    /  \             /  \
 [20] [40]    →    [20] [45]   (удалили 40)
         \
         [45]

      [50]                  [60]
     /    \                 /  \
  [30]   [70]    →       [30]  [70]   (удалили 50)
         /  \                    \
      [60] [80]                  [80]

using u64 = unsigned long long;
using Map = std::map<int, std::string>;

using std::cout;
using cpp_lab::MapTree;

class MapTree : private RBTree {
    using base::begin;   // делает begin публичным
};

template <class T>
struct less {
    bool operator()(const T& a, const T& b) const {
        return a < b;
    }
};

template<typename Derived>
class Base {
    void api() {
        static_cast<Derived*>(this)->impl();
        // вызов метода наследника без virtual
    }
};

class RBTree : public Base<RBTree> {
    void impl() { ... }
};

// insert:
m.insert({1, "hello"});
// 1. Создаётся ВРЕМЕННАЯ пара pair<int, string>{1, "hello"}
// 2. Передаётся в insert
// 3. Внутри копируется/перемещается в узел

// emplace:
m.emplace(1, "hello");
// 1. Выделяется память под узел
// 2. Конструктор pair вызывается ПРЯМО в узле через perfect forwarding

std::map<int, std::unique_ptr<Big>> mA, mB;
mA[1] = std::make_unique<Big>();

auto nh = mA.extract(1);   // узел вынут
nh.key() = 2;             // можно переименовать!
mB.insert(std::move(nh));   // узел в mB, значение не копировано

template<typename... Args>
void wrapper(Args&&... args) {       // forwarding reference
    real_func(std::forward<Args>(args)...);
    // если был lvalue — передастся как lvalue
    // если был rvalue — передастся как rvalue
}

[[nodiscard]] bool is_valid();

is_valid();           // warning: result ignored
if (is_valid()) {}    // OK

namespace mylib {
    struct Foo {};
    void swap(Foo& a, Foo& b) {  /* быстрый */  }
}

mylib::Foo a, b;
{
    using std::swap;
    swap(a, b);  // ADL найдёт mylib::swap, а не std::swap
}

int a = 5;
int b = a++;     // b = 5 (старое), a = 6

int x = 5;
int y = ++x;     // x = 6, y = 6 (новое)

4Ключевые места кода

4.1 Где хранятся узлы дерева

Узлы хранятся в куче, создаются через new, удаляются через delete. Дерево хранит указатели через header_ и через parent/left/right внутри узлов.

// БАЗА — только связи
struct NodeBase {
    NodeBase* parent = nullptr;
    NodeBase* left = nullptr;
    NodeBase* right = nullptr;
    bool is_header = false;
};

// + ЗНАЧЕНИЕ
template<typename Value>
struct Node : NodeBase {
    Value value;       // pair<const Key, T>
};

// + ЦВЕТ (для RB)
template<typename Value>
struct RBNode : Node<Value> {
    bool red = true;
};

// + ВЫСОТА (для AVL)
template<typename Value>
struct AVLNode : Node<Value> {
    int height = 1;
};

class OrderedTreeBase {
  protected:
    NodeBase header_{};   // фейковый узел:
                          //   header_.parent = корень дерева
                          //   header_.left   = минимум
                          //   header_.right  = максимум
                          //   header_.is_header = true
    size_type size_ = 0;
    Compare compare_{};
};

template<typename... Args>
std::pair<iterator, bool> emplace(Args&&... args) {
    auto* z = new tree_node(std::forward<Args>(args)...);
    // ↑ узел в куче, конструктор value вызывается прямо в нём
    auto r = reinsert(z);
    if (!r.second) delete z;
    return r;
}

iterator erase_one(iterator pos) noexcept {
    iterator next = pos;
    ++next;
    delete static_cast<tree_node*>(unlink_and_fix(pos.node_));
    //             ↑ каст обязателен, чтобы delete вызвал правильный dtor
    --this->size_;
    return next;
}

4.2 Ключевые места кода

CRTP-каст

Derived& self() noexcept {
    return *static_cast<Derived*>(this);
}
// База кастит this до Derived* и вызывает методы наследника.
// Это даёт статический полиморфизм без virtual.

Защита от self-assignment

OrderedTreeBase& operator=(const OrderedTreeBase& o) {
    if (this != &o) {            // мы не сами себе?
        Derived tmp(static_cast<const Derived&>(o));
        self().swap(tmp);
    }
    return *this;
}

Strong exception safety в копи-конструкторе

OrderedTreeBase(const OrderedTreeBase& o) : compare_(o.compare_) {
    init_header();
    if (o.size_ == 0) return;
    try {
        set_root(copy_subtree(o.header_.parent, header_ptr()));
        refresh_extremes();
        size_ = o.size_;
    } catch (...) {
        clear();              // очистить что успели
        throw;                // пробросить дальше
    }
}

SFINAE-конструктор конвертации iterator → const_iterator

template<bool C = IsConst, std::enable_if_t<C, int> = 0>
TreeIterator(const TreeIterator<Value, false>& o) noexcept
    : node_(o.node_) {}
// Этот конструктор существует ТОЛЬКО когда IsConst=true.
// Разрешает iterator → const_iterator, запрещает обратное.

Вращения в RB

static void rotate_left(NodeBase* x, NodeBase*& root) noexcept {
    NodeBase* y = x->right;
    x->right = y->left;
    if (y->left) y->left->parent = x;
    y->parent = x->parent;
    if (x == root) root = y;
    else if (x == x->parent->left) x->parent->left = y;
    else x->parent->right = y;
    y->left = x;
    x->parent = y;
}

Восстановление RB-правил после вставки

while (z != root && red_of(z->parent)) {
    NodeBase* parent = z->parent;
    NodeBase* grand = parent->parent;
    const bool pl = parent == grand->left;
    NodeBase* uncle = pl ? grand->right : grand->left;

    if (red_of(uncle)) {          // случай 1: красный дядя
        paint(parent, false);
        paint(uncle, false);
        paint(grand, true);
        z = grand;                // проблема всплыла наверх
    } else {
        if (pl ? (z == parent->right) : (z == parent->left)) {
            // случай 2: внутренний — выпрямить вращением
            z = parent;
            pl ? rotate_left(z, root) : rotate_right(z, root);
            parent = z->parent;
            grand = parent->parent;
        }
        // случай 3: внешний — вращение деда + перекраска
        paint(parent, false);
        paint(grand, true);
        pl ? rotate_right(grand, root) : rotate_left(grand, root);
    }
}
paint(root, false);  // корень всегда чёрный

AVL — рекурсивная балансировка

static NodeBase* rebalance(NodeBase* n) noexcept {
    update_h(n);
    const int b = bf(n);     // баланс-фактор
    if (b > 1) {              // перевес влево
        if (bf(n->left) < 0) {  // зигзаг → двойное вращение
            n->left = rotate_left(n->left);
            n->left->parent = n;
        }
        return rotate_right(n);
    }
    if (b < -1) {             // перевес вправо
        if (bf(n->right) > 0) {
            n->right = rotate_right(n->right);
            n->right->parent = n;
        }
        return rotate_left(n);
    }
    return n;
}

5Доп. задачи · что могут попросить написать

5.1 Факториал на шаблонах

Это прямо из лекции 04.15. Используются шаблонные аргументы-константы (non-type template arguments). Факториал считается во время компиляции.

template<int Value>
int getFactorial() {
    return Value * getFactorial<Value - 1>();
}

template<> int getFactorial<1>() {     // база рекурсии
    return 1;
}

int main() {
    const int result = getFactorial<5>();   // = 120
    // ↑ вычислено компилятором, в runtime ничего не считается
    return result;
}

template<unsigned N>
struct Factorial {
    static constexpr unsigned long long value
        = N * Factorial<N - 1>::value;
};

template<>
struct Factorial<0> {
    static constexpr unsigned long long value = 1;
};

// использование:
constexpr auto f5 = Factorial<5>::value;   // 120 на этапе компиляции

constexpr unsigned long long factorial(unsigned n) {
    return (n <= 1) ? 1 : n * factorial(n - 1);
}

constexpr auto f5 = factorial(5);    // compile-time
int n = 10;
auto f10 = factorial(n);             // runtime

5.2 Гробовая таска — метапрограммирование

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

Числа Фибоначчи

template<unsigned N>
struct Fib {
    static constexpr unsigned long long value
        = Fib<N - 1>::value + Fib<N - 2>::value;
};

template<> struct Fib<0> { static constexpr unsigned long long value = 0; };
template<> struct Fib<1> { static constexpr unsigned long long value = 1; };

// Fib<10>::value == 55

Степень числа

template<int Base, unsigned Exp>
struct Pow {
    static constexpr long long value = Base * Pow<Base, Exp - 1>::value;
};

template<int Base> struct Pow<Base, 0> {
    static constexpr long long value = 1;
};

// Pow<2, 10>::value == 1024

Проверка типа на этапе компиляции (свой is_same)

template<typename T, typename U>
struct is_same {
    static constexpr bool value = false;
};

template<typename T>
struct is_same<T, T> {
    static constexpr bool value = true;
};

// is_same<int, int>::value == true
// is_same<int, double>::value == false

Сумма пакета (variadic)

template<int... Vals>
struct Sum;

template<>
struct Sum<> {
    static constexpr int value = 0;
};

template<int First, int... Rest>
struct Sum<First, Rest...> {
    static constexpr int value = First + Sum<Rest...>::value;
};

// Sum<1, 2, 3, 4, 5>::value == 15

5.3 Другие мини-таски, связанные с темой

А) Свой компаратор для MapTree

Если попросят «сделай MapTree с нестандартным сравнением» — пиши struct с operator() и передавай 4-м параметром:

struct ByAbs {
    bool operator()(int a, int b) const {
        return std::abs(a) < std::abs(b);
    }
};

MapTree<int, std::string, RBTree, ByAbs> m;
m[-5] = "five";
m[3] = "three";
m[-1] = "one";
// порядок обхода: -1, 3, -5 (по модулю)

Б) Подсчёт количества элементов больше N

template<typename Map>
int count_greater_than(const Map& m, int threshold) {
    int n = 0;
    for (const auto& [k, v] : m) {
        if (v > threshold) ++n;
    }
    return n;
}

В) Печать дерева в порядке возрастания

template<typename Map>
void print_sorted(const Map& m) {
    for (const auto& [k, v] : m) {
        std::cout << k << " → " << v << "\n";
    }
    // порядок гарантирован свойством BST + in-order обходом
}

Г) Слияние двух MapTree без копий значений (через extract)

template<typename Map>
void move_all(Map& src, Map& dst) {
    while (!src.empty()) {
        auto nh = src.extract(src.begin());
        dst.insert(std::move(nh));
    }
}
// или ещё короче:
dst.merge(src);   // у меня в коде уже есть merge

Д) Вектор ключей

template<typename Map>
auto keys(const Map& m) {
    std::vector<typename Map::key_type> result;
    result.reserve(m.size());
    for (const auto& [k, v] : m) result.push_back(k);
    return result;
}

Е) Поменять значения местами

template<typename Map>
void swap_values(Map& m, const typename Map::key_type& a,
                                const typename Map::key_type& b) {
    auto ita = m.find(a);
    auto itb = m.find(b);
    if (ita != m.end() && itb != m.end()) {
        std::swap(ita->second, itb->second);
        // КЛЮЧИ менять нельзя (они const) — только значения
    }
}

Ж) Печать структуры дерева (для отладки)

// Если попросят добавить вспомогательный метод —
// можно дописать в RBTree приватный метод для отладки:
void print_tree(NodeBase* node, int depth = 0) {
    if (!node) return;
    print_tree(node->right, depth + 1);
    for (int i = 0; i < depth; ++i) std::cout << "  ";
    std::cout << value_of(node).first
              << (red_of(node) ? "R" : "B") << "\n";
    print_tree(node->left, depth + 1);
}

З) Свой алгоритм через итераторы

// Подсчитать сумму значений в диапазоне ключей [lo, hi]
template<typename Map>
auto range_sum(const Map& m,
               const typename Map::key_type& lo,
               const typename Map::key_type& hi) {
    typename Map::mapped_type sum{};
    auto it = m.lower_bound(lo);
    auto end = m.upper_bound(hi);
    for (; it != end; ++it) sum += it->second;
    return sum;
}

∞Чек-лист перед защитой

• ✓ Знаю все 5 категорий значений и могу пример каждой
• ✓ Объясню правило 5 и зачем оно нужно для моего класса
• ✓ Покажу где хранятся узлы (NodeBase → Node → RBNode/AVLNode + new в куче)
• ✓ Объясню что такое CRTP и зачем его использую
• ✓ Расскажу про bidirectional итератор и его паспорт
• ✓ Покажу 3 случая удаления в BST и нарисую их
• ✓ Сравню AVL и RB по конкретным метрикам
• ✓ Объясню что такое std::less и напишу свой компаратор
• ✓ Знаю что такое лямбда и как она разворачивается в класс
• ✓ Расскажу про exception safety и где у меня strong
• ✓ Объясню разницу между using, typedef, typename
• ✓ Напишу факториал на шаблонах если попросят
• ✓ Знаю как шаблоны работают при компиляции и линковке