🤔 Что знаешь про гарантии безопасности исключений?

Гарантии безопасности исключений (Exception Safety Guarantees) — это концепция, связанная с корректным поведением программы при возникновении исключений. Она определяет, насколько безопасно может завершиться выполнение функции или блока кода в случае выбрасывания исключения.

🚩Никаких гарантий (No Guarantee)

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

void unsafeFunction(std::vector<int>& vec, int value) {
    vec.push_back(value); // Если здесь выбросится исключение, состояние vec не определено
    // ...
}

🚩Базовая гарантия (Basic Guarantee)

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

void safeFunction(std::vector<int>& vec, int value) {
    try {
        vec.push_back(value); // Если исключение, состояние vec остаётся корректным
    } catch (...) {
        // Обработка исключения
        std::cerr << "Ошибка при добавлении элемента!" << std::endl;
    }
}

🚩Сильная гарантия (Strong Guarantee)

Этот уровень гарантирует, что в случае возникновения исключения программа останется в исходном состоянии, как будто вызов функции никогда не происходил. Состояние откатывается до того, что было до вызова функции.

void addValue(std::vector<int>& vec, int value) {
    std::vector<int> temp = vec; // Создаём копию
    temp.push_back(value);       // Работаем с копией
    vec = temp;                  // Замена содержимого
}

🚩Гарантия отсутствия исключений (No-Throw Guarantee)

Этот уровень гарантирует, что функция никогда не выбрасывает исключений. Обычно применяется к ключевым операциям (например, деструкторам, перемещениям).

void safeSwap(std::vector<int>& a, std::vector<int>& b) noexcept {
    a.swap(b); // std::vector::swap гарантирует отсутствие исключений
}

🚩Как достигаются гарантии безопасности исключений?

🟠RAII (Resource Acquisition Is Initialization)
Использование классов, где ресурсы освобождаются в деструкторах. Например, std::unique_ptr или std::lock_guard.

🟠Копирование перед изменением
Применение принципа работы с временными копиями (как в примере сильной гарантии).

🟠Использование стандартных контейнеров
Библиотека STL предоставляет базовую гарантию безопасности исключений для большинства операций.

Ставь 👍 и забирай 📚 Базу знаний

🤔 Как устроена хеш таблица в unordered_map?

std::unordered_map в C++ реализован на основе хеш-таблицы. Это структура данных, обеспечивающая O(1) доступ к элементам в среднем случае.

🚩Основные компоненты хеш-таблицы

🟠Массив "бакетов" (buckets)
Хеш-таблица состоит из массива бакетов, где каждый бакет содержит список элементов с одинаковым хеш-кодом.
🟠Функция хеширования (`std::hash<T>`)
Для определения, в какой бакет попадёт ключ, используется функция хеширования (std::hash<T>).
🟠Проверка коллизий
Если два разных ключа попадают в один бакет (коллизия), элементы сохраняются в связанном списке (чаще всего).
🟠Рехеширование
При переполнении таблицы (load_factor > порогового значения) количество бакетов увеличивается, и все элементы перераспределяются.

🚩Как работает поиск и вставка в `unordered_map`

Хеш-функция вычисляет хеш-код ключа

   std::hash<int> hash_fn;
   size_t hash_value = hash_fn(42); // Например, 23145123

Определяется индекс бакета

   size_t bucket_index = hash_value % bucket_count;

🚩Разрешение коллизий

Когда два ключа попадают в один бакет, возникают коллизии. std::unordered_map использует метод цепочек (separate chaining):
В каждом бакете хранится связанный список (или другой контейнер).
Если несколько элементов имеют одинаковый хеш, они добавляются в этот список.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap;

    myMap[1] = "One";  // Хеш-функция определит бакет
    myMap[2] = "Two";  // Если попадает в тот же бакет, создаётся список

    for (const auto& [key, value] : myMap) {
        std::cout << "Key: " << key << ", Value: " << value << '\n';
    }

    return 0;
}

🚩Рехеширование (увеличение количества бакетов)

Когда таблица заполняется, выполняется rehash (увеличение массива бакетов в 2 раза).
Load factor (load_factor()) показывает, насколько заполнена таблица:

std::unordered_map<int, std::string> myMap;
std::cout << "Load factor: " << myMap.load_factor() << '\n';

Ставь 👍 и забирай 📚 Базу знаний

🤔 Сколько занимает места объект пустого класса?

Объект пустого класса не может иметь нулевой размер из-за требований стандарта. Поэтому компилятор добавляет "фиктивный байт" (dummy byte), чтобы каждый объект имел уникальный адрес.

