C/C++ | Вопросы собесов

🤔 Что такое deque?

Deque (double-ended queue, двусторонняя очередь) — это последовательный контейнер в C++, который позволяет добавлять и удалять элементы как с начала, так и с конца очереди с постоянной временной сложностью O(1). Контейнер deque является частью стандартной библиотеки шаблонов (STL) и объявляется в заголовочном файле <deque>.

🚩Основные характеристики:

🟠Быстрый доступ к элементам:
deque обеспечивает доступ к элементам по индексу с амортизированной временной сложностью O(1).
🟠Двусторонняя очередь:
Позволяет эффективно добавлять и удалять элементы как с начала, так и с конца очереди.
🟠Динамический размер:
deque автоматически изменяет свой размер по мере добавления или удаления элементов, подобно vector.
🟠Не требует смежного хранения:
В отличие от vector, элементы deque могут быть размещены в различных сегментах памяти, что делает его более гибким для частых операций вставки и удаления.

🚩Основные операции:

🟠Добавление элементов:
push_back(), push_front()
🟠Удаление элементов:
pop_back(), pop_front()
🟠Доступ к элементам:
operator[], at(), front(), back()
🟠Размер и емкость:
size(), empty(), resize()
🟠Итераторы:
Поддержка итераторов для прохода по элементам

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;

    // Добавление элементов в конец
    dq.push_back(1);
    dq.push_back(2);
    dq.push_back(3);

    // Добавление элементов в начало
    dq.push_front(0);

    std::cout << "Deque elements: ";
    for (int elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    // Удаление элемента с конца
    dq.pop_back();

    // Удаление элемента с начала
    dq.pop_front();

    std::cout << "Deque elements after pop operations: ";
    for (int elem : dq) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

🤔 Расскажи о различиях ссылки и указателя

Ссылки (references) и указатели (pointers) в C++ служат для работы с памятью и позволяют передавать и изменять данные по адресу. Однако у них есть важные различия, которые влияют на использование и безопасность кода.

🚩Подробное объяснение с примерами

🟠Ссылка – это псевдоним для переменной
Ссылка является просто альтернативным именем для существующей переменной. Она не может существовать без объекта, к которому привязана.

#include <iostream>

void modify(int& ref) {
    ref = 20;  // Меняем значение переданного объекта
}

int main() {
    int a = 10;
    int& refA = a;  // refA теперь синоним a

    std::cout << "До: " << a << std::endl;  // 10
    modify(refA);
    std::cout << "После: " << a << std::endl;  // 20

    return 0;
}

🟠Указатель – это переменная, хранящая адрес
Указатели могут указывать на разные переменные, быть nullptr, поддерживают арифметику.

#include <iostream>

void modify(int* ptr) {
    if (ptr) {
        *ptr = 30;  // Разыменование указателя для изменения значения
    }
}

int main() {
    int a = 10;
    int* ptrA = &a;  // ptrA хранит адрес a

    std::cout << "До: " << a << std::endl;  // 10
    modify(ptrA);
    std::cout << "После: " << a << std::endl;  // 30

    return 0;
}

Указатели могут менять адреса, ссылки – нет

int a = 10, b = 20;
int* ptr = &a;  // ptr указывает на a
ptr = &b;  // Теперь ptr указывает на b

int& ref = a;  // ref – это псевдоним a
ref = b;  // Это НЕ смена привязки! Теперь a == 20

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

int arr[] = {1, 2, 3};
int* ptr = arr;  // ptr указывает на первый элемент

std::cout << *ptr << std::endl;    // 1
std::cout << *(ptr + 1) << std::endl;  // 2 (следующий элемент)
std::cout << *(ptr + 2) << std::endl;  // 3

🚩Когда использовать ссылки, а когда указатели?

Используйте ссылки, если объект гарантированно существует и не должен изменять свою привязку
Используйте указатели, если нужна возможность "ни на что не указывать" (nullptr) или менять адрес
В большинстве случаев лучше использовать ссылки, так как они безопаснее

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

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

Является одним из пяти принципов 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; }
};

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

🤔 Когда начинают жить и умирают глобальные и локальные переменные в С++?

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

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

🤔 Что знаешь о умных указателях?

