C++ Academy

💡 Алгоритм Флойда находит цикл в связном списке всего с двумя указателями и `O(1)` дополнительной памяти. Идея простая: slow двигается на 1 узел fast — на 2 Если цикл есть, они обязательно встретятся. После встречи один указатель возвращаем в head, а дальше оба двигаем по одному узлу. Следующая точка встречи — точное начало цикла.

Node *detect_cycle(Node *head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            slow = head;

            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }

            return slow;
        }
    }

    return NULL;
}

Сложность:

O(n) по времени
O(1) по памяти

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

🔥 Приглашаем на бесплатный открытый вебинар курса «Программист С»: «Указатели в Си — от адреса к управлению памятью» 🗓 Когда: 24 сентября, 20:00 (мск) Указатели — это не просто синтаксис, а ключ к пониманию того, как Си общается с памятью. Без них невозможно осознанно работать с массивами, строками, структурами и динамическими данными. На вебинаре разберём указатели от самого основания — адресов и операторов — до передачи параметров по ссылке, чтобы вы перестали бояться звёздочек и начали управлять памятью уверенно. Что будет на вебинаре: • Разбор ключевых понятий: адрес переменной, операторы & и *, объявление и разыменовывание указателей — разберём, как Си работает с памятью напрямую; • Пошаговый анализ связи указателей, массивов и функций — выясним, как передавать параметры по ссылке и заставлять функции изменять переменные вызывающего кода. 👉 Зарегистрируйтесь https://otus.pw/BLgM/?erid=2W5zFHuFYrV Реклама. ООО "ОТУС ОНЛАЙН-ОБРАЗОВАНИЕ". ИНН 9705100963.

⚡️ В Linux даже обычный syscall начинается с макроса. Например: SYSCALL_DEFINE3(write, unsigned int, fd, const char __user *, buf, size_t, count) После препроцессора это превращается сразу в несколько функций: - sys_write - __se_sys_write - __do_sys_write Одна строка описывает системный вызов, а C-препроцессор через макросы и token pasting собирает остальную обвязку автоматически. Именно поэтому код ядра Linux часто выглядит коротко, пока не начнёшь разворачивать макросы.

🔥 Почему в Redis Cluster именно 16 384 hash slot и при чём тут `{}` Redis Cluster распределяет ключи не напрямую по нодам, а сначала по 16 384 hash slots. Формула по сути такая: CRC16(key) % 16384 Но есть важный трюк — hash tags. Если ключ содержит часть в фигурных скобках, Redis хеширует только содержимое внутри {}: {user100}:cart {user100}:orders Оба ключа будут вычислены по user100, поэтому попадут в один и тот же hash slot и, соответственно, на одну ноду. Это нужно для multi-key операций в cluster mode. Именно поэтому такие конструкции позволяют нормально использовать: - MGET - MSET - транзакции - Lua-скрипты с несколькими ключами На уровне кода Redis сначала ищет {, затем }, и если внутри есть непустая строка — хеширует только её. Небольшая деталь синтаксиса, которая на самом деле решает важную проблему распределённых операций в Redis Cluster.

💡 C++: std::map<std::string, ...> не обязан создавать временный std::string при каждом поиске Если ключ уже приходит как std::string_view, можно использовать transparent comparator:

std::map<std::string, int, std::less<>> status_codes{
    {"not_found", 404},
    {"timeout", 504}
};

std::string_view key = "timeout";

auto match = status_codes.find(key);