Простой пример

#include <iostream>

class Empty {};

int main() {
    std::cout << "Размер пустого класса: " << sizeof(Empty) << " байт\n";
    return 0;
}

Вывод (на большинстве компиляторов):

Размер пустого класса: 1 байт

Что если создать массив пустых объектов?

#include <iostream>

class Empty {};

int main() {
    Empty arr[10]; // Создаем массив из 10 объектов

    std::cout << "Размер массива из 10 пустых объектов: " << sizeof(arr) << " байт\n";
    return 0;
}

Вывод

Размер массива из 10 пустых объектов: 10 байт

🟠Унаследованный пустой класс (Empty Base Optimization - EBO)
Если пустой класс используется в наследовании, компилятор может убрать его размер (оптимизация Empty Base Optimization, EBO).

#include <iostream>

class Empty {};

class Derived : public Empty {
    int value; // 4 байта (обычно)
};

int main() {
    std::cout << "Размер пустого класса: " << sizeof(Empty) << " байт\n";
    std::cout << "Размер наследника: " << sizeof(Derived) << " байт\n";
    return 0;
}

Вывод

Размер пустого класса: 1 байт
Размер наследника: 4 байта (а не 5!)

Ставь 👍 и забирай 📚 Базу знаний

🤔 Почему со стеком работать быстрее чем с кучей?

🟠Управление памятью
Стек: Память в стеке управляется автоматически. Когда вызывается функция, память для её локальных переменных выделяется одним блоком при входе в функцию и освобождается при выходе из неё. Эта операция выполняется за постоянное время (O(1)).
Куча: Память в куче управляется вручную (программистом) или через автоматическое управление памятью (например, сборщик мусора). Выделение и освобождение памяти в куче требуют поиска подходящего блока памяти, что может занимать больше времени (O(log n) или даже O(n)).

🟠Локальность данных
Стек: Данные в стеке расположены компактно и последовательно. Это означает, что доступ к данным будет быстрее из-за лучшего использования кэш-памяти процессора.
Куча: Данные в куче могут быть фрагментированы, что приводит к меньшей эффективности кэширования и увеличению времени доступа.

🟠Предсказуемость
Стек: Память в стеке выделяется и освобождается в строго определённом порядке (LIFO - Last In, First Out). Это делает операции со стеком предсказуемыми и упрощает управление памятью.
Куча: Память в куче может выделяться и освобождаться в произвольном порядке, что приводит к фрагментации и усложняет управление памятью.

🟠Минимизация накладных расходов
Стек: Операции выделения и освобождения памяти на стеке имеют минимальные накладные расходы, так как это просто смещение указателя стека.
Куча: Операции выделения и освобождения памяти в куче требуют более сложных алгоритмов и могут включать в себя дополнительные накладные расходы, такие как управление списками свободных блоков и слияние фрагментов.

#include <iostream>

void stackFunction() {
    int stackArray[1000]; // Массив на стеке
    // Работа с массивом
}

void heapFunction() {
    int* heapArray = new int[1000]; // Массив в куче
    // Работа с массивом
    delete[] heapArray; // Освобождение памяти
}

