Чек-лист: Линейные структуры данных в C++

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

🎯 Векторы (std::vector)

✓ Используйте reserve() для предварительного выделения памяти, когда примерно известен размер
✓ Применяйте push_back() для добавления элементов и pop_back() для удаления с конца
✓ Доступ по индексу выполняется за O(1) с помощью оператора []
✓ Используйте at() вместо [] для проверки границ массива

🎯 Списки (std::list)

✓ Отдавайте предпочтение при частых вставках/удалениях в середине
✓ Используйте splice() для эффективного перемещения элементов между списками
✓ Помните, что прямой доступ по индексу невозможен — только итерация
✓ Двунаправленные итераторы позволяют двигаться как вперед, так и назад

🎯 Очереди и стеки (std::queue, std::stack)
✓ Стек (LIFO): используйте push() для добавления и pop() для извлечения
✓ Очередь (FIFO): применяйте push() для добавления и pop() для извлечения
✓ Функция front() позволяет посмотреть первый элемент без удаления
✓ Обе структуры являются адаптерами и построены на других контейнерах

🎯 Массивы (std::array)
✓ Используйте для данных фиксированного размера, известного на этапе компиляции
✓ Более эффективны чем векторы для неизменяемых данных
✓ Поддерживают STL-алгоритмы (sort, find и др.)
✓ Проверяйте границы с функцией at() во избежание ошибок доступа

Разница между std::stoi+std::to_string и std::from_chars+std::to_chars
#опытным

В C++ есть два основных подхода к конвертации чисел в строки и обратно:

Старомодный  — std::stoi, std::to_string (C++11)

Модномолодежный — std::from_chars, std::to_chars (C++17)

В чем принципиальная разница между ними и когда какой подход использовать? Сегодня мы широкими мазками ответим на эти вопросы.

Особенности старомодного подхода:

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

👉🏿 Работа в высокоуровневом ООП стиле. Используются классы и возвращаются классы, без всяких сырых буферов.

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

👉🏿 Поддержка локалей. Грубо говоря, это механизм для учёта региональных особенностей представления данных. То есть std::stoi, std::to_string реализованы с учетом возможности спецификации локалей и соотвественно изменения результатов конвертации. С локалями возможна такая штука:
// В США (локаль "en_US"):
std::to_string(3.14); // "3.14" (точка как разделитель)

// В Германии (локаль "de_DE"):
std::to_string(3.14); // Может вернуть "3,14" (запятая)!
Естественно, что поддержка такой фичи чего-то да стоит.

Особенности модномолодежного подхода:

👉🏿 Функции std::from_chars, std::to_chars спроектированы быть настолько легкими и быстрыми, насколько это возможно на таком уровне абстракции.

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

👉🏿 Отсутствие исключений. Функции возвращает объект ошибки, который явно нужно проверять руками.

👉🏿 Не проверяет локали.

👉🏿 Поддерживают частичный парсинг.

👉🏿 Поддержка явной гарантии round-trip. Если вы запишите в строку число с помощью std::to_chars и прочитаете его с помощью std::from_chars, то вы всегда получите изначальный результат. Главное, чтобы обе функции были вызваны с использованием одинаковой реализации стандартной библиотеки. Но у std::stoi, std::to_string и этого нет.


Если вы работаете в высоконагруженном или ограниченном по производительности окружении, то ваш выбор явно std::from_chars, std::to_chars. Обычно в коде таких приложений отказываются от использования исключений, поэтому проблем с код-стайлом не будет.

Возможность поэтапного парсинга также не оставляет выбора - используйте std::from_chars.

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

Choose the right tool. Stay cool.

Алгоритм set_intersection

Создает отсортированную последовательность из элементов, встречающихся в обеих последовательностях – [first1, last1) и [first2, last2).

Рекурсивные лямбды. Хакаем систему
#опытным

Конечно же вчерашний пост был первоапрельской шуткой. Не волнуйтесь, мы вас не бросим и без контента не оставим.

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

1️⃣ Вместо использования auto, явно приводим лямбду к std::function. Тогда компилятор будет знать точный тип функционального объекта и сможет его захватить в лямбду:

std::function<int(int)> factorial = [&factorial](int n) -> int { 
  return (n) ? n * factorial(n-1) : 1;
};

Но использование std::function очень затратно по всем критериям. Компиляция ощутимо замедляется, асма намного больше становится, и std::function обычно сильно медленнее обычных функций и лямбд. А еще и динамические аллокации.

Поэтому не самый хороший способ.

2️⃣ Используем С++14 generic лямбды:

auto factorial = [](int n, auto&& factorial) {
    if (n <= 1) return n;
    return n * factorial(n - 1, factorial);
};
auto i = factorial(7, factorial);

