🤔 Как работает виртуальность в C++?

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

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

Виртуальная функция определяется в базовом классе с ключевым словом virtual. Производный класс может переопределить эту функцию.

class Base {
public:
    virtual void display() const {
        std::cout << "Display from Base" << std::endl;
    }
};

class Derived : public Base {
public:
    void display() const override {
        std::cout << "Display from Derived" << std::endl;
    }
};

🚩Как работает vtable и vptr

🟠vtable (виртуальная таблица)
Это таблица указателей на виртуальные функции класса. Каждый класс, содержащий виртуальные функции, имеет свою собственную vtable. В vtable хранятся адреса функций, которые должны быть вызваны для объектов данного класса.

🟠vptr (указатель на vtable)
Это скрытый указатель в каждом объекте класса, содержащего виртуальные функции. Он указывает на vtable соответствующего класса. Когда объект создается, vptr инициализируется, указывая на vtable его класса.

#include <iostream>

class Base {
public:
    virtual void display() const {
        std::cout << "Display from Base" << std::endl;
    }
    virtual void show() const {
        std::cout << "Show from Base" << std::endl;
    }
};

class Derived : public Base {
public:
    void display() const override {
        std::cout << "Display from Derived" << std::endl;
    }
};

int main() {
    Base* b = new Derived();
    b->display(); // Вызовет Derived::display() благодаря vtable
    b->show();    // Вызовет Base::show() поскольку она не переопределена

    delete b;
    return 0;
}

🚩Процесс вызова виртуальных функций

🟠При компиляции
Компилятор создает vtable для каждого класса, содержащего виртуальные функции. Компилятор также добавляет скрытый vptr в каждый объект класса, который инициализируется для указания на соответствующую vtable.

🟠При выполнении
Когда вызывается виртуальная функция через указатель или ссылку на базовый класс, программа использует vptr для доступа к vtable и вызова правильной версии функции. Это обеспечивает динамическое разрешение вызова функции (runtime polymorphism).

🚩Полиморфизм и наследование

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

void callDisplay(const Base& obj) {
    obj.display();
}

int main() {
    Base b;
    Derived d;

    callDisplay(b); // Вызовет Base::display()
    callDisplay(d); // Вызовет Derived::display()

    return 0;
}

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

🤔 Сложность операции удаления элемента в vector

Удаление элемента в середине или начале std::vector имеет сложность O(n), так как все последующие элементы сдвигаются. Удаление элемента с конца (последнего) — O(1).

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

🤔 Можно использовать в контексте нескольких потоков 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 без необходимости явной синхронизации при изменении указателя.

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

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

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

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

🤔 В чем разница map и unordered_map?

std::map и std::unordered_map – оба являются ассоциативными контейнерами в C++, но они устроены по-разному и имеют разные скорости работы.

🚩Как устроены контейнеры?

🟠`std::map` – красно-чёрное дерево (сбалансированное BST)
Все ключи хранятся упорядоченно.
Операции insert, erase, find выполняются за O(log n).
Упорядоченность важна, если требуется поиск в диапазоне (lower_bound, upper_bound).

#include <map>
#include <iostream>

int main() {
    std::map<int, std::string> m;
    m[2] = "B";
    m[1] = "A";
    m[3] = "C";

    for (const auto& [key, value] : m) {
        std::cout << key << " -> " << value << '\n'; 
    }
}

Вывод (отсортирован!)

1 -> A  
2 -> B  
3 -> C  

🟠`std::unordered_map` – хеш-таблица
Нет сортировки, но поиск выполняется быстро – O(1) (в среднем).
Использует хеш-функцию, поэтому доступ к элементам зависит от хеширования.
Может быть медленным при коллизиях (O(n) в худшем случае).

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> um;
    um[2] = "B";
    um[1] = "A";
    um[3] = "C";

    for (const auto& [key, value] : um) {
        std::cout << key << " -> " << value << '\n';
    }
}

Вывод (порядок непредсказуем!)

2 -> B  
1 -> A  
3 -> C  

