cpluspluc | Unsorted

Telegram-канал cpluspluc - C++ Academy

16151

По всем вопросам- @haarrp @itchannels_telegram - 🔥 best it channels РКН: clck.ru/3FmxJF

Subscribe to a channel

C++ Academy

⚡️ В 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 часто выглядит коротко, пока не начнёшь разворачивать макросы.

Читать полностью…

C++ Academy

💡 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);

Читать полностью…

C++ Academy

📚 Отличная подборка материалов по современному 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++ Academy

🐢 Все пытаются ускорить процессоры. А этот проект делает наоборот.

Новый проект CPU deoptimization ищет самые медленные инструкции, которые когда-либо выполнялись на x86.

Идея простая:

Не «как заставить CPU работать быстрее», а:

«Какую самую ужасную инструкцию можно заставить выполнить процессор?»

Результат уже впечатляет:

💀 Рекорд x86:
198 002 498 236 тактов CPU
62 секунды на выполнение одной инструкции

Это целая «галерея позора» для ассемблера:

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

Иногда лучший способ понять процессор — не ускорять его, а найти его слабые места.

Assembly Hall of Shame:
https://github.com/xoreaxeaxeax/asm-hall-of-shame

Читать полностью…

C++ Academy

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

Читать полностью…

C++ Academy

🔥 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++ Academy

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

Читать полностью…

C++ Academy

🔥 Джулиан Сторер - разработчик с более чем 30-летним опытом C++

Он создал сразу несколько заметных проектов в мире аудио-разработки:

- Tracktion DAW
- JUCE C++ Framework
- Cmajor DSP language

Особенно интересно тем, кто работает с:

- C++
- аудио и музыкой
- DSP
- DAW
- real-time приложениями

У него много сильного open-source кода и проектов, которые стоит изучить разработчикам из audio/software engineering.

https://github.com/julianstorer

Читать полностью…

C++ Academy

❓Кто этот призрак в вашем коде: изучаем особенности работы с легаси на C++

Легаси — вот что объединяет всех разработчиков на всех языках программирования. Мы учимся уживаться с «наследием», встраиваем его в современную кодовую базу или стараемся не трогать.

Пришло время разобраться с легаси в email-проекте Ghost in the code.

Вы получите семь писем от инженеров, в числе которых представитель России в Международной рабочей группе по стандартизации C++ Антон Полухин и эксперт по архитектуре Константин Владимиров. Вместе с ними и другими опытным разработчиками пройдете путь от навигации по «зрелому» коду с помощью AI до выстраивания процессов с учетом легаси.

➡️Подписывайтесь на серию писем, это бесплатно. Оставляйте email-адрес на сайте проекта — первое письмо придет 15 сентября.

Читать полностью…

C++ Academy

✈️🌍 FlightGear: мощный симулятор полетов с открытым исходным кодом.

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

🚀Основные моменты:
- Поддержка множества типов самолетов и ландшафтов.
- Реалистичная физика полета и погодные условия.
- Многофункциональный интерфейс и расширяемая архитектура.
- Активное сообщество разработчиков и пользователей.
- Кроссплатформенная доступность.

📌 GitHub: https://github.com/FlightGear/flightgear

#c++

Читать полностью…

C++ Academy

В C есть синтаксис, который выглядит как опечатка:


case '0' ... '9':


Кажется, что такой switch вообще не должен компилироваться.

Но в GCC это работает. Это расширение называется case ranges — можно задавать сразу диапазон значений внутри case.

Например:


case '0' ... '9':
return DIGIT;

case 'a' ... 'z':
case 'A' ... 'Z':
return LETTER;


Вместо десяти отдельных case для цифр и ещё десятков для букв — одна строка на диапазон.

Но есть нюанс: это не стандартный C, а расширение GCC. Если код должен быть переносимым между компиляторами, на такой синтаксис лучше не рассчитывать.

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

Читать полностью…

C++ Academy

🔥 Хочешь быстрее расти в IT? Хватит учиться в одиночку

Окружение решает больше, чем кажется.

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

AI: t.me/ai_machinelearning_big_data
Python: t.me/pythonl
Linux: t.me/linuxacademiya
Хакинг: t.me/linuxkalii
DevOps: t.me/DevOPSitsec
Docker: /channel/+90Z5TAyfuNU5YmRi
Golang: t.me/Golang_google
Rust: t.me/rust_code
C++: t.me/cpluspluc
C#: t.me/csharp_1001_notes
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: /channel/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: /channel/addlist/2Ls-snqEeytkMDgy
Папка Frontend: /channel/addlist/mzMMG3RPZhY2M2Iy

Полезное сверху:

ИТ-мемы: t.me/memes_prog
Английский для программистов: t.me/english_forprogrammers
ИИ и технологии: t.me/vistehno
954 ГБ open-source курсов: /channel/+rKBQEMccAA01MTcy
ИТ-книги бесплатно: /channel/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++ Academy

🖥 C++26 закрывает одну из самых больных тем lock-free кода - безопасное удаление памяти.

Проблема не в atomics.

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

