C++ Academy

💡 Clang умеет показывать AST, и это один из лучших способов реально понять, что компилятор видит в вашем C/C++ коде.
AST — это Abstract Syntax Tree, внутреннее представление программы после парсинга.
Например, простой код:
int x = a + b * 2;
для компилятора — не просто строка текста, а дерево примерно такого смысла:
VarDecl
└── BinaryOperator +
├── a
└── BinaryOperator *
├── b
└── 2
Именно через такое представление компилятор понимает структуру выражений, типы, области видимости и то, какие преобразования можно выполнить дальше.
У Clang AST можно получить напрямую:
clang++ -Xclang -ast-dump -fsyntax-only main.cpp
А в Compiler Explorer / Godbolt есть отдельный режим просмотра AST, поэтому можно менять код и сразу видеть, как перестраивается дерево.
Особенно полезно разбирать так:
шаблоны;
перегрузку функций;
implicit conversions;
auto;
лямбды;
range-based for;
временные объекты;
разные формы инициализации.
Если регулярно смотреть AST, C++ постепенно перестаёт выглядеть как набор «магических правил».
Начинаешь видеть код примерно так, как его видит компилятор.
🔗 https://godbolt.org/z/cfc7h41bT
#Cpp #Clang #Compiler #Programming

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

Он преобразует обычную инфиксную запись:

3 + 4 * 2

в постфиксную:

3 4 2 * +

После этого калькулятору уже не нужно каждый раз разбираться с приоритетами операторов и строить полноценное AST.

Как работает идея:

- один стек хранит операторы;
- второй поток формирует результат;
- операторы с более высоким приоритетом выходят раньше;
- скобки и ассоциативность обрабатываются по правилам стека.

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

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

#Algorithms #C #Programming #Compilers #ComputerScience

🔥 Quickselect быстрый, пока не выберет плохой pivot

Обычный Quickselect в среднем работает за O(n), но неудачный выбор опорного элемента может превратить поиск k-го элемента в O(n²).

В 1973 году Блум, Флойд, Пратт, Ривест и Тарьян предложили алгоритм median of medians, который гарантирует линейное время даже в худшем случае.

Идея:

1. Разделить массив на группы по 5 элементов.
2. Найти медиану каждой группы.
3. Рекурсивно найти медиану полученных медиан.
4. Использовать её как pivot для Quickselect.
int mom_pivot(int *arr, int n)
{
    if (n <= 5) {
        sort(arr, n);
        return arr[n / 2];
    }

    int medians[(n + 4) / 5];

    for (int i = 0; i < n; i += 5) {
        int len = (n - i < 5) ? n - i : 5;

        sort(arr + i, len);
        medians[i / 5] = arr[i + len / 2];
    }

    return mom_pivot(medians, (n + 4) / 5);
}
Такой pivot не обязательно будет настоящей медианой массива, но он гарантированно не окажется слишком близко к краю. После разбиения отбрасывается достаточно большая часть элементов, поэтому рекурсия не деградирует.

Итоговая сложность поиска:
Средний случай: O(n)
Худший случай: O(n)
Дополнительная память: зависит от реализации
На практике randomized Quickselect часто быстрее из-за меньших констант. Median of medians нужен там, где важна строгая гарантия времени: real-time системы, adversarial input и библиотеки с предсказуемой производительностью.