🚩Когда использовать `map`, а когда `unordered_map`?

🟠Используйте `std::map`, если:
Нужно сортированное хранение ключей.
Требуется поиск по диапазону (lower_bound, upper_bound).
Хеш-функция для ключей сложна или недоступна (например, std::pair без кастомного хешера).

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

🤔 Что такое spinlock?

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

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

🤔 Какие знаешь алгоритмы реализации коллизии?

В хеш-таблицах коллизия возникает, когда два разных ключа имеют одинаковый хеш и попадают в одну ячейку. Для её разрешения используют разные алгоритмы.

🚩Методы открытой адресации (Open Addressing)

🟠Линейное пробирование (Linear Probing)
Просто идём вперёд (с фиксированным шагом 1), пока не найдём свободное место.
Хешируем key1, попадаем в index = 3 → занято.
Проверяем index = 4 → занято.
Проверяем index = 5 → свободно, вставляем!

int hash(int key, int size) {
    return key % size;
}

int linearProbe(int key, int size, int table[]) {
    int index = hash(key, size);
    while (table[index] != -1) { // -1 означает пустую ячейку
        index = (index + 1) % size; // Двигаемся вперёд
    }
    return index;
}

🟠Квадратичное пробирование (Quadratic Probing)
Идём по квадратичному шагу: +1², +2², +3², …

index = (hash(key) + i²) % size;

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

index = (hash1(key) + i * hash2(key)) % size;

🚩Методы цепочек (Chaining)

🟠Связный список (Separate Chaining)
Каждая ячейка – это список (обычно std::list), в который добавляются элементы с одинаковым хешем.

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

class HashTable {
    std::vector<std::list<int>> table;
    int size;
public:
    HashTable(int s) : size(s), table(s) {}

