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

🤔 Можно использовать в контексте нескольких потоков Shared_ptr и потокобезопасный он или нет?

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

🚩Потокобезопасность

🟠Безопасное копирование и удаление
Стандарт C++ гарантирует, что операции копирования и удаления shared_ptr являются потокобезопасными в том смысле, что вы можете безопасно копировать и удалять разные экземпляры shared_ptr из разных потоков, даже если они указывают на один и тот же объект.

🟠Счётчик ссылок
Модификации счётчика ссылок в нем (т.е. увеличение и уменьшение) являются атомарными операциями, что означает, что при изменении счётчика из разных потоков состояние счётчика останется консистентным и корректным.

🟠Ограничения потокобезопасности
Не рекомендуется изменять сам объект, на который указывает shared_ptr, из нескольких потоков без дополнительной синхронизации, так как shared_ptr не предоставляет потокобезопасность для доступа к объекту. Если несколько потоков изменяют один и тот же shared_ptr (не копии), например, присваивают ему новые значения или обнуляют его, это должно синхронизироваться, так как стандартная библиотека не гарантирует безопасность таких операций без внешней синхронизации.

🚩Рекомендации для использования в многопоточной среде

🟠Избегайте разделять один и тот же `shared_ptr` между потоками
Лучше дать каждому потоку собственную копию shared_ptr, что позволяет избежать конфликтов на запись.

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

🟠Рассмотрите использование std::atomic<std::shared_ptr<T>> для C++20 и выше
Эта оболочка предоставляет потокобезопасные операции на shared_ptr без необходимости явной синхронизации при изменении указателя.

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

🤔 Принцип Open/Closed (открытости/закрытости)?

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

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

🤔 Асимптотическая сложность в 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), потому что используется сортировка слиянием

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

🤔 Что известно об умных указателях?

Обёртки над обычными указателями, автоматически управляющие временем жизни объекта.
- std::unique_ptr — единственный владелец, нельзя копировать.
- std::shared_ptr — подсчёт ссылок, разделённое владение.
- std::weak_ptr — не влияет на счётчик shared_ptr, нужен для избежания циклов.
Плюсы:
- Безопасное управление памятью.
- Нет утечек при правильном использовании.
- Легче соблюдать RAII.

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

🤔 Что такое deque?

Это двусторонняя очередь, позволяющая добавлять и удалять элементы как с начала, так и с конца.
• Реализована как динамическая структура, состоящая из нескольких блоков памяти.
•Примеры использования: std::deque.

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

🤔 Какие есть два типа оператора delete?

В C++ существует два вида оператора delete
Одиночный delete (delete ptr) – удаляет один объект.
Массивный delete[] (delete[] ptr) – удаляет массив объектов.
Использование неправильного вида delete может привести к неопределённому поведению (UB).

🟠Одиночный `delete`
Используется для удаления одного объекта, созданного через new.

#include <iostream>

class Test {
public:
    Test() { std::cout << "Constructor\n"; }
    ~Test() { std::cout << "Destructor\n"; }
};

int main() {
    Test* obj = new Test(); // Выделяем память для одного объекта
    delete obj; // Вызывается деструктор, память освобождается
}

🟠Массивный `delete[]`
Используется для удаления массива объектов, созданного через new[].

#include <iostream>

class Test {
public:
    Test() { std::cout << "Constructor\n"; }
    ~Test() { std::cout << "Destructor\n"; }
};

int main() {
    Test* arr = new Test[3]; // Выделяем массив из 3 объектов
    delete[] arr; // Вызываются 3 деструктора, освобождается память
}

🟠Что будет, если забыть `[]` при удалении массива?
Если использовать delete вместо delete[], будет вызван только один деструктор, а память массива не будет полностью освобождена, что приведёт к утечке памяти.

Test* arr = new Test[3];
delete arr; // ❌ Не все деструкторы вызываются, UB!

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

🤔 В чем разница set и unordered_set?

Set — это отсортированное множество, которое хранит элементы в порядке возрастания и использует бинарное дерево для внутренней реализации. Unordered_set хранит элементы в произвольном порядке и использует хеш-таблицу для доступа к элементам. В set операции поиска, вставки и удаления имеют сложность O(log n), а в unordered_set — O(1) в среднем случае, но O(n) в худшем случае. Set предпочтителен, когда требуется поддерживать порядок элементов.

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

🤔 Что будет если вызвать дважды 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;

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

🤔 Как со стандартной библиотекой контейнеров?

Стандартная библиотека предоставляет набор контейнеров, таких как vector, list, deque, set, map и другие, которые позволяют удобно хранить и управлять данными. Они реализуют разные структуры данных, такие как массивы, списки, деревья и хэш-таблицы, предоставляя эффективные операции для различных сценариев.

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

🤔 Что такое 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;
}

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

🤔 Как работает счетчик ссылок в shared_ptr?

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

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

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

Гарантии безопасности исключений (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)

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

🤔 Что известно про вызовы throw exception в конструкторах и деструкторах?