Удалишь слишком рано, получишь use-after-free.

Поэтому в C++26 стандартизируют Hazard Pointers.

Идея простая:

поток заранее помечает объект как “я сейчас его читаю”.

Пока хотя бы один reader держит такой hazard pointer, объект нельзя удалять.

Удаление откладывается до момента, когда все читатели закончат работу.

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

Lock-free программирование становится не магией, а чуть более нормальным инженерным инструментом.

Читать полностью…

C++ Academy

⚙️ Обычный strcat() в цикле может незаметно превратить простую склейку строк в O(n²).

Причина в том, что strcat() при каждом вызове сначала ищет конец уже собранной строки.

Чем длиннее буфер, тем больше данных приходится повторно проходить.

Например:


for (int i = 0; i < 100000; i++)
strcat(buf, "chunk");


В бенчмарке сборка строки примерно на 1 МБ заняла около 4,1 секунды.

Если же заранее выделить буфер и просто хранить текущую позицию записи:


char *p = buf;

for (int i = 0; i < 100000; i++) {
memcpy(p, "chunk", 5);
p += 5;
}


тот же объём собирается примерно за 0,4 мс.

Разница больше чем в 10 000 раз.

Мелочь, которую легко пропустить: проблема не в копировании строки, а в постоянном повторном поиске её конца.

Читать полностью…

C++ Academy

📚 Библиотека для работы с SQLite в C++26 с использованием рефлексии

Reflite — это библиотека на C++26, которая упрощает взаимодействие с SQLite, позволяя использовать обычные структуры как основу для выполнения запросов. Она поддерживает основные операции: вставка, удаление, выборка и обновление, избавляя от лишнего шаблона кода.

🚀 Основные моменты:
- Легковесная библиотека в одном файле
- Поддержка операций INSERT, DELETE, SELECT, UPDATE
- Использует рефлексию для работы с типами структур
- Не требует полной реализации SQL, фокус на простоте
- Совместима с современными компиляторами C++26

📌 GitHub: https://github.com/KaruroChori/reflite

#cpp

Читать полностью…

C++ Academy

🔥 Почему в 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++ Academy

🔥 Хочешь расти в 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: /channel/+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: /channel/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: /channel/addlist/2Ls-snqEeytkMDgy
Папка Frontend: /channel/addlist/mzMMG3RPZhY2M2Iy

Полезное сверху:

ИТ-мемы: t.me/memes_prog
Английский для программистов: t.me/english_forprogrammers
ИИ и технологии: t.me/vistehno
954 ГБ open-source курсов: /channel/+rKBQEMccAA01MTcy
ИТ-книги бесплатно: /channel/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++ Academy

🛠 Как автоматически закрывать файлы из 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, обработчик освобождения вызван не будет.

Читать полностью…

C++ Academy

🚀 Как ядро 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, которая помогает писать быстрый код на уровне ядра.

Читать полностью…

C++ Academy

🔥 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

Читать полностью…

C++ Academy

Разбор одной из тех 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

Читать полностью…

C++ Academy

3D-фрактал Mandelbulb можно отрендерить примерно в 100 строках C++ - вообще без полноценного 3D-движка.

В основе всего несколько идей:

- Mandelbulb строится через сферическую итерацию в степени 8
- distance estimator примерно определяет расстояние до поверхности фрактала
- sphere tracing двигает луч большими шагами через пустое пространство
- когда луч приближается к поверхности, конечные разности вычисляют нормаль для освещения
- результат записывается напрямую в обычный PPM-файл

То есть сложнейший на вид 3D-фрактал получается из математики, ray marching и небольшого количества C++.

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

Читать полностью…

C++ Academy

Как Linux увеличивает счётчик без lock на SMP-системах

В ядре Linux есть трюк, который выглядит почти слишком просто: не заставлять все CPU драться за одну переменную.

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

На x86 макрос this_cpu_inc(var) превращается в одну инструкцию incl, которая работает с областью данных текущего CPU через GS.

Что это даёт:

* нет общего lock
* нет постоянной конкуренции между ядрами
* инкремент выполняется локально для текущего CPU
* операция получается быстрой и дешёвой

Идея мощная: если данные можно разделить по CPU, не нужно синхронизировать каждый маленький апдейт между всеми ядрами.

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

Читать полностью…

C++ Academy

✔️ curl - один из самых недооценённых проектов в истории софта.

Первый релиз вышел 20 марта 1998 года. Его запустил один разработчик - Daniel Stenberg.

Прошло больше 27 лет, а он всё ещё поддерживает проект.

Сегодня curl работает на миллиардах устройств и поставляется почти везде:

* macOS
* основные Linux-дистрибутивы
* Windows 10 и новее
* серверы
* контейнеры
* embedded-системы
* CI/CD пайплайны

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

Одна маленькая CLI-утилита стала невидимой инфраструктурой интернета.

Вот так выглядит настоящий open source: без хайпа, без миллиардных раундов, но с кодом, который держит половину мира.

Читать полностью…

C++ Academy