    void insert(int key) {
        int index = key % size;
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < size; i++) {
            std::cout << i << ": ";
            for (int num : table[i])
                std::cout << num << " -> ";
            std::cout << "NULL\n";
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(10);
    ht.insert(15);
    ht.insert(20);
    ht.insert(25);
    ht.display();
}

🟠Хеширование с ко-хешированием (Coalesced Hashing)
Комбинация цепочек и открытой адресации:
В таблице хранятся указатели на следующий элемент с таким же хешем.
Не требует выделения памяти для списков.

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

🤔 Когда возникает самый худший случай поиска в unordered_set?

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

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

🤔 Что такое POD тип ?

POD (Plain Old Data) тип — это простой тип данных в C++, который совместим с C и обладает определенными свойствами, делающими его поведение предсказуемым и простым.

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

🟠Тривиальность (Trivial)
Тривиальный конструктор (конструктор по умолчанию, копирования и перемещения). Тривиальный деструктор. Компилятор генерирует их автоматически, если они не определены явно.

🟠Стандартная макетируемость (Standard Layout)
Все нестатические члены данных имеют один и тот же доступ (public, private, или protected). Нет виртуальных функций и нет виртуальных базовых классов. Все базовые классы являются POD типами. Стандартные правила выравнивания и макетирования данных в памяти.

struct MyPOD {
    int x;
    float y;
};

Пример НЕ POD типа

struct NonPOD {
    int x;
    virtual void func() {}  // Наличие виртуальной функции делает тип не POD
};

🚩Применение POD типов

🟠Совместимость с C
Поскольку POD типы совместимы с C, они могут быть безопасно использованы в смешанных C/C++ программах.

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

🟠Оптимизация
Компиляторы могут лучше оптимизировать код с POD типами из-за их простоты и предсказуемости.

🚩Проверка, является ли тип POD

В C++11 и новее можно использовать стандартную библиотеку для проверки, является ли тип POD

#include <type_traits>

struct MyPOD {
    int x;
    float y;
};

struct NonPOD {
    int x;
    virtual void func() {}
};

int main() {
    std::cout << std::is_pod<MyPOD>::value << std::endl;  // вывод: 1 (true)
    std::cout << std::is_pod<NonPOD>::value << std::endl; // вывод: 0 (false)
    return 0;
}

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

🤔 Какие известны виды итераторов?

В стандартной библиотеке есть несколько видов итераторов:
- InputIterator – предназначен только для однократного чтения данных.
- OutputIterator – позволяет записывать данные в контейнер.
- ForwardIterator – поддерживает однократное чтение и запись, может быть использован многократно.
- BidirectionalIterator – поддерживает движение в обоих направлениях (вперед и назад).
- RandomAccessIterator – обеспечивает доступ к любому элементу за O(1), работает как указатель.

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

🤔 Как называется одинаковый результат после применения хэш функции?

Одинаковый результат после применения хэш-функции называется коллизией.

🚩Что такое коллизия?

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

🚩Почему коллизии возникают?

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

🚩Как справляться с коллизиями?

Есть несколько способов обработки коллизий в хэш-таблицах:

🟠Метод цепочек (chaining)
Каждое значение хэша хранит список элементов, которые получили одинаковый хэш. При добавлении нового ключа он просто добавляется в связанный список.

#include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
    int size;
    vector<list<int>> table;

public:
    HashTable(int s) : size(s), table(s) {}

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

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
    }

    void display() {
        for (int i = 0; i < size; i++) {
            cout << i << ": ";
            for (int key : table[i]) {
                cout << key << " -> ";
            }
            cout << "NULL" << endl;
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(10);
    ht.insert(15);
    ht.insert(20);
    ht.insert(7);
    ht.insert(2);
    ht.display();
    return 0;
}

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

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

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

🤔 Что будет если в функции помеченной как noexcept бросить исключение?

Если функция, помеченная как `noexcept`, выбросит исключение, программа вызовет `std::terminate()`, что приведёт к немедленному завершению выполнения. Это связано с тем, что `noexcept` гарантирует, что функция не выбросит исключений, и нарушение этого обещания считается критической ошибкой. Использование `noexcept` позволяет оптимизировать код, так как компилятор может делать определённые оптимизации, полагаясь на то, что исключения не будут выбрасываться. Следует избегать выбрасывания исключений в таких функциях.

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

🤔 Какая сложность поиска в set и unordered_set?

Контейнеры set и unordered_set представляют собой различные структуры данных, каждая из которых имеет свои особенности по скорости выполнения основных операций, включая поиск. Вот как работают эти контейнеры и какова сложность их операций поиска:

🚩set

Реализуется как сбалансированное двоичное дерево поиска, обычно как красно-черное дерево. Он хранит элементы в отсортированном порядке, что позволяет выполнять двоичный поиск. Сложность поиска: Поиск в нем выполняется за логарифмическое время, \(O(\log n)\), где \(n\) — количество элементов в set. Эта эффективность достигается за счёт использования структуры сбалансированного дерева, которое позволяет быстро делить данные на меньшие сегменты.

🚩unordered_set

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

Для set

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {5, 3, 9, 1};
    auto search = mySet.find(3);
    if (search != mySet.end()) {
        std::cout << "Found " << *search << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

Для unordered_set

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> mySet = {5, 3, 9, 1};
    auto search = mySet.find(3);
    if (search != mySet.end()) {
        std::cout << "Found " << *search << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    return 0;
}

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

🤔 Какая сложность поиска в set и unordered_set?

В set поиск имеет сложность O(log n), так как он реализован как сбалансированное бинарное дерево. В unordered_set сложность поиска в среднем O(1), но в худшем случае (при большом количестве коллизий) может достигать O(n).

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

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

🟠Управление памятью
Стек: Память в стеке управляется автоматически. Когда вызывается функция, память для её локальных переменных выделяется одним блоком при входе в функцию и освобождается при выходе из неё. Эта операция выполняется за постоянное время (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;
}

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

🤔 Если std::move() не перемещает данные, то что их перемещает?

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

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

🤔 Для чего при перегрузке оператора присваивания возвращать ссылку?

При перегрузке оператора = в C++ принято возвращать ссылку на текущий объект (*this). Это позволяет цепочечное присваивание (a = b = c), а также улучшает производительность и удобство использования.

🚩Правильная сигнатура оператора `=`

class MyClass {
public:
    MyClass& operator=(const MyClass& other) {
        if (this != &other) {  // Защита от самоприсваивания
            // Копируем данные
        }
        return *this; // Возвращаем ссылку на текущий объект
    }
};

🚩Что даёт возвращение ссылки (`T&`)?

Поддержка цепочки присваивания (a = b = c)

a = b = c;  // Интерпретируется как a = (b = c);

Пример

#include <iostream>

class MyClass {
public:
    int value;
    MyClass(int v) : value(v) {}

    MyClass& operator=(const MyClass& other) {
        if (this != &other) { // Защита от самоприсваивания
            value = other.value;
        }
        return *this;
    }
};

int main() {
    MyClass a(1), b(2), c(3);
    a = b = c; // Работает, потому что `b = c` возвращает ссылку на `b`
    std::cout << "a: " << a.value << ", b: " << b.value << ", c: " << c.value << std::endl;
}

Вывод

a: 3, b: 3, c: 3

🟠Убираем лишнее копирование (повышаем производительность)
Если оператор = вернёт не ссылку, а объект, то произойдёт лишнее копирование.

Плохо (возвращаем объект, а не ссылку)

MyClass operator=(const MyClass& other) { // ⚠️ Ошибка: возвращаем объект
    value = other.value;
    return *this; // Здесь создаётся временный объект (лишняя копия!)
}

Хорошо (возвращаем T&)

MyClass& operator=(const MyClass& other) { // ✅ Возвращаем ссылку
    value = other.value;
    return *this;
}

🚩Поддержка `if (a = b)`

Если оператор = вернёт ссылку, мы можем использовать его в условии:

if ((a = b).value == 42) { // ОК
    std::cout << "Присваивание выполнено, a == 42";
}

🚩Что если вернуть `void`?

Если оператор = вернёт void, цепочка a = b = c; не будет работать.

class MyClass {
public:
    void operator=(const MyClass& other) { // ⚠️ Ошибка!
        value = other.value;
    }
};

int main() {
    MyClass a, b, c;
    a = b = c; // ❌ Ошибка: `b = c` возвращает void, а `a = void` не работает!
}

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

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

В list сложность вставки и удаления — O(1), так как он двусвязный. В vector вставка и удаление в конец — O(1), а в произвольное место — O(n) из-за необходимости сдвига элементов.

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

🤔 За счет чего появляетcя амортизированная константная сложность в map?

std::map реализован как самобалансирующееся красно-чёрное дерево (Red-Black Tree).
Вставка (insert)
Поиск (find)
Удаление (erase)
выполняются за O(log n) в худшем и среднем случае.
Однако std::map не имеет амортизированной O(1) сложности, как std::unordered_map.
Амортизированная сложность O(1) появляется в std::unordered_map, но не в std::map!

🚩Как работает балансировка?

Каждая операция (insert, erase) перестраивает дерево так, чтобы его высота оставалась O(log n). Это достигается с помощью поворотов (rotate left, rotate right) и перекраски узлов.
Вставка нового элемента иногда требует перестройки дерева, но в среднем это занимает O(log n).

        10
       /  \
      5    20

🚩Почему `std::unordered_map` имеет амортизированное O(1)?

В std::unordered_map используется хеш-таблица, где:
Операции insert, find, erase – O(1) в среднем (поиск по хешу).
Но если возникает коллизия (несколько ключей в одном бакете), сложность ухудшается до O(n).
Чтобы избежать O(n), std::unordered_map использует rehash (перехеширование).
При увеличении элементов контейнер расширяет бакеты.
Операции разделяются по разным вызовам → за счёт этого амортизированная сложность O(1).

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

🤔 Что известно о ключевом слове override?

Ключевое слово override используется для явного указания, что метод переопределяет виртуальный метод базового класса. Оно предотвращает ошибки, связанные с неправильным именованием или сигнатурой методов.

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