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

🤔 В чем разница vector и list? Vector в C++ представляет собой динамический массив с последовательным размещением элементов в памяти, что обеспечивает быстрый доступ по индексу. List — это двусвязный список, где каждый элемент хранит указатели на соседние элементы, что обеспечивает быструю вставку и удаление. Вставка и удаление в vector могут быть медленными из-за необходимости сдвига элементов, тогда как в list такие операции происходят быстрее. Однако доступ по индексу в list требует обхода элементов, что делает его медленнее для случайного доступа. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 В unordered_set поиск — константа? Поиск в unordered_set имеет среднюю сложность O(1), но в худшем случае при хеш-коллизиях может быть O(n). Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

🤔 Принцип Open/Closed (открытости/закрытости)? Принцип открытости/закрытости гласит, что классы должны быть открыты для расширения, но закрыты для модификации. Это достигается за счёт использования абстракций, чтобы добавлять функциональность через наследование или композицию, не изменяя исходный код. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

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

🤔 Что такое deque? Это двусторонняя очередь, позволяющая добавлять и удалять элементы как с начала, так и с конца. • Реализована как динамическая структура, состоящая из нескольких блоков памяти. •Примеры использования: std::deque. Ставь 👍 если знал ответ, 🔥 если нет Забирай 📚Базу знаний

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

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

🤔 Что знаешь о умных указателях? Умные указатели (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 в многопоточном контексте требует определённой осторожности, поскольку он сам по себе имеет ограниченную потокобезопасность. Рассмотрим подробнее, что это значит и как можно безопасно использовать его в многопоточной среде. 🚩Потокобезопасность 🟠Безопасное копирование и удаление Стандарт 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 без необходимости явной синхронизации при изменении указателя. Ставь 👍 и забирай 📚 Базу знаний

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

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