Тут надо разобраться. Мы не могли захватывать лямбду в себя, потому что мы не знали ее тип. Сейчас мы тоже не знаем ее тип, но нам это и не нужно, потому что мы используем дженерик лямбду, которая под капотом превращается в замыкание с шаблонным оператором(). Благодаря cppinsides мы можем заглянуть под капот:

class __lambda_24_20
  {
    public: 
    template<class type_parameter_0_0>
    inline /*constexpr */ auto operator()(int n, type_parameter_0_0 && factorial) const
    {
      if(n <= 1) {
        return n;
      } 
      
      return n * factorial(n - 1, factorial);
    }
    
    #ifdef INSIGHTS_USE_TEMPLATE
    template<>
    inline /*constexpr */ int operator()<__lambda_24_20 &>(int n, __lambda_24_20 & factorial) const
    {
      if(n <= 1) {
        return n;
      } 
      
      return n * factorial.operator()(n - 1, factorial);
    }
    #endif
    
  };

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

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

auto factorial_impl = [](int n, auto&& factorial) {
    if (n <= 1) return n;
    return n * factorial(n - 1, factorial);
};
auto factorial = [&](int n) { return factorial_impl(n, factorial_impl); };
auto i = factorial(7);

Теперь не нужно передавать доп параметры.

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

using factorial_t = int(*)(int);
static factorial_t factorial = [](int n) {
    if (n <= 1) return n;
    return n * factorial(n - 1);
};
auto i = factorial(7);

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

Если у вас есть какие-то еще подобные приемы - пишите в комменты.

Но это все какие-то обходные пути. Хочется по-настоящему рекурсивные лямбды.

И их есть у меня!

Об этом в следующий раз.

Always find a way out. Stay cool.

Что такое TCP Server Project в C++?

💬 TCP Server Project — это проект, который реализует сервер для обмена данными по протоколу TCP (Transmission Control Protocol). Такой сервер позволяет клиентам подключаться к нему, отправлять запросы и получать ответы через надёжное соединение.

На практике TCP-сервер в C++ создаётся с помощью сокетов (например, используя Berkeley sockets на Linux или Winsock на Windows).

Процесс обычно включает:
• Создание сокета — создаётся дескриптор для коммуникации.
• Привязка к порту (bind) — сервер привязывается к определённому порту на хосте.
• Прослушивание соединений (listen) — сервер ожидает входящие подключения.
• Принятие соединений (accept) — сервер принимает запросы от клиентов.
• Обмен данными — сервер и клиент обмениваются сообщениями через соединение.

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

Deducing this и CRTP
#опытным

У deducing this есть одна особенность. При обычном наследовании(без виртуальных функций) методы родительского класса знают про точный тип объектов наследников, которые вызывают метод:

struct Machine {
  template <typename Self>
  void print(this Self&& self) {
    self.print_name();
  }
};

struct Car : public Machine {
  std::string name;
  void print_name() {
    std::cout << "Car\n";
  }
};

Car{}.print(); // Выведется "Car"

Вам ничего это не напоминает? CRTP конечно.

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

template <typename Derived>
struct add_postfix_increment {
    Derived operator++(int) {
        auto& self = static_cast<Derived&>(*this);

        Derived tmp(self);
        ++self;
        return tmp;
    }
};

struct some_type : add_postfix_increment<some_type> {
    // Prefix increment, which the postfix one is implemented in terms of
    some_type& operator++();
};

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

Но с появлением deducing this мы можем избежать рождения этого странного отпрыска наследования и шаблонов:

struct add_postfix_increment {
    template <typename Self>
    auto operator++(this Self&& self, int) {
        auto tmp = self;
        ++self;
        return tmp;
    }
};

struct some_type : add_postfix_increment {
    // Prefix increment, which the postfix one is implemented in terms of
    some_type& operator++();
};

Ну вот. У нас только один шаблонный метод. Но для пользователя он ничем не отличается от обычного нешаблонного метода.

Все красиво, эстетично и не ломает голову людям, мало работающим с шаблонами.

Make things more elegant. Stay cool.

ref-qualified методы
#опытным

В С++ можно довольно интересными способами перегружать методы класса. Один из самых малоизвестных и малоиспользуемых - помечать методы квалификатором ссылочности.

Чтобы было понятнее. Примерно все знают, что бывают константные и неконстантные методы.

struct SomeClass {
  void foo() {std::cout << "Non-const member function" << std::endl;}
  void foo() const {std::cout << "Const member function" << std::endl;}
};

SomeClass nonconst_obj;
const SomeClass const_obj;
nonconst_obj.foo();
const_obj.foo();

// OUTPUT
// Non-const member function
// Const member function

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

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

По аналогии с cv-квалификаторами методов начиная с С++11 существуют ref-квалификаторы. Мы можем перегрузить метод так, чтобы он мог раздельно обрабатывать левые и правые ссылки.

