Оглавление
Data structures
| 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) |
STL containers
| 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 |
STL adapters
| 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
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.
Плюсы:
- ожидание захвата блокировки предполагается недолгим.
- контекст выполнения не позволяет переходить в заблокированное состояние.
Минусы:
- при длительной блокировке невыгоден - пустая трата процессорных ресурсов.
Smart Pointers
RAII (Resource Acquisition Is Initialization) - эффективный способ решения проблемы освобождения ресурсов, в том числе, в случае возникновения исключений. Умные указатели — это RAII классы, которые захватывают ресурс в конструкторе, работают с ним и освобождают его в деструкторе, являются не потокобезопасными.
Виды:
Unique_Ptr (сильный указатель - владеет ресурсом)
1 указатель может ссылаться только на один объект, конструктор копирования = delete, оператор копирования = delete. При вызове деструктора удаляет объект.
Shared_Ptr (сильный указатель - владеет ресурсом)
Производит два раздельных выделения памяти: аллокация управляемого объекта + Control Block(atomic shared_count (сильные ссылки), atomic weak_count (слабые ссылки), allocator, deleter), вместо одновременного выделения памяти make_shared. При вызове конструктора копирования или оператора копирования ++shared_count, при вызове коструктора перемещения, оператора перемещения или деструктора --shared_count. При shared_count == 0 удаляет объект + weak_count == 0 удаляет Control Block.
Передача Shared_Ptr в аргументе функции/метода
Передавать Shared_Ptr в качестве аргумента функции/метода/конструктора следует по const ссылке, по значению передавать только тогда, когда речь идет о работе в отдельном потоке (чтобы программист видел и имел это в виду).
Характеристики:
- не нужно делать лишнюю итерацию на увеличение shared_count (сильные ссылки) в Control Block.
- право собственности на объект имеют только классы/структуры и функции, работающие в многопотчном режиме, ну и место на стеке, где они создавались.
Weak_Ptr (слабый указатель - не владаеет ресурсом)
Создает с помощью 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.
Разницу между Shared_Ptr и Unique_Ptr
Указатель на базовый класс присваивается динамический объект производного класса, то
при разрушение объекта деструктор производного класса не вызовется, потому что удаление производится через указатель на базовый класс и для вызова деструктора компилятор использует раннее связывание (статический полиморфизм), поэтому может быть утечка памяти.
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()
make_unique/make_shared
Функции, не требующие дублирования типа (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.
Lambda
ЛЯМБДА (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 - два разных объекта
Function
std::function - контейнер с фиксированным протитопом, который может содержать объект любого типа и этот объект можно использовать как функцию или как callback. Это единый тип, к которому приводятся все замыкания (closer) с данной сигнатурой. function захватывает функтор/lambda, стирая ее тип: lambda хранится в куче как указатель void* привиденный с помощью reinterpret_cast к типу char[], а сам тип хранится отдельно в шаблонных параметрах.
ЗАМЫКАНИЕ (closer) (lvalue) - функциональный объект (функтор), создаваемый компилятором при генерации кода. С C++20 можно копировать и создать значение этого типа.
С помощью связывания (std::bind): можно хранить копии/ссылки/указатели объектов классов, члены классов, аргументы к функциям/методам. С помощью placeholder можно подставлять значения при вызове function.
Bind
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