🔥 Хочешь расти в IT быстрее остальных? Перестань учиться в одиночку Можно годами смотреть курсы, читать документацию и всё равно топтаться на месте. А можно попасть в правильное окружение, где каждый день обсуждают новые инструменты, вакансии, реальные кейсы, ошибки и то, что уже завтра станет стандартом. Здесь собраны папки и каналы по разным направлениям IT, чтобы ты быстрее находил нужных людей, идеи и полезный контент - без бесконечного поиска. AI: t.me/ai_machinelearning_big_data Python: t.me/pythonl Linux: t.me/linuxacademiya Хакинг: t.me/linuxkalii DevOps: t.me/DevOPSitsec Docker: https://t.me/+90Z5TAyfuNU5YmRi Golang: t.me/Golang_google Rust: t.me/rust_code C++: t.me/cpluspluc C#: t.me/csharp_ci Java: t.me/javatg JavaScript: t.me/javascriptv React: t.me/react_tg Frontend: t.me/front PHP: t.me/phpshka Android: t.me/android_its Мобильная разработка: t.me/mobdevelop Базы данных: t.me/sqlhub Data Science: t.me/data_analysis_ml Big Data: t.me/bigdatai Математика: t.me/data_math Физика: t.me/fizmat Kubernetes: t.me/kubernetc GameDev: https://t.me/gamedev Haskell: t.me/haskell_tg Собеседования и карьера: DS собеседования: t.me/machinelearning_interview Python собеседования: t.me/python_job_interview Папка с вакансиями: t.me/addlist/_zyy_jQ_QUsyM2Vi Папка Go разработчика: t.me/addlist/MUtJEeJSxeY2YTFi Папка Python разработчика: t.me/addlist/eEPya-HF6mkxMGIy Папка ML: https://t.me/addlist/2Ls-snqEeytkMDgy Папка Frontend: https://t.me/addlist/mzMMG3RPZhY2M2Iy Полезное сверху: ИТ-мемы: t.me/memes_prog Английский для программистов: t.me/english_forprogrammers ИИ и технологии: t.me/vistehno 954 ГБ open-source курсов: https://t.me/+rKBQEMccAA01MTcy ИТ-книги бесплатно: https://t.me/addlist/BkskQciUW_FhNjEy Max Ai: https://max.ru/ai_machinelearning_big_data Max python: https://max.ru/pythonl ТЕХНО: https://max.ru/vistehno Max Go: https://max.ru/Golang_google Max Linux: https://max.ru/linuxkalii Devops: https://max.ru/DevOPSitsec C#: https://max.ru/csharp_ci C++: https://max.ru/cpluspluc SQL: https://max.ru/sqlhub Java: https://max.ru/javatg Подпишись и сохрани, здесь регулярно появляются новые подборки, инструменты и материалы, которые реально помогают расти быстрее.

📚 Отличная подборка материалов по современному C++ На Modernes C++ собрали большой структурированный каталог статей по языку - от базовых концепций до сложных тем из современного стандарта. Что есть внутри: - templates и metaprogramming; - concurrency и multithreading; - smart pointers и управление ресурсами; - ranges, concepts и coroutines; - STL и алгоритмы; - memory model; - best practices и типичные ошибки; - новые возможности C++20/23 и дальше. Удобно, что это не набор случайных постов, а фактически большая карта тем по современному C++. Хороший ресурс, если хочется системно закрыть пробелы и глубже понять, как язык работает под капотом. https://modernescpp.com/index.php/table-of-content/ #Cpp #CPlusPlus #Programming #STL #ModernCpp

🛠 Как автоматически закрывать файлы из C-библиотеки в C++ FILE* можно обернуть в std::unique_ptr с собственным обработчиком освобождения:

#include <cstdio>
#include <memory>

struct FileCloser {
    void operator()(std::FILE* file) const noexcept {
        std::fclose(file);
    }
};

using File = std::unique_ptr<std::FILE, FileCloser>;

Использование внутри функции:

File file{std::fopen("data.txt", "r")};

if (!file) {
    return;
}

// Передаём FILE* в функции C-библиотеки
int ch = std::fgetc(file.get());

Когда file выйдет из области видимости, unique_ptr вызовет fclose. Это работает при обычном завершении функции, раннем return и раскрутке стека при исключении. Так устроен RAII: время жизни ресурса связано со временем жизни объекта. Если fopen вернул nullptr, обработчик освобождения вызван не будет.