int main() {
    stackFunction(); // Быстрая работа со стеком
    heapFunction();  // Медленная работа с кучей
    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Какой имеется побочный эффект при работе с кодом в хидере?

При работе с кодом в хидерах возможны проблемы, связанные с повторным включением файлов (multiple inclusion), что может вызвать ошибки компиляции. Это решается использованием включающих защит (#pragma once или #ifndef). Также код в хидере увеличивает время компиляции, так как включается в несколько исходных файлов.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Какова суть принципа подстановки Барбары Лисков?

Является одним из пяти принципов SOLID и был предложен Барбарой Лисков в 1987 году. Этот принцип гласит, что объекты базового (родительского) класса должны быть заменяемы объектами производного (дочернего) класса без нарушения правильности программы. Другими словами, если класс S является подтипом класса T, то объекты типа T должны быть заменяемы объектами типа S без изменения желаемых свойств программы.

🚩Почему это нужно?

LSP помогает обеспечить правильное использование наследования и полиморфизма в объектно-ориентированном программировании. Если принцип подстановки нарушен, то полиморфизм может привести к неожиданным ошибкам и некорректному поведению программы. Следование LSP делает код более гибким, надежным и легким для сопровождения.

🚩Как это используется?

1⃣Поддерживали контракт, заданный базовым классом.
2⃣Не изменяли ожидаемое поведение базового класса.
3⃣Не ослабляли инварианты базового класса.
4⃣Не нарушали постусловия и предусловия базового класса.

🚩Пример использования

🟠Нарушение LSP
Здесь класс Square нарушает LSP, потому что он изменяет поведение методов setWidth и setHeight, что может привести к неожиданным результатам при использовании объекта Square как Rectangle.

class Rectangle {
protected:
    int width, height;
public:
    virtual void setWidth(int w) { width = w; }
    virtual void setHeight(int h) { height = h; }
    int getWidth() const { return width; }
    int getHeight() const { return height; }
    int area() const { return width * height; }
};

class Square : public Rectangle {
public:
    void setWidth(int w) override {
        width = w;
        height = w; // Изменяем и ширину, и высоту
    }

    void setHeight(int h) override {
        height = h;
        width = h; // Изменяем и высоту, и ширину
    }
};

🟠Соблюдение LSP
Лучше всего избегать такого наследования, которое приводит к нарушению LSP. В этом случае можно использовать другой подход, например, композицию вместо наследования. Теперь Rectangle и Square наследуют от абстрактного класса Shape, и каждый класс реализует метод area согласно своей логике, не нарушая LSP.

class Shape {
public:
    virtual int area() const = 0;
    virtual ~Shape() = default;
};

class Rectangle : public Shape {
protected:
    int width, height;
public:
    Rectangle(int w, int h) : width(w), height(h) {}
    void setWidth(int w) { width = w; }
    void setHeight(int h) { height = h; }
    int getWidth() const { return width; }
    int getHeight() const { return height; }
    int area() const override { return width * height; }
};

class Square : public Shape {
    int side;
public:
    Square(int s) : side(s) {}
    void setSide(int s) { side = s; }
    int getSide() const { return side; }
    int area() const override { return side * side; }
};

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что будет, если несколько раз вызвать lock?

1. Если используется обычный std::mutex, повторный вызов lock из того же потока вызовет deadlock.
2. Для избежания этой ситуации можно использовать std::recursive_mutex, который позволяет одному потоку многократно блокировать мьютекс

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Как пофиксить проблему, когда mutex является локальной переменной?

Использование std::mutex в качестве локальной переменной может привести к различным проблемам, особенно если он используется для синхронизации доступа к общим данным. Локальный std::mutex будет уничтожен при выходе из области видимости, что нарушит работу других потоков, ожидающих блокировку или разблокировку.

🚩Проблемы с локальным `std::mutex`

🟠Жизненный цикл локального `std::mutex`
Локальная переменная уничтожается при выходе из функции или блока, в котором она объявлена. Это может привести к неопределенному поведению, если другие потоки все еще используют этот мьютекс.

🟠Неопределенное поведение
Уничтожение мьютекса, который все еще заблокирован, может привести к неопределенному поведению программы и потенциальным сбоям.

🚩Решение проблемы

Чтобы исправить проблему, нужно гарантировать, что std::mutex имеет более длительный срок жизни и доступен всем потокам, которые его используют.

🚩Правильные подходы

🟠Использование глобального или статического мьютекса
Если мьютекс используется для защиты глобальных или статических данных, сделайте его также глобальным или статическим.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void sharedFunction() {
    std::lock_guard<std::mutex> lock(mtx);
    // Доступ к общим данным
    std::cout << "Thread " << std::this_thread::get_id() << " is running\n";
}

int main() {
    std::thread t1(sharedFunction);
    std::thread t2(sharedFunction);

    t1.join();
    t2.join();

    return 0;
}

🟠Член класса
Если мьютекс используется для защиты данных объекта, объявите его членом класса.

#include <iostream>
#include <thread>
#include <mutex>

class SharedResource {
private:
    std::mutex mtx;
    int data;

public:
    void increment() {
        std::lock_guard<std::mutex> lock(mtx);
        ++data;
        std::cout << "Data: " << data << " from thread " << std::this_thread::get_id() << "\n";
    }
};

int main() {
    SharedResource resource;

    std::thread t1(&SharedResource::increment, &resource);
    std::thread t2(&SharedResource::increment, &resource);

    t1.join();
    t2.join();

    return 0;
}

🟠Использование умных указателей
Если мьютекс должен иметь динамическую продолжительность жизни, используйте умные указатели, такие как std::shared_ptr или std::unique_ptr.

#include <iostream>
#include <thread>
#include <mutex>
#include <memory>

void sharedFunction(std::shared_ptr<std::mutex> mtx) {
    std::lock_guard<std::mutex> lock(*mtx);
    // Доступ к общим данным
    std::cout << "Thread " << std::this_thread::get_id() << " is running\n";
}

int main() {
    auto mtx = std::make_shared<std::mutex>();

    std::thread t1(sharedFunction, mtx);
    std::thread t2(sharedFunction, mtx);

    t1.join();
    t2.join();

    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что в себе хранит указатель?

Указатель (pointer) — это переменная, которая хранит адрес другой переменной в памяти. По сути, указатель "указывает" на местоположение другого значения.

🚩Основные аспекты указателей

🟠Адрес памяти
Указатель хранит числовое значение, которое представляет адрес ячейки памяти. Этот адрес указывает на начальную позицию объекта, на который ссылается указатель.

🟠Тип данных
Указатели типизированы. Тип указателя указывает на тип данных, который находится по адресу. Это важно для правильной интерпретации данных, хранящихся по адресу.

🚩Объявление и инициализация указателей

🟠Объявление
Указатель объявляется с использованием символа * после типа данных.

      int* ptr; // Указатель на целое число
   double* dptr; // Указатель на число с плавающей  

🟠Инициализация
Указатели могут быть инициализированы адресом существующей переменной с помощью оператора & (адресной операции).

      int value = 42;
   int* ptr = &value; // ptr хранит адрес переменной  

Пример использования указателей

#include <iostream>

int main() {
    int value = 42;
    int* ptr = &value; // ptr хранит адрес переменной value

    std::cout << "Значение value: " << value << std::endl; // Вывод: 42
    std::cout << "Адрес value: " << &value << std::endl; // Вывод: Адрес переменной value
    std::cout << "Значение, на которое указывает ptr: " << *ptr << std::endl; // Вывод: 42
    std::cout << "Адрес, хранимый в ptr: " << ptr << std::endl; // Вывод: Адрес переменной value

    // Изменение значения через указатель
    *ptr = 10;
    std::cout << "Новое значение value: " << value << std::endl; // Вывод: 10

    return 0;
}

🚩Операции с указателями

🟠Доступ к значению по указателю
Используя оператор разыменования *, можно получить или изменить значение, на которое указывает указатель.

      int value = 42;
   int* ptr = &value;
   *ptr = 10; // Изменение значения value через  

🟠Адресные операции
& оператор используется для получения адреса переменной.
* оператор используется для разыменования указателя.

🟠Арифметика указателей
Указатели поддерживают арифметические операции, такие как сложение и вычитание, что позволяет перемещаться по массивам.

      int arr[] = {1, 2, 3, 4, 5};
   int* ptr = arr;
   std::cout << *(ptr + 1) << std::endl; // Вывод: 2 (второй элемент массива

🚩Типы указателей

🟠Указатель на объект
Указатель, который хранит адрес конкретного объекта.

      int value = 42;
   int* ptr = &value;

🟠Указатель на массив
Указатель может указывать на первый элемент массива, и арифметика указателей позволяет перемещаться по массиву.

   int arr[] = {1, 2, 3, 4, 5};
   int* ptr = arr;

🟠Указатель на функцию
Указатель, который хранит адрес функции.

      void func() {
       std::cout << "Hello, World!" << std::endl;
   }

   void (*funcPtr)() = func;
   funcPtr(); // Вызов функции через указатель

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что будет если вызвать дважды lock()?

Если вызвать дважды lock() на одном и том же объекте std::mutex из одного и того же потока, это приведет к взаимной блокировке (deadlock). Это происходит потому, что после первого вызова lock() мьютекс уже будет заблокирован данным потоком, и второй вызов lock() будет ожидать освобождения мьютекса, что никогда не произойдет, так как поток уже заблокировал мьютекс.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void threadFunction() {
    mtx.lock();  // Первый вызов lock()
    std::cout << "Locked once" << std::endl;
    
    // Попытка повторного захвата того же мьютекса приведет к взаимной блокировке
    mtx.lock();  // Второй вызов lock() - Deadlock
    std::cout << "Locked twice" << std::endl;

    mtx.unlock();
    mtx.unlock();
}

int main() {
    std::thread t(threadFunction);
    t.join();

    return 0;
}

🚩Как избежать взаимной блокировки

🟠Использование `std::recursive_mutex`: Этот тип мьютекса позволяет одному и тому же потоку захватывать мьютекс несколько раз без блокировки. Но следует использовать его осторожно, так как он может скрывать логические ошибки в коде.

#include <iostream>
#include <thread>
#include <mutex>

std::recursive_mutex rec_mtx;

void threadFunction() {
    rec_mtx.lock();  // Первый вызов lock()
    std::cout << "Locked once" << std::endl;
    
    rec_mtx.lock();  // Второй вызов lock()
    std::cout << "Locked twice" << std::endl;

    rec_mtx.unlock();
    rec_mtx.unlock();
}

int main() {
    std::thread t(threadFunction);
    t.join();

    return 0;
}

🟠Использование `std::unique_lock` или `std::lock_guard`: Эти обертки автоматически управляют блокировкой и разблокировкой мьютекса, обеспечивая корректное использование мьютексов.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void threadFunction() {
    std::lock_guard<std::mutex> lock(mtx);  // Автоматическая блокировка
    std::cout << "Locked once" << std::endl;
    
    // Повторный вызов lock() не требуется, так как lock_guard управляет мьютексом
}

int main() {
    std::thread t(threadFunction);
    t.join();

    return 0;
}

🟠Проверка состояния мьютекса с помощью `try_lock()`: Метод try_lock() пытается захватить мьютекс и возвращает false, если мьютекс уже захвачен, что предотвращает взаимную блокировку.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex mtx;

void threadFunction() {
    if (mtx.try_lock()) {  // Попытка захвата мьютекса
        std::cout << "Locked once" << std::endl;
        
        if (mtx.try_lock()) {  // Попытка повторного захвата
            std::cout << "Locked twice" << std::endl;
            mtx.unlock();
        }

        mtx.unlock();
    }
}

int main() {
    std::thread t(threadFunction);
    t.join();

    return 0;

Ставь 👍 и забирай 📚 Базу знаний

🤔 Какой контейнер используется в priority_queue?

priority_queue в C++ обычно реализован на базе std::vector с использованием кучи (heap) для управления приоритетами.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Зачем используются делиторы в умных указателях?

Делиторы – это специальные функции, которые определяют, как должен уничтожаться объект при освобождении памяти умным указателем.

Обычно std::unique_ptr и std::shared_ptr по умолчанию вызывают delete, но иногда это поведение нужно изменить.

🚩Когда нужны делиторы?

🟠Для работы с нестандартными ресурсами (не `new`)
Например, если объект создан через malloc(), fopen(), CreateFile(), то delete не подходит!
🟠Если нужно логировать или выполнять доп. действия при удалении
Можно добавить std::cout, логику очистки, сброс ресурсов.
🟠Если объект хранится в массиве (`new[]`)
delete не удалит массив корректно, нужно delete[].
🟠Если ресурс должен освобождаться особым способом
Например, в std::shared_ptr можно передать free(), fclose() или CloseHandle().

🚩Как передавать делитор в `std::unique_ptr`?

Пример: освобождение памяти от malloc() через std::free()

#include <iostream>
#include <memory>

int main() {
    std::unique_ptr<int, void(*)(void*)> ptr(malloc(sizeof(int)), free);
    *reinterpret_cast<int*>(ptr.get()) = 42;

    std::cout << "Значение: " << *reinterpret_cast<int*>(ptr.get()) << "\n";
}

Здесь free используется вместо delete, потому что память выделена malloc().
Пример: закрытие файла через std::fclose()

#include <iostream>
#include <memory>
#include <cstdio>

int main() {
    std::unique_ptr<FILE, decltype(&std::fclose)> file(fopen("test.txt", "w"), &std::fclose);

    if (file) {
        std::fprintf(file.get(), "Hello, world!\n");
    }
} // `fclose(file)` вызовется автоматически!

🚩Как передавать делитор в `std::shared_ptr`?

В std::shared_ptr можно передавать делитор прямо в конструкторе

#include <iostream>
#include <memory>

void customDeleter(int* ptr) {
    std::cout << "Удаляю объект: " << *ptr << "\n";
    delete ptr;
}

int main() {
    std::shared_ptr<int> ptr(new int(100), customDeleter);
} // В конце `customDeleter(ptr)` вызовется автоматически!

🚩Делитор для массивов (`delete[]`)

По умолчанию std::unique_ptr<int[]> сам вызывает delete[], но если std::unique_ptr<int> используется неправильно, то delete удалит только первый элемент массива!
Ошибка: delete вместо delete[]

std::unique_ptr<int> arr(new int[10]); // ОШИБКА! `delete` вызовет утечку памяти!

Правильный вариант

std::unique_ptr<int[], std::default_delete<int[]>> arr(new int[10]);

Ставь 👍 и забирай 📚 Базу знаний

🤔 В unordered_set поиск - константа?

std::unordered_set — это контейнер, который использует хеш-таблицу для хранения элементов. Это позволяет выполнять операции вставки, удаления и поиска с амортизированной константной временной сложностью \(O(1)\). Однако, важно понимать, что эта сложность — средняя, а не гарантированная в каждом конкретном случае.

🚩Принцип работы

Основан на механизме хеширования. Каждому элементу сопоставляется хеш-код, который определяет, в каком "ведре" (bucket) хеш-таблицы будет храниться элемент. Если хеш-функция хорошо распределяет значения, то доступ к элементу, его вставка или удаление могут выполняться за время \(O(1)\).

🚩Возможные сценарии сложности

🟠Лучший случай
Если хеш-функция равномерно распределяет элементы по всем "ведрам", то каждая операция (поиск, вставка, удаление) будет выполняться за амортизированное время \(O(1)\).
🟠Худший случай
В случае, когда многие или все элементы попадают в одно "ведро" (например, из-за плохой хеш-функции), операции с контейнером могут деградировать до \(O(n)\), где \(n\) — количество элементов в контейнере. В этом случае поведение контейнера будет похоже на список или массив, где каждый поиск требует линейного прохода по всем элементам.

🚩Реальные характеристики

Используются качественные хеш-функции для стандартных типов (например, для целых чисел, строк), что обеспечивает хорошее распределение элементов в большинстве случаев. Тем не менее, для пользовательских типов может потребоваться определение собственной хеш-функции, что важно для сохранения высокой производительности unordered_set.

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet;

    // Добавление элементов
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

    // Поиск элемента
    if (mySet.find(2) != mySet.end()) {
        std::cout << "Element found" << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что такое back_inserter, зачем он нужен?

std::back_inserter — это адаптер итератора из библиотеки STL, который позволяет удобно добавлять элементы в конец контейнера при использовании алгоритмов стандартной библиотеки (например, std::copy, std::transform и т. д.).

Он создает итератор-вставку (inserter iterator), который при попытке записи нового элемента фактически вызывает метод push_back() у контейнера.

🚩Почему он нужен?

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

🚩Пример использования

Без back_inserter (приведет к ошибке!)

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination; // Пустой контейнер

    // Ошибка! У destination нет места для элементов
    std::copy(source.begin(), source.end(), destination.begin());

    return 0;
}

Используем back_inserter (правильный вариант)

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> destination; // Начинаем с пустого контейнера

    // Используем back_inserter
    std::copy(source.begin(), source.end(), std::back_inserter(destination));

    // Вывод результата
    for (int num : destination) {
        std::cout << num << " ";
    }

    return 0;
}

Вывод

1 2 3 4 5

🚩Где используется `back_inserter`?

🟠**std::transform – Преобразование элементов**
Применяем функцию ко всем элементам и добавляем результат в новый контейнер

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> nums = {1, 2, 3, 4, 5};
    std::vector<int> squared;

    std::transform(nums.begin(), nums.end(), std::back_inserter(squared), 
                   [](int x) { return x * x; });

    for (int num : squared) {
        std::cout << num << " ";
    }

    return 0;
}

Вывод:

1 4 9 16 25

std::unique_copy – Удаление дубликатов

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> nums = {1, 2, 2, 3, 4, 4, 5};
    std::vector<int> unique_nums;

    std::unique_copy(nums.begin(), nums.end(), std::back_inserter(unique_nums));

    for (int num : unique_nums) {
        std::cout << num << " ";
    }

    return 0;
}

Вывод:

1 2 3 4 5

Ставь 👍 и забирай 📚 Базу знаний

🤔 Почему со стеком работать быстрее чем с кучей?

🟠Управление памятью
Стек: Память в стеке управляется автоматически. Когда вызывается функция, память для её локальных переменных выделяется одним блоком при входе в функцию и освобождается при выходе из неё. Эта операция выполняется за постоянное время (O(1)).
Куча: Память в куче управляется вручную (программистом) или через автоматическое управление памятью (например, сборщик мусора). Выделение и освобождение памяти в куче требуют поиска подходящего блока памяти, что может занимать больше времени (O(log n) или даже O(n)).

🟠Локальность данных
Стек: Данные в стеке расположены компактно и последовательно. Это означает, что доступ к данным будет быстрее из-за лучшего использования кэш-памяти процессора.
Куча: Данные в куче могут быть фрагментированы, что приводит к меньшей эффективности кэширования и увеличению времени доступа.

🟠Предсказуемость
Стек: Память в стеке выделяется и освобождается в строго определённом порядке (LIFO - Last In, First Out). Это делает операции со стеком предсказуемыми и упрощает управление памятью.
Куча: Память в куче может выделяться и освобождаться в произвольном порядке, что приводит к фрагментации и усложняет управление памятью.

🟠Минимизация накладных расходов
Стек: Операции выделения и освобождения памяти на стеке имеют минимальные накладные расходы, так как это просто смещение указателя стека.
Куча: Операции выделения и освобождения памяти в куче требуют более сложных алгоритмов и могут включать в себя дополнительные накладные расходы, такие как управление списками свободных блоков и слияние фрагментов.

#include <iostream>

void stackFunction() {
    int stackArray[1000]; // Массив на стеке
    // Работа с массивом
}

void heapFunction() {
    int* heapArray = new int[1000]; // Массив в куче
    // Работа с массивом
    delete[] heapArray; // Освобождение памяти
}

int main() {
    stackFunction(); // Быстрая работа со стеком
    heapFunction();  // Медленная работа с кучей
    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний

🤔 Что такое абстрактный класс?

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

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 Асимптотическая сложность в list?

std::list — это двусвязный список, где каждый элемент хранит ссылку на предыдущий и следующий элементы. Это даёт эффективное добавление и удаление элементов в любой части списка, но делает доступ по индексу медленным

🚩Разбор операций в `std::list` с примерами

Добавление в начало и конец — O(1)

std::list<int> lst;
lst.push_back(10);  // O(1)
lst.push_front(5);  // O(1)

Доступ по индексу — O(n)

auto it = std::next(lst.begin(), 2); // O(n), приходится идти от начала
std::cout << *it << std::endl;

Вставка и удаление по итератору — O(1)

auto it = lst.begin();
std::advance(it, 1);  // Двигаем итератор на 1 элемент (O(n))

lst.insert(it, 8);  // O(1), просто меняем указатели
lst.erase(it);      // O(1), просто изменяем ссылки соседних элементов

Поиск элемента — O(n)

auto it = std::find(lst.begin(), lst.end(), 8); // O(n)

Сортировка — O(n log n)

lst.sort(); // O(n log n), потому что используется сортировка слиянием

Ставь 👍 и забирай 📚 Базу знаний

🤔 Строгая гарантия исключений?

Гарантии безопасности исключений (exception safety) в C++ бывают трёх уровней:
Базовая гарантия (Basic Guarantee) – программа не падает, но состояние может быть некорректным.
Строгая гарантия (Strong Guarantee) – либо операция завершается успешно, либо объект остаётся в исходном состоянии.
Гарантия отсутствия исключений (No-throw Guarantee) – операция никогда не бросает исключения.

🚩Что такое строгая гарантия исключений?

Строгая гарантия исключений означает, что если во время выполнения метода выбросится исключение, объект останется в том же состоянии, в каком был до вызова метода.

#include <iostream>
#include <vector>

class BadContainer {
    std::vector<int> data;
public:
    void add(int value) {
        data.push_back(value);  // push_back() может выбросить исключение
    }

    void print() {
        for (int x : data) std::cout << x << " ";
        std::cout << std::endl;
    }
};

int main() {
    BadContainer c;
    c.add(1);
    c.add(2);
    c.add(3);
    c.print();  // Вывод: 1 2 3

    try {
        c.add(42);  // Может выбросить исключение (например, при нехватке памяти)
    } catch (...) {
        std::cout << "Ошибка!" << std::endl;
    }

    c.print();  // ?? Возможно, состояние испорчено!
}

🚩Как реализовать строгую гарантию?

Чтобы добиться строгой гарантии, используем Copy & Swap:
1. Создаём временный объект.
2. Выполняем изменения на временном объекте.
3. Если всё прошло успешно – меняем указатель (swap).

#include <iostream>
#include <vector>

class SafeContainer {
    std::vector<int> data;
public:
    void add(int value) {
        std::vector<int> temp = data;  // Копируем текущее состояние
        temp.push_back(value);         // Изменяем копию
        std::swap(data, temp);         // Если исключения нет, меняем данные
    }

    void print() {
        for (int x : data) std::cout << x << " ";
        std::cout << std::endl;
    }
};

int main() {
    SafeContainer c;
    c.add(1);
    c.add(2);
    c.add(3);
    c.print();  // Вывод: 1 2 3

    try {
        c.add(42);  // Если тут исключение, объект не изменится
    } catch (...) {
        std::cout << "Ошибка!" << std::endl;
    }

    c.print();  // Вывод: 1 2 3 (не испорчен!)
}

🚩Где ещё применяется строгая гарантия?

Операции присваивания (operator=) с Copy & Swap
Функции, изменяющие состояние контейнеров (std::vector::resize, std::map::insert)
Операции перевыделения памяти
Функции стандартной библиотеки (std::sort)

Ставь 👍 и забирай 📚 Базу знаний

🤔 Сложность удаление из конца у vector?

Удаление элемента из конца vector выполняется за O(1), поскольку не требуется сдвигать элементы. Это делает vector эффективным для операций добавления и удаления в конце. Операции вставки и удаления в конце vector работают за постоянное время, если не требуется перераспределение памяти.

Ставь 👍 если знал ответ, 🔥 если нет
Забирай 📚Базу знаний

🤔 В каких STL контейнерах внутри находится хеш таблица?

🚩В стандартной библиотеке шаблонов (STL) C++ хеш-таблица используется для реализации следующих контейнеров

🟠std::unordered_map
Ассоциативный контейнер, который хранит пары ключ-значение, с уникальными ключами. Обеспечивает амортизированное среднее время доступа, вставки и удаления за O(1).

🟠std::unordered_multimap
Ассоциативный контейнер, который хранит пары ключ-значение, где ключи могут повторяться. Обеспечивает амортизированное среднее время для основных операций за O(1), несмотря на дублирование ключей.

🟠std::unordered_set
Ассоциативный контейнер, который хранит уникальные элементы, неупорядоченные. Обеспечивает амортизированное среднее время для основных операций за O(1).

🟠std::unordered_multiset
Ассоциативный контейнер, который хранит элементы, где значения могут повторяться, неупорядоченные. Обеспечивает амортизированное среднее время для основных операций за O(1), несмотря на дублирование элементов.

Ставь 👍 и забирай 📚 Базу знаний

🤔 Какой подсчет ссылок имеется в shared_ptr?

В умном указателе shared_ptr используется два основных счётчика: счётчик сильных ссылок (strong reference count) и счётчик слабых ссылок (weak reference count). Эти счётчики управляют жизненным циклом объекта и связанных с ним ресурсов различными способами.

🚩Счётчик сильных ссылок

Увеличивается каждый раз, когда новый shared_ptr создаётся как копия другого shared_ptr или когда объект присваивается shared_ptr. Этот счётчик уменьшается, когда shared_ptr уничтожается или когда его значение присваивается другому объекту. Когда счётчик достигает нуля, это означает, что больше нет shared_ptr, управляющих этим объектом, и объект удаляется. Это гарантирует, что ресурсы, связанные с объектом, будут освобождены только тогда, когда не останется ни одной "сильной" ссылки.

🚩Счётчик слабых ссылок

Используется вместе с weak_ptr, другим типом умных указателей, который может ссылаться на объект, управляемый shared_ptr, но не увеличивает счётчик сильных ссылок. Слабые ссылки не предотвращают удаление объекта, к которому они имеют доступ, так как не участвуют в владении объектом. Счётчик слабых ссылок увеличивается каждый раз, когда создаётся weak_ptr, указывающий на объект, и уменьшается, когда такой weak_ptr уничтожается. Когда счётчик сильных ссылок достигает нуля и объект удаляется, память, выделенная под сам объект, освобождается, но "control block" (блок управления), содержащий счётчики, сохраняется до тех пор, пока счётчик слабых ссылок также не обнулится.

#include <iostream>
#include <memory>

int main() {
    std::shared_ptr<int> sp1 = std::make_shared<int>(10);
    std::cout << "sp1 use_count: " << sp1.use_count() << '\n';  // Вывод: 1

    {
        std::shared_ptr<int> sp2 = sp1;  // Копирование shared_ptr
        std::cout << "sp1 use_count after copy: " << sp1.use_count() << '\n';  // Вывод: 2

        std::weak_ptr<int> wp1 = sp1;  // Создание weak_ptr
        std::cout << "wp1 use_count: " << wp1.use_count() << '\n';  // Вывод: 2
    }  // sp2 выходит из области видимости, use_count уменьшается до 1

    std::cout << "sp1 use_count after sp2 destruction: " << sp1.use_count() << '\n';  // Вывод: 1
    return 0;
}

Ставь 👍 и забирай 📚 Базу знаний