- В конструкторе: если выброшено исключение, объект считается несозданным, вызываются деструкторы уже созданных членов класса, после чего исключение передается дальше.
- В деструкторе: выбрасывать исключения небезопасно, так как это может вызвать std::terminate(), если исключение не обработано (throw в ~Destructor() недопустимо).
- Если необходимо обработать ошибку в деструкторе, лучше использовать логирование или явный вызов try-catch.

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

🤔 Коллизия - когда для разных ключей получается одно и тоже хэш значение?

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

🚩Причины возникновения

🟠Ограниченное количество возможных хеш-значений
Поскольку количество возможных хеш-значений фиксировано (и обычно меньше, чем количество возможных ключей), статистически неизбежно, что разные ключи будут иметь одинаковые хеш-значения.
🟠Неидеальные хеш-функции
Хеш-функции могут не равномерно распределять хеш-значения, что увеличивает вероятность коллизий.

🚩Способы решения

🟠Цепочки (Chaining)
В этом методе каждая ячейка хеш-таблицы содержит указатель на список (или другую структуру данных, например, связный список), которые хранят все элементы, имеющие одинаковый хеш. Это простой и эффективный метод, но может потребовать больше памяти и времени при обращении к элементам.

🟠Открытая адресация (Open Addressing)
Включает в себя методы, такие как линейное пробирование, квадратичное пробирование и двойное хеширование. При возникновении коллизии метод находит следующую свободную ячейку в таблице для размещения нового элемента.

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

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

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

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

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

🤔 Как сделать операцию удаления элемента из начала, если порядок элементов не важен, в vector?

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

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

Этот подход позволяет выполнить операцию удаления за постоянное время O(1) вместо линейного O(n).

🚩Пример

void removeFirstElement(std::vector<int>& vec) {
    if (!vec.empty()) {
        std::swap(vec.front(), vec.back()); // Обмен первого и последнего элементов
        vec.pop_back(); // Удаление последнего элемента
    }
}

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

    std::cout << "Before removal: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    removeFirstElement(vec);

    std::cout << "After removal: ";
    for (int i : vec) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

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

🤔 Как можно проверить, что нет double exception?

Используйте функцию std::uncaught_exceptions() (C++17) или std::uncaught_exception() (до C++17) для проверки активного исключения.

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

🤔 Что можешь сказать про исключение в конструкторе?

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

🚩Что происходит при исключении в конструкторе?

Когда исключение возникает в конструкторе:
Объект не создаётся – вызов конструктора считается неудачным.
Деструктор НЕ вызывается – потому что объект не был полностью создан.
Уже созданные члены класса должны быть очищены вручную (если используются RAII-объекты, они сами очистят ресурсы).
Исключение должно быть обработано – либо перехвачено (try-catch), либо передано дальше.

🚩Пример исключения в конструкторе

#include <iostream>
#include <stdexcept>

class MyClass {
public:
    MyClass() {
        std::cout << "Конструктор\n";
        throw std::runtime_error("Ошибка в конструкторе!");
    }

    ~MyClass() {
        std::cout << "Деструктор\n";
    }
};

int main() {
    try {
        MyClass obj; // Попытка создать объект
    } catch (const std::exception& e) {
        std::cout << "Поймано исключение: " << e.what() << '\n';
    }
}

Вывод программы

Конструктор
Поймано исключение: Ошибка в конструкторе!

🚩Как правильно работать с исключениями в конструкторе?

🟠Использовать RAII
Лучший способ избежать утечек – использовать RAII (объекты, которые сами освобождают ресурсы в деструкторе).

#include <iostream>
#include <memory>
#include <stdexcept>

class MyClass {
private:
    std::unique_ptr<int> data; // Умный указатель RAII
public:
    MyClass() : data(std::make_unique<int>(42)) {
        throw std::runtime_error("Ошибка!");
    }
};

int main() {
    try {
        MyClass obj;
    } catch (const std::exception& e) {
        std::cout << "Ошибка: " << e.what() << '\n';
    }
}

🟠Использовать `try-catch` внутри конструктора
Если важно, чтобы объект всегда создавался, можно перехватывать исключение прямо в конструкторе.

class MyClass {
public:
    MyClass() {
        try {
            throw std::runtime_error("Ошибка!");
        } catch (...) {
            std::cout << "Ошибка обработана, объект создан\n";
        }
    }
};

🟠Использовать `noexcept(false)` или `noexcept(true)`
По умолчанию конструкторы могут выбрасывать исключения, но если мы точно знаем, что этого не произойдёт, лучше явно указать noexcept:

class SafeClass {
public:
    SafeClass() noexcept {
        std::cout << "Конструктор без исключений\n";
    }
};

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

🤔 Какие есть уровни exception гарантий?

1. No-throw Guarantee: метод или операция не выбрасывает исключений. Пример: деструкторы.
2. Strong Guarantee: при выбросе исключения состояние объекта или программы остаётся неизменным.
3. Basic Guarantee: состояние объекта остаётся корректным, но изменения могут быть частичными.
4. No Guarantee: программа может оказаться в некорректном состоянии при исключении.

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

🤔 В 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;
}

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