🐢 Все пытаются ускорить процессоры. А этот проект делает наоборот. Новый проект CPU deoptimization ищет самые медленные инструкции, которые когда-либо выполнялись на x86. Идея простая: Не «как заставить CPU работать быстрее», а: «Какую самую ужасную инструкцию можно заставить выполнить процессор?» Результат уже впечатляет: 💀 Рекорд x86: 198 002 498 236 тактов CPU ≈ 62 секунды на выполнение одной инструкции Это целая «галерея позора» для ассемблера: - странные инструкции; - неожиданные микроархитектурные эффекты; - случаи, когда одна команда превращается в вечность. Иногда лучший способ понять процессор — не ускорять его, а найти его слабые места. Assembly Hall of Shame: https://github.com/xoreaxeaxeax/asm-hall-of-shame

🚀 Как ядро Linux создаёт пакеты переменной длины без лишних копирований В C есть мощный паттерн — flexible array member. Вместо хранения заголовка и данных отдельно:

header → отдельно
payload → отдельно

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

+----------------+
| struct msg     |
| len            |
+----------------+
| payload data[] |
+----------------+

Код:

struct msg {
    uint32_t len;
    uint8_t data[];
};

struct msg *m = malloc(sizeof(*m) + n);

Один malloc() → один блок памяти → один free(). Почему это любят в системном коде: ✅ меньше аллокаций ✅ лучше работа с CPU cache ✅ проще сериализация ✅ нет лишних указателей и разрозненных данных Такой подход используется в низкоуровневом коде: ядрах, драйверах, сетевых стеках. До C99 часто писали:

uint8_t data[1];

и вручную обходили ограничения языка. Теперь data[] — официальный способ сказать: «После структуры здесь будет динамический массив данных». Маленькая особенность C, которая помогает писать быстрый код на уровне ядра.

Redis не доверяет обычным строкам C - и вот почему В C строка заканчивается нулевым байтом \0. Из-за этого strlen() каждый раз проходит весь буфер, а хранить произвольные бинарные данные становится неудобно. Поэтому Redis использует собственную структуру SDS — Simple Dynamic Strings. В памяти она выглядит примерно так:

[len][alloc][flags][данные...\0]
                   ↑
                  sds

Перед самими данными Redis хранит метаданные: - len — текущую длину; - alloc — размер выделенной памяти; - flags — тип заголовка. Благодаря этому длина строки определяется за O(1), а свободное место известно заранее. При добавлении данных Redis не обязан каждый раз заново вычислять размер и перевыделять память. SDS также остаётся совместимой со многими функциями C: указатель ведёт прямо на буфер, а в конце всё равно находится \0. Но Redis не зависит от этого терминатора — длина хранится отдельно. Поэтому внутри строки могут находиться нулевые байты, изображения, сериализованные объекты и другие бинарные данные. Важный нюанс: структура sdshdr из старых примеров сегодня упрощена. Современный Redis выбирает компактный заголовок sdshdr5, sdshdr8, sdshdr16, sdshdr32 или sdshdr64 в зависимости от размера строки. Небольшой заголовок перед буфером решил сразу три проблемы: быстрое получение длины, безопасную работу с бинарными данными и эффективное расширение строк. Источник: https://redis.io/docs/latest/operate/oss_and_stack/reference/internals/internals-sds/ https://github.com/redis/redis/blob/unstable/src/sds.h

🔥 Python + AI без игрушечных демок. Курс для тех, кто хочет собирать рабочие системы. Stepik: «Python современный AI для разработчика и автоматизации задач» 63 урока, 382 шага, практика с кодом и автопроверкой. Внутри: RAG, tool calling, агенты, evals, MCP, Ollama, vLLM, pgvector + HNSW, безопасный text-to-SQL, prompt injection, кэш, очереди и sandbox для агентного кода. Плюс реальные автоматизации: почта, отчёты, боты, вебхуки и браузерные сценарии. Для тех, кто уже знает Python и хочет перейти к production AI. ⏳ 72 часа скидка 55% https://stepik.org/a/295921

🔥 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 и библиотеки с предсказуемой производительностью.

Согласны ?)