struct SomeClass {
  void foo() & {std::cout << "Call on lvalue reference" << std::endl;}
  void foo() && {std::cout << "Call on rvalue reference" << std::endl;}
};

SomeClass lvalue;
lvalue.foo();
SomeClass{}.foo(); 

// OUTPUT
// Call on lvalue reference
// Call on rvalue reference

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

Работают они примерно также, как вы и ожидаете. lvalue-ref перегрузка вызывается на именованном объекте, rvalue-ref перегрузка - на временном.

Зачем это придумано?

Здесь на самом деле большие параллели с cv-квалификацией методов. Допустим, у вас класс - это какая-то коллекция. И вы хотите давать пользователям доступ к элементам этой коллекции через оператор[]. Для неконстантных объектов удобно возвращать ссылку. А вот для константных возвращение ссылки - потенциальное нарушение неизменяемости объекта. Поэтому в таких случаях константный оператор может возвращать элемент по значению или по константной ссылке.

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

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

Stay flexible. Stay cool.

scope_exit в C++: cleanup без goto и забытых close()

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

В таких местах удобно использовать маленький RAII-хелпер, который выполнит переданную лямбду при выходе из scope. Это особенно полезно в коде с исключениями и несколькими точками выхода.

Начнём с самого класса:

template <class F>
class scope_exit {
    F fn;
    bool active = true;

Он хранит функцию cleanup и флаг, нужно ли её вызывать.

public:
    explicit scope_exit(F f) : fn(std::move(f)) {}
    ~scope_exit() { if (active) fn(); }

В деструкторе cleanup выполнится автоматически, если guard ещё активен.

    void release() noexcept { active = false; }
};

release() нужен, если в каком-то сценарии cleanup уже не требуется.

Теперь добавим маленький helper, чтобы не писать тип вручную:

template <class F>
scope_exit<F> make_scope_exit(F f) {
    return scope_exit<F>(std::move(f));
}

С ним использование получается заметно чище.

Открываем файл и сразу вешаем cleanup рядом:

FILE* f = std::fopen("data.bin", "wb");
if (!f) throw std::runtime_error("open failed");

auto guard = make_scope_exit([&] { std::fclose(f); });

Это главный плюс паттерна: ресурс и его освобождение находятся буквально рядом.

Дальше могут быть любые ранние выходы:

if (std::rand() % 2)
    return;

std::fwrite("abc", 1, 3, f);

Даже если функция завершится раньше, fclose всё равно вызовется автоматически.

Такой helper быстро окупается в коде, где много веток, ошибок и временных ресурсов. Он убирает дублирование и делает cleanup предсказуемым.

Фиксим проблему с конструированием POD типов
#опытным

В прошлом посте говорили о том, что тяжело POD типам работать с функциями, которые внутри себя вызывают new. Клятые скобки!

Это очевидные недоработки стандарта. Которые взяли и пофиксили в С++20!

Теперь объекты POD типов можно создавать как через фигурные скобки, так и через круглые. Хотя небольшая разница есть. Но это уже супердетали:

struct A {  
  int a;  
  int&& r;  
};  
  
int f();  
int n = 10;  
  
A a1{1, f()};               // OK, lifetime is extended  
A a2(1, f());               // well-formed, but dangling reference  
A a3{1.0, 1};               // error: narrowing conversion  
A a4(1.0, 1);               // well-formed, but dangling reference  
A a5(1.0, std::move(n));    // OK

Теперь можно использовать все преимущества метода emplace_back и писать такой код:

std::vector<Point> vec;
vec.emplace_back(1, 2, 3);

Вроде мелочь, а раньше это выбивало из колеи. Правило almost always use emplace_back здесь не работало.

Давайте добавлю еще чуть больше контекста(и своей боли) про emplace_back vs push_back.

Что было до с++20.
push_back спокойно переваривал следующий код:

std::vector<Point> vec;
vec.push_back({1, 2, 3});

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

Как видите здесь нет явного указания типа. И это работало до 20-х плюсов и было причиной делать исключения для правила с emplace_back'ом. Сравните:

std::vector<Point> vec;
vec.push_back({1, 2, 3});
vec.emplace_back(Point{1, 2, 3});

Больше букав! А если название структуры длинное? Вот вот.

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

Благо теперь наши пальцы сильнее защищены от стачивания, что не может не радовать!

Кстати, с С++20 и сам термин POD стал помечаться устаревшим, теперь его заменили более тонкие типы TrivialType, ScalarType, и StandardLayoutType. Ну и функции std::make_* тоже работают как надо с простыми структурами.

std::initializer_list

Присваивайте значения контейнерам непосредственно с помощью списка инициализаторов, как это можно делать с C-массивами.

Это справедливо и для вложенных контейнеров. Скажите спасибо С++11.