Умные указатели (smart pointers) в C++ – это классы-обёртки для обычных указателей, которые автоматически управляют временем жизни объектов в динамической памяти. Они помогают избежать утечек памяти и делают код более безопасным, минимизируя вероятность ошибок с указателями.

🚩Зачем нужны умные указатели?

🟠Управление ресурсами
Автоматически освобождают память, когда объект больше не нужен.
🟠Исключение утечек памяти
С их помощью можно избежать забывания вызова delete.
🟠Улучшение безопасности
Умные указатели предотвращают доступ к освобождённой памяти (dangling pointers).
🟠Снижение сложности
RAII (Resource Acquisition Is Initialization) позволяет делегировать управление ресурсами объектам.

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

🟠`std::unique_ptr`
Уникальный указатель (unique pointer) обладает единственным владельцем объекта. После передачи владения объектом другому std::unique_ptr, исходный указатель становится недействительным.
Обеспечивает строгую семантику владения.
Лёгкий, так как не использует счётчики ссылок.
Не копируемый, но перемещаемый.

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass() { std::cout << "Создан объект\n"; }
    ~MyClass() { std::cout << "Удалён объект\n"; }
};

int main() {
    std::unique_ptr<MyClass> ptr1 = std::make_unique<MyClass>(); // Владеет объектом
    std::unique_ptr<MyClass> ptr2 = std::move(ptr1);            // Передача владения
    // ptr1 теперь nullptr, ptr2 владеет объектом
    return 0; // Объект автоматически удаляется
}

🟠`std::shared_ptr`
Разделяемый указатель (shared pointer) поддерживает разделённое владение объектом. Указатель освобождает память только тогда, когда все std::shared_ptr, ссылающиеся на объект, будут уничтожены.
Использует счётчик ссылок (reference count).
Обеспечивает совместное использование ресурса несколькими владельцами.

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass() { std::cout << "Создан объект\n"; }
    ~MyClass() { std::cout << "Удалён объект\n"; }
};

int main() {
    std::shared_ptr<MyClass> ptr1 = std::make_shared<MyClass>();
    std::shared_ptr<MyClass> ptr2 = ptr1; // Разделение владения
    // Указатель ptr1 и ptr2 указывают на один и тот же объект
    return 0; // Объект удаляется после уничтожения последнего shared_ptr
}

🟠`std::weak_ptr`
Слабый указатель (weak pointer) не увеличивает счётчик ссылок. Используется для предотвращения циклических зависимостей между std::shared_ptr.
Ссылается на объект, которым управляет std::shared_ptr.
Не владеет объектом.
Может проверять существование объекта с помощью expired().

#include <iostream>
#include <memory>

class MyClass {
public:
    MyClass() { std::cout << "Создан объект\n"; }
    ~MyClass() { std::cout << "Удалён объект\n"; }
};

int main() {
    std::shared_ptr<MyClass> shared = std::make_shared<MyClass>();
    std::weak_ptr<MyClass> weak = shared; // Слабая ссылка
    if (auto ptr = weak.lock()) { // Проверка на существование
        std::cout << "Объект существует\n";
    }
    shared.reset(); // Освобождаем shared_ptr
    if (weak.expired()) {
        std::cout << "Объект удалён\n";
    }
    return 0;
}

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

🤔 Как сделать так, чтобы в shared_ptr были утечки?

Утечки возможны при создании циклических ссылок, например, когда два объекта хранят shared_ptr друг на друга.

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

🤔 Что будет если сделать delete для nullptr?

В C++ delete nullptr безопасен и не делает ничего. Стандарт гарантирует, что delete не вызывает ошибок при передаче nullptr.

int* p = nullptr;
delete p; // НИЧЕГО НЕ ПРОИЗОЙДЁТ (без ошибки)

🚩Почему `delete nullptr` не вызывает ошибку?

Стандарт C++ (C++98, C++11, C++17, C++20) говорит:
> Если переданный в delete указатель равен nullptr, то delete ничего не делает.
Это сделано, чтобы избежать избыточных проверок в коде:

if (ptr) { // Проверка не нужна
    delete ptr;
}

🚩Как работает `delete` внутри?