🖥 Большинство “простых” shuffle-алгоритмов дают кривой рандом

Частая ошибка:


for (int i = 0; i < n; i++) {
int j = rand() % n;
swap(a[i], a[j]);
}


На вид всё нормально: каждый элемент случайно меняется местами с другим.

Но проблема в вероятностях.

Для массива из n элементов существует n! перестановок.

Хороший shuffle должен давать каждой перестановке одинаковый шанс.

Наивный вариант делает n шагов, и на каждом шаге выбирает индекс из полного диапазона 0..n-1.

В итоге некоторые перестановки появляются чаще других.

Правильный подход - Fisher-Yates shuffle:


for (int i = n - 1; i > 0; i--) {
int j = random(0, i);
swap(a[i], a[j]);
}


Идея простая:

на каждом шаге мы выбираем элемент только из ещё не зафиксированной части массива.

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

Так каждая перестановка получает одинаковую вероятность.

В C++ лучше не писать через rand() % n, потому что там может быть ещё и modulo bias.

Нормальный вариант:


std::mt19937 rng(std::random_device{}());

for (int i = n - 1; i > 0; --i) {
std::uniform_int_distribution<int> dist(0, i);
int j = dist(rng);
std::swap(a[i], a[j]);
}


Shuffle - хороший пример, где код может выглядеть “рандомным”, но математически быть неправильным.

Читать полностью…

C++ Academy

Одна строка C, которая может сломать вам логику

В C порядок вычисления аргументов функции не определён.


foo(i++, i++);


Из-за этого один и тот же код может дать разный результат:

* gcc: foo(1, 0)
* clang: foo(0, 1)

Причина простая: компиляторы по-разному вычисляют аргументы.

Такие вещи годами становились источником очень неприятных багов.
Хорошая новость: сейчас -Wall обычно умеет это подсветить.

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

Читать полностью…

C++ Academy

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

И до сих пор никто достоверно не знает, кто скрывается за этим именем.

При этом сама базовая идея Proof of Work выглядит почти примитивно: берём число nonce, меняем его снова и снова, каждый раз считаем хэш и проверяем, попал ли результат ниже нужного target.

Условно это выглядит так:


uint32_t nonce = 0;

while (1) {
header.nonce = nonce;
hash = sha256(sha256(header));

if (hash < target)
break;

nonce++;
}


То есть майнинг Bitcoin в основе своей это гигантский перебор чисел с постоянным пересчётом SHA-256.

Простой цикл, который в итоге породил ASIC-фермы, энергопотребление в масштабах стран и индустрию на миллиарды долларов.

Читать полностью…

C++ Academy

⚡️ Linux может освободить RAM, не уничтожая сам диапазон виртуальной памяти процесса.

Это как раз то, что делает madvise(MADV_DONTNEED) для anonymous mappings.

Сценарий такой:


char *region = mmap(NULL, GB,
PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS,
-1, 0);

// потрогали часть страниц

madvise(region, GB, MADV_DONTNEED);


После madvise виртуальные адреса остаются валидными. Процесс всё ещё «видит» тот же диапазон памяти.

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

При следующем обращении к этому участку процесс получит свежие zero-filled страницы. Старых данных там уже не будет.

Почему это полезно:

* можно держать большой виртуальный регион без постоянного удержания RAM
* аллокаторы могут возвращать неиспользуемые страницы ядру
* long-running процессы меньше раздувают RSS
* память можно переиспользовать без полного munmap и нового mmap

Важная деталь: MADV_DONTNEED не означает «удали адреса». Это скорее сигнал ядру: «эти страницы мне сейчас не нужны, можешь забрать физическую память».

Адреса остаются. Страницы уходят. Следующее чтение приносит нули.

Читать полностью…

C++ Academy

⚡️ Fenwick Tree держится на одном битовом трюке

Fenwick Tree, или Binary Indexed Tree, считает prefix sums за O(log n).

Вся магия в операции:


i & -i


Она находит младший установленный бит числа.

Почему это работает?

В two’s complement число -i получается как инверсия битов i плюс 1.
Когда мы делаем i & -i, остаётся только самый правый бит, равный 1.

Например:


i = 12 // 1100
-i // 0100 в нужной маске
i & -i = 4


Именно это значение говорит Fenwick Tree, на сколько нужно прыгнуть по индексам.

Для обновления:


for (; i < MAXN; i += i & -i)
tree[i] += v;


Мы идём вверх по структуре и обновляем все узлы, которые покрывают этот индекс.

Для запроса суммы:


for (; i > 0; i -= i & -i)
s += tree[i];


Мы идём вниз и собираем нужные блоки суммы.

Одна и та же операция управляет двумя направлениями:

* i += i & -i — перейти к следующему ответственному узлу
* i -= i & -i — убрать последний блок из prefix sum

Поэтому Fenwick Tree такой компактный:
никаких явных рёбер, указателей и рекурсии. Только массив и битовая арифметика.

Красота структуры в том, что дерево как бы спрятано внутри двоичного представления индекса.

Читать полностью…

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

Читать полностью…
Subscribe to a channel