| Name structure | Indexation | Search | Inserting | Deleting | Memory |
|---|---|---|---|---|---|
| Binary Heap | - | - | O(log(n)) | O(log(n)) | O(n) |
| Binary Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| LinkedList | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | O(1) | O(1) | O(1) | O(1) | O(n) |
| Queue | - | - | O(1) | O(1) | O(n) |
| Stack | - | - | O(1) | O(1) | O(n) |
| Name STL container | Indexation | Search | Inserting | Deleting | Memory | Iterator invalidation | Iterator category |
|---|---|---|---|---|---|---|---|
| array | O(1) | - | - | - | O(n) | + | RA |
| vector | O(1) | - | O(1) back | O(n) | O(n) | + | RA |
| list | O(n) | O(n) | O(1) | O(1) | O(n) | - | BD |
| forward_list | O(n) | O(n) | O(1) front | O(1) front | O(n) | - | F |
| deque | O(1) | O(1) | O(1) back,front | O(1) | O(n) | + | RA |
| unordered_set | O(1) | O(1) | O(1) | O(1) | O(n) | + | F |
| unordered_map | O(1) | O(1) | O(1) | O(1) | O(n) | + | F |
| unordered_multiset | O(1) | O(1) | O(1) | O(1) | O(n) | - | F |
| unordered_multimap | O(1) | O(1) | O(1) | O(1) | O(n) | - | F |
| set | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | - | BD |
| map | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | - | BD |
| multiset | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | - | BD |
| multimap | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | - | BD |
| Name STL adapter | Indexation | Search | Inserting | Deleting | Memory |
|---|---|---|---|---|---|
| queue | - | - | O(1) | O(1) | O(n) |
| stack | - | - | O(1) | O(1) | O(n) |
| priority_queue | - | - | O(log(n)) | O(log(n)) | O(n) |
Spinlock - аналог mutex, который использует цикл активного ожидания (while(true)) и атомарный флаг (std::atomic) входа/выхода из цикла без изменения состояния потока, что приводит к трате процессорного времени на ожидание освобождения блокировки другим потоком, но тратит меньше времени на процедуру блокировки потока, т.к. не требуется задействование планировщика задач (Scheduler) с переводом потока в заблокированное состояние через походы в ядро процессора.
Методы:
- lock - происходит захват spinlock текущим потоком и блокирует доступ к данным другим потокам; или поток блокируется, если spinlock уже захвачен другим потоком.
- unlock - освобождение spinlock, разблокирует данные другим потокам.
Замечание: При повторном вызове lock - вылезет exception или приведет к состоянию бесконечного ожидания, при повторном вызове unlock - ничего не будет. - try_lock - происходит захват spinlock текущим потоком, НО НЕ блокирует доступ к данным другим потокам, а возвращает значение: true - можно захватить spinlock / false - нельзя; НО МОЖЕТ возвращать ложное значение, потому что в момент вызова try_lock spinlock может быть уже lock/unlock. Использовать try_lock в редких случаях, когда поток мог что-то сделать полезное, пока ожидает unlock.
Плюсы: - ожидание захвата блокировки предполагается недолгим. - контекст выполнения не позволяет переходить в заблокированное состояние. Минусы: - при длительной блокировке невыгоден - пустая трата процессорных ресурсов.
RAII (Resource Acquisition Is Initialization) - эффективный способ решения проблемы освобождения ресурсов, в том числе, в случае возникновения исключений. Умные указатели — это RAII классы, которые захватывают ресурс в конструкторе, работают с ним и освобождают его в деструкторе, являются не потокобезопасными. Виды:
1 указатель может ссылаться только на один объект, конструктор копирования = delete, оператор копирования = delete. При вызове деструктора удаляет объект.
Производит два раздельных выделения памяти: аллокация управляемого объекта + Control Block(atomic shared_count (сильные ссылки), atomic weak_count (слабые ссылки), allocator, deleter), вместо одновременного выделения памяти make_shared. При вызове конструктора копирования или оператора копирования ++shared_count, при вызове коструктора перемещения, оператора перемещения или деструктора --shared_count. При shared_count == 0 удаляет объект + weak_count == 0 удаляет Control Block.
Создает с помощью lock - Shared_Ptr, но не выделяет память для Control Block(atomic shared_count (сильные ссылки), atomic weak_count (слабые ссылки), allocator, deleter) - это делает сам Shared_Ptr. При вызове конструктора, конструктора копирования или оператора копирования ++weak_count. При вызове конструктора перемещения, оператора перемещения или деструктора --Weak_Ptr. При shared_count == 0 + Weak_Ptr == 0 удаляет Control Block, но НЕ УДАЛЯЕТ сам объект, это может сделать ТОЛЬКО - Shared_Ptr.
Нужен для решения проблемы с «висячим указателем» или «циклической зависимостью», где два объекта взаимноссылаются на друг друга и при выходе видимости стека их деструкторы не будут вызваны -> утечка памяти. Идет в связке с Shared_Ptr, но не увеличивает счетчик ссылок shared_count.
Из Weak_Ptr легко создать умный указатель Shared_Ptr, из сырого указателя - это низкоуровневое управление динамической памятью (гиблое дело).
При создании нескольких Shared_Ptr из «сырых указателей» создается свой контрольный блок, они оказываются несвязанные друг с другом и это приводит к двойному удалению объекта.
При создании нескольких Shared_Ptr из Weak_Ptr, они будут иметь один контрольный блок.
При условии, что в Weak_Ptr есть объект, с помощью метода lock() создается Shared_Ptr.
expired() - проверяет объект на nullptr.
Указатель на базовый класс присваивается динамический объект производного класса, то
при разрушение объекта деструктор производного класса не вызовется, потому что удаление производится через указатель на базовый класс и для вызова деструктора компилятор использует раннее связывание (статический полиморфизм), поэтому может быть утечка памяти.
struct A
{
~A()
{
std::cout << "~A()" << std::endl;
}
};
struct B : A
{
~B()
{
std::cout << "~B()" << std::endl;
}
};
shared_ptr<A> base_ptr1 = make_shared<B>();
unique_ptr<A> base_ptr2 = make_unique<B>();
shared_ptr: деструктор struct A - невиртуальный, поэтому должно вызваться только деструктор: ~A() - это неверно. std::shared_ptr хранит внутри себя deleter, который знает тип объекта, переданного в конструктор, и поэтому будут вызываться все деструкторы:
~B()
~A()
unique_ptr: если заменить std::shared_ptr на std::unique_ptr, то в std::unique_ptr deleter является частью типа, поэтому будет вызываться только деструктор:
~A()
Функции, не требующие дублирования типа (auto ptr = make_unique/make_shared(10)). Стоит использовать make_unique/make_shared вместо unique_ptr/shared_ptr(new T()).
make_shared - функция нужна для повышения производительности по сравнению shared_ptr(new), которая с помощью вызова конструктора требуют минимум две аллокации: одну — для размещения объекта, вторую — для Control Block.
Плюсы:
- невозможна утечка памяти.
- не нужно писать new.
- там не нужно дублировать тип shared_ptr number(new int(1)) -> auto number = make_shared(1).
- make_shared - производит одно выделение памяти вместе: аллокация управляемого объекта + Control Block(shared_count (сильные ссылки), weak_count (слабые ссылки), allocator, deleter), следовательно они будут находиться в одном участке памяти и работать с ними быстрее, по сравнению с раздельным выделением памяти в shared_ptr.
Минусы:
- не могут использовать deleter.
- перегруженные operator new и operator delete в классе будут проигнорированы в make_unique/make_shared.
- make_shared не может вызывать private конструкторы внутри метода (например, синглтон).
- для make_shared нужно ждать shared_count == weak_count == 0, чтобы удалить объект + Control Block.
ЛЯМБДА (rvalue) — это просто анонимная функция. Позволяет создавать объект (замыкание) в именную локальную функцию, которую можно создать внутри какой-нибудь функции.
ЗАМЫКАНИЕ (closer) (lvalue) - функциональный объект (функтор), создаваемый компилятором при генерации кода.
- В списке захвата (capture list) [] при указании переменных - создаются private члены класса с такими же типами и именами. С C++14 можно использовать move семантику.
- В списке аргументов (), который является необязательным и можно не писать (), при указании переменных - создается конструктор, куда передаются значения. С C++20 можно передавать шаблоны только в качестве аргументов.
- Переопределение operator() const - означает, что в константном методе локальные переменные (члены класса) захваченные по значению менять - нельзя, по ссылке - можно. Обойти это ограничение можно с помощью mutable, которое убирает const у operator() и позволяет изменять копии локальных переменных, но не оригиналы. Для глобальных/статических переменных это правило не распространяется.
- Перегружать лямбды - нельзя, но можно можно делать имитацию перегрузки с помощью шаблонных миксин (template mixin).
ЗАМЕЧАНИЕ: лямбда-функция ≠ замыкание (closer).
С C++20 можно копировать и создать значение этого типа.
Пример:
using SQRT = decltype([](int x)
{
return std::pow(x, 2);
});
SQRT sqrt1; // Создание типа
auto sqrt2 = sqrt1; // Копирование значение
СИНТАКСИС LAMBDA:
auto lambda = [](){}();
lambda - замыкание (closer). Это объект, который имеет тип.
[] - список захвата (capture list), в котором указываются локальные переменные, которые будут изменяться.
() - cписок аргументов, если их нет (можно не писать).
constexpr - может вычисляться на этапе компиляции, но с C++20 идет по-умолчанию (можно не указывать).
mutable - позволяет изменять копии локальных переменных, но не оригиналы. Для глобальных/статических переменных это правило не распространяется (mutable можно не указывать).
noexcept - спецификатор, указывающий что лямбда-выражение не создает никаких исключений (можно не указывать).
-> - выводимый тип (можно не указывать).
{} - тело функции.
Immediate invocation: вызов безымянной функции:
[](){}();
auto lambda2 = lambda; // lambda и lambda2 - два разных объекта
std::function - контейнер с фиксированным протитопом, который может содержать объект любого типа и этот объект можно использовать как функцию или как callback. Это единый тип, к которому приводятся все замыкания (closer) с данной сигнатурой. function захватывает функтор/lambda, стирая ее тип: lambda хранится в куче как указатель void* привиденный с помощью reinterpret_cast к типу char[], а сам тип хранится отдельно в шаблонных параметрах.
ЗАМЫКАНИЕ (closer) (lvalue) - функциональный объект (функтор), создаваемый компилятором при генерации кода. С C++20 можно копировать и создать значение этого типа. С помощью связывания (std::bind): можно хранить копии/ссылки/указатели объектов классов, члены классов, аргументы к функциям/методам. С помощью placeholder можно подставлять значения при вызове function.
std::bind - функтор или шаблонная функция, а также инструмент для каррирования и частичного применения функции с несколькими аргументами. bind выделяет память на стеке, а не в куче как function. Функциональный объект (функтор) - класс, у которого переопределен operator(). Объекты этого класса могут вести себя как функция.
СРАВНЕНИЕ bind и Lambda:
- std::bind удобнее использовать, когда много аргументов в фукнции.
- Lambda удобнее использовать, когда сложное выражение или их несколько.
Каррирование (std::currying) - функция, принимающая только один аргумент, которая продолжает возвращать функции до тех пор, пока не будут отправлены все ее аргументы. В случае, если переданы не все аргументы, функция их запомнит - это возможно с помощью замыкания (closer). Частичное применение — это возможность вызывать функции N аргументов передавая в них только часть этих аргументов, результатом такого вызова будет другая функция от оставшихся аргументов. Каррирование ≠ частичное применение функции. Отличие: Каррирование принимает по 1 аргументу, частичное применение функции принимает > 1 аргумента.
Плюсы над обычными указателями на функции (function pointer):
- умеет захватывать переменные контекста [this, &].
- может работатать как с lambda-функциями, так и с обычными функциями.
- есть связывание с помощью std::bind: можно хранить копии/ссылки/указатели объектов классов, члены классов, аргументы к функциям/методам. С помощью placeholder можно подставлять значения при вызове function.
- может рекурсивно вызывать самого себя.
Минусы над обычными указателями на функции (function pointer):
- является более затратным по ресурсам, т.к. требуется выделение памяти в куче. ОТЛИЧИЕ Lambda от function:
- имеют разные типы.
- std::function захватывает функтор/lambda, стирая ее тип: lambda хранится в куче как указатель void* привиденный с помощью reinterpret_cast к типу char[], а сам тип хранится отдельно в шаблонных параметрах.
- в std::function выделение памяти происходит в куче, в lambda - на стеке, поэтому std::function теряет в производительности.
- std::function может вызывать самого себя рекурсивно.
shared_ptr, weak_ptr, make_shared, enable_shared_from_this
Ох уж этот std::make_shared…
Can you make a std::shared_ptr manage an array allocated with new T?
What can std::remove_extent be used for?
shared_ptr
shared_ptr