Когда вызывается delete p, компилятор:
Проверяет, равен ли p nullptr. Если да → ничего не делает.
Вызывает деструктор объекта, если p не nullptr.
Освобождает память с помощью operator delete().

🚩Что с `delete[]`?

Тоже безопасно

int* arr = nullptr;
delete[] arr; // НИЧЕГО НЕ ПРОИЗОЙДЁТ

🚩Ошибки, которых `delete nullptr` помогает избежать

Безопасно

void destroy(int* p) {
    delete p; // Даже если p == nullptr, ошибки не будет
}

Опасность: двойное удаление
Хотя delete nullptr безопасен, удаление уже освобождённого указателя — ошибка!

int* p = new int(10);
delete p;  // Освободили память
delete p;  // ❌ НЕСКОЛЬКО DELETE - неопределённое поведение (UB)!

Решение: после delete занулять указатель

int* p = new int(10);
delete p;
p = nullptr; // Теперь повторный delete безопасен
delete p; // ОК, ничего не делает

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

🤔 Чем отличаются STL-контейнеры vector и array?

1. vector:
- Динамический массив, размер которого можно изменять.
- Управляет памятью автоматически.
- Подходит для сценариев, где размер данных неизвестен заранее.
2. array:
- Статический массив, размер которого фиксирован при создании.
- Не выделяет и не освобождает память динамически.
- Быстрее и эффективнее для небольших данных с фиксированным размером.

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

🤔 Как пофиксить проблему, когда 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;
}

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

🤔 Что будет, если для беззнаковой переменной, равной 0, сделать декремент?

Значение переменной перейдёт в максимальное значение типа (например, UINT_MAX для unsigned int).
Это связано с переполнением, так как беззнаковые типы используют арифметику по модулю.

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

🤔 Чем отличаются STL контейнеры vector и array?

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

🟠Различия в управлении памятью
std::vector использует динамическую память, выделяемую в куче (heap). Его размер может изменяться во время выполнения.
std::array использует статическую память, выделяемую в стеке (stack) или в статической области памяти, и его размер фиксирован на этапе компиляции.

#include <vector>
#include <array>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3}; // Размер может изменяться динамически
    vec.push_back(4);                 // Добавляем новый элемент

    std::array<int, 3> arr = {1, 2, 3}; // Размер фиксирован, нельзя добавить новый элемент

    std::cout << "Vector size: " << vec.size() << std::endl; // Выведет 4
    std::cout << "Array size: " << arr.size() << std::endl;  // Выведет 3

    return 0;
}

🟠Гибкость и изменение размера
std::vector позволяет изменять размер в процессе работы, автоматически выделяя новую память при необходимости.
std::array имеет фиксированный размер, который нельзя изменить после создания.

std::vector<int> v = {1, 2, 3};
v.push_back(4); // Увеличиваем размер

std::array<int, 3> a = {1, 2, 3};
// a.push_back(4); // Ошибка! У std::array нет метода push_back

🟠Производительность
std::array работает быстрее, так как все данные хранятся в непрерывном участке памяти и нет затрат на динамическое выделение.
std::vector может требовать дополнительное время при изменении размера, так как может потребоваться новое выделение памяти и копирование элементов.

#include <vector>
#include <array>
#include <chrono>
#include <iostream>

int main() {
    constexpr int N = 1'000'000;
    
    std::vector<int> vec(N, 1); // Динамический массив
    std::array<int, N> arr{};   // Статический массив
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) vec[i] += 1;
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector time: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " us" << std::endl;

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) arr[i] += 1;
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Array time: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() 
              << " us" << std::endl;

    return 0;
}

🟠Совместимость с C-API
std::array хранит данные как обычный C-массив, поэтому можно легко передавать его в функции, ожидающие int*.
std::vector использует динамическую память, но можно получить указатель на внутренний буфер с помощью data().