✔️ В C/C++ есть любопытный трюк с AVX-512: `_mm512_maskz_loadu_epi8`. Инструкция может выборочно загрузить до 64 байт по маске. Каждый бит маски отвечает за один байт: - 1 - байт загружается - 0 - вместо него ставится ноль Самое интересное начинается, когда маска полностью нулевая:

#include <x86intrin.h>

void f(const char *p) {
    _mm512_maskz_loadu_epi8(0, p);
}

При нулевой маске память фактически не читается, а результатом становится 512-битный вектор из нулей. То есть значение p в таком случае не влияет на результат, а компилятор при оптимизации вообще может удалить весь вызов. Хороший пример того, насколько необычно работают masked-load инструкции в AVX-512.

Разбор одной из тех Win32-задач, где C++ быстро превращается в борьбу с ручным управлением памятью. На этот раз речь про LPPROC_THREAD_ATTRIBUTE_LIST, который нужен при расширенном создании процессов и потоков. Проблема в API простая: - сначала нужно отдельно узнать размер буфера - потом вручную выделить память - вызвать InitializeProcThreadAttributeList - после работы обязательно вызвать DeleteProcThreadAttributeList - и только потом освободить сам буфер Chen предлагает обернуть всё это в RAII через WIL, чтобы очистка происходила автоматически. Из интересного: - отдельный helper для освобождения списка - безопасное получение нужного размера - разбор того, почему CTAD здесь не помогает - перегрузки через SFINAE, чтобы не ловить неоднозначность с int - возможность сразу предзаполнить список атрибутами - можно заранее оставить место под дополнительные атрибуты, которые добавятся позже В итоге работа с LPPROC_THREAD_ATTRIBUTE_LIST становится заметно аккуратнее и меньше похожа на ручной Win32-ритуал с кучей cleanup-кода. https://devblogs.microsoft.com/oldnewthing/20260813-00/?p=112611

Bare Metal C++: как писать прошивки на C++ без ОС и тяжёлого runtime Practical Guide to Bare Metal C++ - бесплатная практическая книга для разработчиков, которые хотят использовать C++ напрямую на микроконтроллерах и ARM-платформах. Внутри: - анализ машинного кода, который генерирует компилятор - запуск C++ без стандартного runtime - работа без исключений, RTTI и динамической памяти - шаблоны и статические структуры данных - event loop и компонентная архитектура драйверов - прерывания, таймеры, UART, GPIO, I2C и SPI - сборка bare-metal приложений для Raspberry Pi Автор показывает, как применять возможности C++ там, где ограничены память, процессорное время и размер прошивки. Это не учебник для новичков. Материал рассчитан на разработчиков, которые уже знают C++ и хотят понять, во что превращается их код на уровне железа. https://arobenko.github.io/bare_metal_cpp/ #cpp #cplusplus #embedded #baremetal

3D-фрактал Mandelbulb можно отрендерить примерно в 100 строках C++ - вообще без полноценного 3D-движка. В основе всего несколько идей: - Mandelbulb строится через сферическую итерацию в степени 8 - distance estimator примерно определяет расстояние до поверхности фрактала - sphere tracing двигает луч большими шагами через пустое пространство - когда луч приближается к поверхности, конечные разности вычисляют нормаль для освещения - результат записывается напрямую в обычный PPM-файл То есть сложнейший на вид 3D-фрактал получается из математики, ray marching и небольшого количества C++. Особенно красиво здесь то, что геометрия вообще не хранится в виде миллионов полигонов - поверхность вычисляется прямо во время рендера.

🔥 Джулиан Сторер - разработчик с более чем 30-летним опытом C++ Он создал сразу несколько заметных проектов в мире аудио-разработки: - Tracktion DAW - JUCE C++ Framework - Cmajor DSP language Особенно интересно тем, кто работает с: - C++ - аудио и музыкой - DSP - DAW - real-time приложениями У него много сильного open-source кода и проектов, которые стоит изучить разработчикам из audio/software engineering. https://github.com/julianstorer