void processArray(int* arr, size_t size) {
    for (size_t i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
}

int main() {
    std::array<int, 3> arr = {1, 2, 3};
    std::vector<int> vec = {4, 5, 6};

    processArray(arr.data(), arr.size()); // std::array можно передавать в C-функции
    processArray(vec.data(), vec.size()); // std::vector тоже можно передавать

    return 0;
}

🟠Итераторы и стандартные алгоритмы
Оба контейнера поддерживают итераторы и совместимы со стандартными алгоритмами из #include <algorithm>

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

int main() {
    std::vector<int> vec = {3, 1, 4, 1, 5};
    std::array<int, 5> arr = {3, 1, 4, 1, 5};

    std::sort(vec.begin(), vec.end());
    std::sort(arr.begin(), arr.end());

    for (int n : vec) std::cout << n << " "; // 1 1 3 4 5
    std::cout << std::endl;
    for (int n : arr) std::cout << n << " "; // 1 1 3 4 5

    return 0;
}

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

🤔 Сложность поиска в бинарных деревьях логарифмическая, всегда ли так?

Нет, сложность поиска в бинарных деревьях не всегда логарифмическая. Она зависит от структуры дерева. Хотя логарифмическая сложность \(O(\log N)\) считается идеальной, это справедливо только для сбалансированных бинарных деревьев. Давайте разберём, когда эта сложность сохраняется, а когда может увеличиваться.

🚩Идеальный случай: сбалансированное бинарное дерево

Если бинарное дерево поиска (Binary Search Tree, BST) сбалансировано, глубина дерева пропорциональна \( \log_2 N \), где \(N\) – количество узлов. В этом случае поиск, вставка и удаление элемента выполняются за \(O(\log N)\).

🚩Худший случай: несбалансированное дерево

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

🚩Как избежать вырождения дерева?

Чтобы поддерживать сложность операций \(O(\log N)\), используют сбалансированные бинарные деревья, такие как:
🟠AVL-деревья
Поддерживают балансировку после каждой операции вставки/удаления.
🟠Красно-чёрные деревья
Гарантируют, что глубина дерева остаётся \(O(\log N)\).
🟠B-деревья и B+ деревья
Используются для работы с большими объёмами данных, например, в базах данных.

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

🤔 Может ли быть проблема со вставкой ста элементов через push_back?

Проблема может возникнуть, если память vector переполнена, что требует перераспределения и копирования всех существующих элементов в новый массив, увеличивая временные затраты. Для большого количества вставок рекомендуется заранее вызвать reserve, чтобы выделить необходимую память и избежать перераспределений.

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

🤔 Какие есть виды полиморфизма?

В программировании, включая C++, полиморфизм (многоформенность) – это способность объекта или функции принимать разные формы. Полиморфизм является ключевой концепцией объектно-ориентированного программирования (ООП).

🚩Компиляторный (статический) полиморфизм

Этот вид полиморфизма реализуется во время компиляции. Он достигается с помощью перегрузки функций (function overloading) и перегрузки операторов (operator overloading).

🟠Перегрузка функций
В перегрузке функций одна функция имеет несколько определений с разными параметрами.

#include <iostream>

void print(int value) {
    std::cout << "Целое число: " << value << std::endl;
}

void print(double value) {
    std::cout << "Вещественное число: " << value << std::endl;
}

void print(const std::string& value) {
    std::cout << "Строка: " << value << std::endl;
}

int main() {
    print(42);           // Вызов функции для int
    print(3.14);         // Вызов функции для double
    print("Привет!");    // Вызов функции для строки
    return 0;
}

🟠Перегрузка операторов
Перегрузка операторов позволяет определить, как стандартные операторы работают с пользовательскими типами данных.

#include <iostream>

class Complex {
    double real, imag;
public:
    Complex(double r, double i) : real(r), imag(i) {}

    Complex operator+(const Complex& other) const {
        return Complex(real + other.real, imag + other.imag);
    }

    void display() const {
        std::cout << real << " + " << imag << "i" << std::endl;
    }
};

int main() {
    Complex c1(1.0, 2.0), c2(3.0, 4.0);
    Complex c3 = c1 + c2; // Используется перегрузка оператора +
    c3.display();         // Вывод: 4 + 6i
    return 0;
}

🚩Рантаймный (динамический) полиморфизм

Этот вид полиморфизма проявляется во время выполнения программы. Реализуется с использованием виртуальных функций и наследования.

Виртуальные функции

#include <iostream>

class Animal {
public:
    virtual void sound() const { // Виртуальная функция
        std::cout << "Некоторый звук" << std::endl;
    }
};

class Dog : public Animal {
public:
    void sound() const override { // Переопределение
        std::cout << "Гав-гав" << std::endl;
    }
};

class Cat : public Animal {
public:
    void sound() const override { // Переопределение
        std::cout << "Мяу" << std::endl;
    }
};

void makeSound(const Animal& animal) {
    animal.sound(); // Динамическое определение, какой sound() вызывать
}

int main() {
    Dog dog;
    Cat cat;

    makeSound(dog); // Вывод: Гав-гав
    makeSound(cat); // Вывод: Мяу
    return 0;
}

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

🤔 Что пришло на смену auto_ptr?

На смену auto_ptr пришли умные указатели unique_ptr и shared_ptr. unique_ptr безопаснее управляет памятью и исключает случайное копирование, что было проблемой в auto_ptr. Эти новые указатели входят в стандарт C++11 и являются более надежными.

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

🤔 Каким свойством должен обладать объект, чтобы его можно было добавить в ассоциативные контейнеры в качестве ключа?

Чтобы объект можно было использовать в качестве ключа в ассоциативных контейнерах (std::set, std::map, std::unordered_set, std::unordered_map), он должен обладать определёнными свойствами, которые зависят от типа контейнера.

🚩Требования к объекту-ключу

🟠Для `std::map` и `std::set` (красно-чёрное дерево)
Класс или структура, используемая в качестве ключа, должна поддерживать операцию < (меньше).

#include <iostream>
#include <map>

struct Person {
    std::string name;
    int age;

    // Оператор сравнения, необходимый для std::map и std::set
    bool operator<(const Person& other) const {
        return age < other.age; // Ключи будут упорядочены по возрасту
    }
};

int main() {
    std::map<Person, std::string> people;
    people[{ "Alice", 30 }] = "Doctor";
    people[{ "Bob", 25 }] = "Engineer";

    for (const auto& [key, value] : people) {
        std::cout << key.name << " (" << key.age << "): " << value << '\n';
    }
}

🟠Для `std::unordered_map` и `std::unordered_set` (хеш-таблица)
Объект-ключ должен поддерживать операции:
Оператор == (для проверки равенства)
Функция-хешер (по умолчанию std::hash<T>)

#include <iostream>
#include <unordered_map>

struct Person {
    std::string name;
    int age;

    // Оператор равенства нужен для сравнения ключей
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// Специализация std::hash для структуры Person
namespace std {
    template <>
    struct hash<Person> {
        std::size_t operator()(const Person& p) const {
            return std::hash<std::string>()(p.name) ^ (std::hash<int>()(p.age) << 1);
        }
    };
}

int main() {
    std::unordered_map<Person, std::string> people;
    people[{ "Alice", 30 }] = "Doctor";
    people[{ "Bob", 25 }] = "Engineer";

    for (const auto& [key, value] : people) {
        std::cout << key.name << " (" << key.age << "): " << value << '\n';
    }
}

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

🤔 Зачем нам нужна move семантика?

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

🚩Зачем она нужна?

🟠Эффективность работы с ресурсами
Копирование больших объектов может быть очень затратным. Move семантика позволяет перенести ресурсы от одного объекта к другому без дорогостоящего копирования.

🟠Улучшение производительности
Перемещение (move) быстрее копирования, поскольку оно всего лишь переназначает указатели на ресурсы, вместо создания их копий. Это особенно важно в приложениях с высокой производительностью, таких как игры, обработка видео, базы данных.

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

Move семантика реализуется с помощью rvalue ссылок (ссылок на временные объекты) и специальных методов — move конструктора и move оператора присваивания.

#include <iostream>
#include <vector>

class MyClass {
public:
    int* data;
    size_t size;

    // Конструктор
    MyClass(size_t s) : size(s), data(new int[s]) {
        std::cout << "Constructing MyClass\n";
    }

    // Деструктор
    ~MyClass() {
        delete[] data;
        std::cout << "Destructing MyClass\n";
    }

    // Move конструктор
    MyClass(MyClass&& other) noexcept : data(other.data), size(other.size) {
        other.data = nullptr; // Обнуляем указатель у "старого" объекта
        other.size = 0;
        std::cout << "Move constructing MyClass\n";
    }

    // Move оператор присваивания
    MyClass& operator=(MyClass&& other) noexcept {
        if (this != &other) {
            delete[] data; // Освобождаем старый ресурс
            data = other.data;
            size = other.size;
            other.data = nullptr; // Обнуляем указатель у "старого" объекта
            other.size = 0;
            std::cout << "Move assigning MyClass\n";
        }
        return *this;
    }
};

int main() {
    MyClass a(10); // Создаем объект a
    MyClass b = std::move(a); // Перемещаем ресурсы от a к b
    
    return 0;
}

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

🤔 Чисто виртуальный метод зачем он нужен и какой синтаксис?

Чисто виртуальный метод в C++ определяет интерфейс для производных классов без предоставления реализации. Синтаксис: `virtual ReturnType MethodName() = 0;`. Класс, содержащий чисто виртуальные методы, становится абстрактным, и его нельзя инстанцировать напрямую.

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

🤔 В какой момент принимается решение, что хеш таблице надо перестроиться?

Решение о необходимости перестроения (рехеширования) хэш-таблицы принимается на основе значения нагрузки (load factor). Нагрузка — это отношение количества элементов в хэш-таблице к количеству бакетов (размеру массива).

🚩Порог нагрузки

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

Формула нагрузки:

\text{load factor} = \frac{\text{number of elements}}{\text{size of table}} 

Типичные пороговые значения: Пороговое значение нагрузки часто устанавливается в пределах от 0.5 до 1.0, в зависимости от реализации. Например, std::unordered_map в стандартной библиотеке C++ по умолчанию использует пороговое значение 1.0.

🚩Процесс рехеширования

1⃣Увеличение размера таблицы
Размер массива увеличивается, часто в два раза.

2⃣Перераспределение элементов
Все существующие элементы перераспределяются в новую таблицу с использованием новой хэш-функции или той же хэш-функции, но с новым размером таблицы.

🚩Пример

#include <iostream>
#include <list>
#include <vector>

class HashTable {
private:
    int currentSize;
    int numberOfElements;
    double loadFactorThreshold;
    std::vector<std::list<std::pair<int, std::string>>> table;

    void rehash() {
        int oldSize = currentSize;
        currentSize *= 2; // Увеличиваем размер таблицы
        std::vector<std::list<std::pair<int, std::string>>> newTable(currentSize);

        for (const auto& list : table) {
            for (const auto& pair : list) {
                int hashValue = pair.first % currentSize;
                newTable[hashValue].emplace_back(pair.first, pair.second);
            }
        }

        table = std::move(newTable);
    }

public:
    HashTable(int size = 10, double threshold = 0.75) 
        : currentSize(size), numberOfElements(0), loadFactorThreshold(threshold) {
        table.resize(currentSize);
    }

    int hashFunction(int key) {
        return key % currentSize;
    }

    void insertItem(int key, std::string value) {
        int hashValue = hashFunction(key);
        table[hashValue].emplace_back(key, value);
        numberOfElements++;

        // Проверяем, нужно ли выполнять рехеширование
        if (static_cast<double>(numberOfElements) / currentSize > loadFactorThreshold) {
            rehash();
        }
    }

    void displayTable() {
        for (int i = 0; i < currentSize; i++) {
            if (!table[i].empty()) {
                std::cout << "Bucket " << i << ": ";
                for (auto& pair : table[i]) {
                    std::cout << "[" << pair.first << ": " << pair.second << "] ";
                }
                std::cout << std::endl;
            }
        }
    }
};

int main() {
    HashTable ht;
    ht.insertItem(1, "one");
    ht.insertItem(2, "two");
    ht.insertItem(11, "eleven"); // Триггер рехеширования при необходимости

    ht.displayTable();
    // Вывод:
    // Bucket 1: [1: one] 
    // Bucket 2: [2: two] 
    // Bucket 11: [11: eleven]

    return 0;
}

🚩Когда происходит

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

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

🤔 Альтернативное решение для хранения float цены в качестве ключа?

Вместо хранения float можно:
1.Преобразовать цену в целочисленное значение (например, умножить на 100 или 1000 для точности до копеек/центов).
2.Хранить результат как int, что обеспечит точное сравнение и отсутствие ошибок округления.

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