Двусвязный список: поиск элемента по значению, вставка элемента, удаление элемента. Реализация функции удаления элемента из двусвязного списка. Основные методы std::list. Пример работы с std::list
std::list - двусвязный список:
template <typename T>
class list {
struct node {
node* prev;
node* next;
T value;
};
node* first;
node* last;
// C++11
size_t size;
};Оценки сложности (N - размер контейнера/количество элементов):
- Вставка/удаление - O(1)
- Вставка/удаление нескольких элементов - O(M), где M - количество последовательных элементов, над которыми проивзодятся манипуляции.
- Поиск элемента - O(N)
- Размер - O(1) после C++11, до этого O(N)
Основные методы:
- push_back, push_front, insert - вставка элемента в конец, начало и на произвольную позицию (причем для произвольной позиции возможна вставка нескольких элментов)
- pop_back, pop_front, erase - аналогичные методы для удаления соответствующих элементов
- front, back - методы для доступа к первому и последнему элементам списка. Сложность O(1)
- emplace_back, emplace_front, emplace - вставка элемента, причем элемент конструируется на месте, а в метод передаются аргументы соответствующего конструктора. Позволяет избежать ненужных перемещений/копирований.
- reverse - разворот списка. Первый элемент становится последним и т.д. Сложность O(N)
- merge - слияние двух отсортированных списков, второй список остается пустым. Сложность O(N + M)
- splice - перенос элементов из одного списка в другой, второй список остается пустым. При переносе операции производятся лишь над указателями, поэтому не проиходит ни копирования, ни перемещения.
И так далее. Так же имеет базовые методы типа swap, size, clear и resize, присущие многим контейнерам STL.
Реализация удаления элемента (единственный элемент): Функции необходимо очистить память удаленного элемента, обрабатывать случай, когда передавамый итератор является end(), а так же возвращать итератор на следующий за удаленным элемент.
template <typename T>
iterator list<T>::erase(iterator elem) {
if (elem == end()) return elem; // Check if dereferenceble
if (elem->prev) elem->prev->next = elem->next; // Check if prev element exists
else first = elem->next; // otherwise change list first elem
if (elem->next) elem->next->prev = elem->prev; // Check if next element exists
else last = elem->prev; // otherwise change list last elem
auto old = elem++; // Increment elem and save old iterator to delete its pointer later
delete old.base();
return elem;
}Класс std::map. Внутренняя реализация map, его основные методы. Сложность поиска, сортировки, удаления элемента, добавления элемента. Пример работы с std::map
std::map - отображение. Ставит значение в соответствие ключу. Ключи уникальны и на их основе сортируются элементы при добавлении. Реализовано посредством красно-черного дерева. Благодаря такому устройству элементы постоянно балансируются (ветви лежащего внутри дерева приобретают одинаковую глубину) и сложность большинства операций поддерживается на уровне O(log N).
Оценки сложности (N - размер контейнера/количество элементов):
- Вставка/удаление - O(log N)
- Поиск элемента по ключу - O(log N)
- Сортировка - так как отображение является сортированным ассоциативным контейнером, то я не совсем понимаю что подразумевается под сложностью сортировки. Раз уж элементы сортируются при добавлении, то пусть будет O(log N)
Основные методы:
- at, operator[] - доступ по ключу c проверкой и без.
- insert - вставка элемента/элементов. В последнем случае сложность O(N * log N + N)
- emplace - вставка элемента, причем элемент конструируется на месте, а в метод передаются аргументы соответствующего конструктора. Позволяет избежать ненужных перемещений/копирований.
- erase - удаление элемента/элементов.
- find - поиск элемента в контейнере. Возвращает итератор
- upper_bound, lower_bound, equal_range - поиск первого элемента, ключ которого больше/меньше чем указанный. equal_range делает то же самое, но одновременно, возвращая пару соответствующих итераторов.
И так далее. Так же имеет базовые методы типа swap, size и clear, присущие многим контейнерам STL.
Класс std::set. Внутренняя реализация set, его основные методы. Сложность поиска, сортировки, удаления элемента, добавления элемента. Пример работы с std::set
std::set - множество. Элементы уникальны, а так же сравниваются и сортируются при добавлении. Реализовано посредством красно-черного дерева. Благодаря такому устройству элементы постоянно балансируются (ветви лежащего внутри дерева приобретают одинаковую глубину) и сложность большинства операций поддерживается на уровне O(log N).
Оценки сложности (N - размер контейнера/количество элементов):
- Вставка/удаление - O(log N)
- Поиск элемента по ключу - O(log N)
- Сортировка - так как множество является сортированным ассоциативным контейнером, то я не совсем понимаю что подразумевается под сложностью сортировки. Раз уж элементы сортируются при добавлении, то пусть будет O(log N)
Основные методы:
- insert - вставка элемента/элементов. В последнем случае сложность O(M * log(N + M)), где M - количество элементов для вставки.
- emplace - вставка элемента, причем элемент конструируется на месте, а в метод передаются аргументы соответствующего конструктора. Позволяет избежать ненужных перемещений/копирований.
- erase - удаление элемента/элементов.
- find - поиск элемента в контейнере. Возвращает итератор
- upper_bound, lower_bound, equal_range - поиск первого элемента, ключ которого больше/меньше чем указанный. equal_range делает то же самое, но одновременно, возвращая пару соответствующих итераторов.
И так далее. Так же имеет базовые методы типа swap, size и clear, присущие многим контейнерам STL.
Класс std::unordered_map. Внутренняя реализация unordered_map, его основные методы. Сложность поиска, сортировки, удаления элемента, добавления элемента. Пример работы с std::unordered_map
std::unordered_map - неупоряжоченное отображение. Ставит элемент в соответствие ключу. Элементы не располагаются в каком-либо определенном порядке, лишь распределяются по подмассивам (buckets/chunks) в зависимости от вычесленного для ключа хэша. Реализовано посредством хэш-таблицы. Такое устройство позволяет предоставить в среднем O(1) доступ по ключу.
Оценки сложности (N - размер контейнера/количество элементов):
- Вставка/удаление - в среднем O(1), в худшем O(N)
- Поиск элемента по ключу - в среднем O(1), в худшем O(N)
- Сортировка - элементы контейнера располагаются в зависимости от хэшей соответсвующих им ключей. Контейнер можно естественным способом отсортировать, например, вставкой всех его элементов в std::map (O(N * log N)), или просто сохранить их в список/массив и затем отсортировать понравивишимся алгоритмом/std::sort, но сам контейнер такой возможности не предоставляет.
Основные методы: Контейнер имеет множество методов std::map (за исключением методов для работы с сортированными контейнерами - lower_bound, upper_bound), а так же методы для работы с хэшами и подмассивами.
- insert - вставка элемента/элементов. В последнем случае сложность O(M) в лучшем и O(M * N + M) в худшем случае, где M - количество элементов для вставки.
- emplace - вставка элемента, причем элемент конструируется на месте, а в метод передаются аргументы соответствующего конструктора. Позволяет избежать ненужных перемещений/копирований.
- erase - удаление элемента/элементов.
- find - поиск элемента в контейнере. Возвращает итератор
И так далее. Так же имеет базовые методы типа swap, size и clear, присущие многим контейнерам STL.
Класс std::vector. Внутренняя реализация vector, его основные методы. Сложность поиска, сортировки, удаления элемента, добавления элемента. Пример работы с std::vector. Особенность std::vector.
std::vector - динамический массив. Для хранения элементов используется последовательный участок памяти. Реализован таким образом, чтобы предоставлять амортизированную сложность O(1) для вставки в конец массива - при выделении памяти запрашивается чуть (как правило до 1.5 * N) больше памяти чем необходимо, дабы не приходилось выделять память и перемещать элементы при каждой новой вставке.
Оценки сложности (где N - размер массива)
- Поиск - O(N)
- Доступ по индексу - O(1)
- Сортировка - O(N * log N), в зависимости от выбранного алгоритма сортировки.
- Вставка/удаление элемента на произвольной позиции - O(N)
- Добавление/удаление элемента в конеце - амортизированная O(1)
Основные методы:
- push_back, insert - вставка в конец/произвольное место.
- emplace_back, emplace - вставка в конец/произвольное место с конструированием на месте.
- pop_back, erase - удаление последнего/произвольного элемента.
- front, back, operator[], at - доступ к первому/последнему/произовольному элементу (по индексу, с проверкой и без)
- size - размер массива
Основные методы для работы с резервированием памяти:
- reserve - резервирует память для указанного количества элементов.
- capacity - возвращает количество элементов, на которые хватит зарезервированной памяти.
И так далее. Так же имеет базовые методы типа swap, size, clear и resize, присущие многим контейнерам STL.
std::vector - специализация std::vector, более эффективно использующая память путем храненения булевых значений в каждом бите (в отличие от одного значения в байте, как для переменных типа bool). Так же предоставляет особый метод - flip, для инвертирования всех значений массива. Согласно cppreference std::vector накладывает некоторые издержки. К примеру, вектор может не удовлетворять всем тербованиям stl-контейнеров, а к его итераторам нет жестких требований, что может вести к неопределенному поведению.
Объекто ориентированное пограммирование подразумевает создание объектов, содержащих данные в форме полей, а так же предоставляющих методы для управления этими данными. Парадигмы ООП: полиморфизм, наследование и инкапсуляция.
Инкапсуляция - сокрытие информации, которое гарантирует что данные объекта и его методы используются по назначению. Использование инкапсуляции позволяет в дальнейшем изменять устройство классов без вреда для пользователя, при условии что открытый интерфейс объекта остается неизменным. С++ предоставляет 3 типа доступа - public, protected и private.
Наследование - базирование одного типа данных (объекта или класса) на другом типе данных, способствующее повторному использованию уже существующего кода. Помимо повторного использования кода через наследование реализуются очевидные связи между классами, что способствует чистоте кода. С++ предлагает несколько типов наследования - public, protected, private и даже виртуальное наследование (Для разрешения проблем ромбовидного наследования), каждое из которых реализует определенное отношение между классами. К примеру public наследование реализует отношение "является".
Полиморфизм - различное поведение объекта в зависимости от обстоятельств. С++ допускае два типа полиморфизма. Статический (времени компиляции) и динамический (времени исполнения)
Статическийп полиморфизм представлен перегрузкой функций, аргументами по умолчанию и шаблонами. Таким образом функция ведет себя по разному в зависимости от параметров или типа, над которыми она работает.
Динамический полиморфизм представлен наследованием и виртуальными функциями. Во время выполнения определяется какой метод необходимо использовать для соответствующего объекта в иерархии.
Шаблоны - средство C++, предназначенное для разработки обобщённых алгоритмов, без привязки к некоторым параметрам (например, типам данных). Инстанцирование - генерация кода функции или, напрмер, класса, дял конкретных параметров. Спецификация шаблонов (или, скорее, специализация) - ручное указание реализации сущности для каких-либо конкретных параметров. Может быть полной или частичной.
// Сама шаблонная функция. На ее месте может быть и класс
template <typename T1, typename T2>
void foo() {}
// Полная специализация
template <>
void foo<int, int>() {}
// Частичная специализация
template <typename T>
void foo<int, T>() {}Таким образом можно реализовать функцию по-особому для <int, int> или всех функций типа <int, T>.
Итераторы: определение, назначение, преимущества. Итераторы прямого доступа, итераторы ввода, итераторы вывода, двунаправленные итераторы, прямой итератор. Примеры.
Итератор - интерфейс, предоставлюящий доступ к элементам контейнера и средства для навигации по ним. Итераторы используются многими функциями стандартоной библиотеки и являются своеобразным общим интерфейсом для них. Преимущества итераторов перед сырыми указателями (оберткой коих итераторы как правило и являются) - удобство и безопасность. Итераторы инкапсулируют логику, необходимую для навигации по контейнеру, что необходимо, если контейнер не является тривиальным (например массивом или списком).
Каждый новый тип итератора базируется на предыдущем и предоставляет новые функции.
Итераторы ввода - итераторы, допускающие чтение и единичный проход в одном направлении. (++/--, * (единичное))
Итераторы вывода - итераторы, допускающие запись и единичный проход в одном направлении. (++/--, =)
Итераторы прямого доступа - итератор, дополнительно к свойствам предыдущих двух, допускающий множественный проход в одном направлении. (++/--, * , =, !=)
Двунаправленные итераторы - итератор, допускающий проход в обоих направлениях. (++, --, * , =, !=)
Итератор произвольного доступа - итератор, допускающий произвольный доступ (арифметика указателей, доступная указателям в массивах). (++, +, --, -, * , <=>)
Для получения итераторов контейнеры в C++ обладают методами begin() и end(). begin() возвращает итератор, который указывает на первый элемент контейнера (при наличии в контейнере элементов). Функция end() возвращает итератор, который указывает на следующую позицию после последнего элемента. Если контейнер пуст, то итераторы, возвращаемые обоими методами совпадают, иначе в контейнере есть как минимум один элемент.
auto- автоматическое выведение типа переменной. Такое выведение используется при инициализации, причем по умолчанию auto отбрасывает cv-квалификаторы и ссылки.auto&- ссылочное выведение типа переменной. В таком случае cv-квалификаторы уже не отбрасываются. При использовании этого варианта для rvalue ссылки произойдет ошибка времени компиляции.auto&&- универсальное ссылочное выведение типа переменной. То есть, в случае вивдениея из rvalue, переменная получит тип T&&, в противном - T&. cv-квалификаторы так же сохрянаются.
auto нельзя использовать при указании типов аргументов в определениях функций, но при этом, можно использовать в определениях лямбда-выражений.
decltype- автоматическое выведение типа выражения/переменной. Причем выражение для этого не вычисляется. (Имеется в виду основное выражение. Дляdecltype(f(g())), g() вычислить придется)decltype(auto)- прямое выведение типа для переменной, если нас не устраивает то, что обычный auto отбрасывает сcылки и квалификаторы.
Более читаемый эквивалент стандартного for-цикла. Выглядит как:
for (cv type name : container) {
...
}Аналогичен проходу по контейнеру с помощью итераторов. Если необходимо, переменная name, последовательно принимающая все значения из соответствующего контейнера, может объявляться с использованием cv-квалификаторов или по ссылке.
Специальное ключевое слово, обозначающее нулевой указатель, имеет тип std::nullptr_t.
Квалификатор, который указывает на то, что выражение будет рассчитано на этапе компиляции. Может быть примено к переменным и функциям. constexpr-функция так же будет рассчитана на этапе компиляции, если ее аргументы известны на этапе компиляции. constexpr-переменная, внезапно, явялется константой. При этом сonstexpr не является cv-квалификатором. При объявлении функции аргументы нельзя объявлять constexpr, то есть не получится сделать функцию работающую только на этапе компиляции. Так же на constexpr функции и переменные накалыдваются некоторые ограничения. Переменная должна быть литерального типа, функции не должны быть вирутальными и содержать только определенные ключевые слова, а классы должны иметь тривиальные конструкторы/деструкторы и так далее.
Перечисление с областью видимости. Задается как:
enum class/struct name {enumerators};Условие на стадии компиляции. То есть, компилироваться будет только блок, подходящий по условию.
Проверка условия на стадии компиляции. Если условие не выполняется - вобуждается ошибка компиляции. Первым аргументом указывается условие, а вторым можно указать сообщение, которое будет показано, если условие не выполнится.
std::initializer_list - легковестный контейнер, содержащий элементы типа const T. В самом объекте содержится лишь указатель на начало массива и его длина (const T[N]). Используется для инициализации объектов, и в функциях принимающих initializer_list.
Насколько я понимаю, из Си пришел синтаксис инициализации переменных, массивов и структур, но он не был доступен для пользовательских классов. С появлением функций с переменным числом аргументов проблема не решилась и было решено придумать initializer_list, который конструируется с помощью сишного синтаксиса и при наличии в пользовательском классе соответствующего конструктора, передается в нужный объект, создавая подобие сишной инициализации.
Явное указание компилятору сгенерировать специальный метод (конструктор/деструктор/оператор копирования и пр.) класса по умолчанию.
Указание что определенный метод класса нельзя переопредять в классах-наследниках или указание, что от класса нельзя наследовать.
class A {
...
public:
void foo() final;
}
class B final {
...
}Явное указание что функция наследника переопредяет вирутальную функцию предка.
Указание псевдонима для типа.
using alias = type;Аналогичным является ключевое слово typedef, но оно не работает с шаблонами. То есть с помощью using можно указать пмевдоним для семейства типов.
template <typename L, typename R> using Position = std::pair<L, R>;
...
Position<int, int> pos{0, 0};std::optional - шаблонный класс, реализует обертку над объектом и содержит информацию о том, содержит ли она сейчас объект или нет. Таким образом, std::optional можно использовать там, где наличие объекта не гарантируется. Обычно, отсуствие объекта обозначалось каким-либо специальным значением (-1, nullptr и т.д) или пустым (инициализированным по умолчнию) объектом, но это не всегда возможно. К тому же плохо читаемо, с чем и справляется std::optional. Более того, создание пустого объекта может быть накладно, а optional этого не делает, лишь хранит флаг. Нормальной практикой использования std::optional являются функции, конструирующие объекты. Если создание объекта по каким-либо причинам не происходит, то возвращается пустой объект std::optional. Для удобства std::optional неявно приводится к bool.
std::variant - типо-безопасное объединение. В опеределенный момент времени объект std::variant либо содержит объект одного из указанных типов, либо не содержит объекта вообще (в случае ошибки). Пустые std::variant так же являются плохой практикой, согласно cppreference.
Так же std::variant может содержать типы более одного раза или типы с различными cv-квалификаторами. То есть
std::variant<int, const int, int> obj - легальный объект. Так же он не может содержать ссылки, массивы или тип void.
Для доступа к вложенному объекту используются функции std::get, std::get_if, а для проверки .index(), .holds_variant() и пр.
std::any - типо-безопасный контейнер, который может содержать единственное значение произвольного типа. Доступ к лежащему внутри объекту производится с помощью std::any_cast и в случае обращения по неправильному типу прокидывается исключение std::bad_cast.
std::string_view - легковесный класс, содержащий указатель на массив символов и его размер. При этом объект самими данными не владеет. Таким образом, некоторые операции, например нахождение подстроки, происходят с помощью смещений указателя на начало и размера массива, то есть, без работы с памятью и копирования. В общем и целом - позволяет быстро и эффективно работать со строками.
Лямбда-функции, функторы, указатели на функции, std::functional. Примеры использования std::functional. Примеры использования лямбда-функций.
Лямбда-функция - локальный анонимный функтор. Функтор, в свою очередь, - объект, для которого определен оператор вызова - соответствующий объект или указатель на функцию.
Под лямбда-выражением для с++ подразумевается краткая форма записи такого функтора:
cpp [vars](args){ body; }
Указывая в квадратных скобках переменные можно передыть их в лямбда функцию. Есть несколько режимов передачи - по значению и по ссылке. Переданные по значению переменные в ламбде изменить будет нельзя, но это исправляется указанием улючевого слова mutable за скобкой после аргументов. Переданные по ссылке значения изменяются свободно. Таким образом, в лямбду нельзя передать константную ссылку на какой-либо локальный объект.
При указании [&] все локальные переменные передаются в лямбду по ссылке, при [=] - по значению. При этом можно будет дополнительно указать переменные, которые будут передаваться иным способом.
[] // no capture
[=] // value
[&] // reference
[a, &b] // a - value, b - reference
[=, &a] // all - value, a - referenceпри использовании лямбды в методе класса, можно передавать [this] чтобы использовать методы уже внутри лямбды. Так же для лямбд разрешено ключевое слово auto при указании типа. В таком случае необходимо дополнительно записать хвостовое выведение типа (его же можно указывать если возвращаемый тип нужно указать в явном виде). Так же лямбда-функция может быть указана как noexcept. Это ключевое слово пишется после mutable, если он присутствует и вместо если нет.
Указатель на функцию хранит адрес функции. По сути указатель на функцию содержит адрес первого байта в памяти, по которому располагается выполняемый код функции. Указатель на функцию - ее имя. Тип такого указателя
type (*)(args), где type - возвращаемый тип, а args - аргументы принимаемые функцией.
functional - библиотека функциональных объектов. Содержит std::function в частности - обертку для любых функциональных объектов. Так же содержит std::bind - обертку, которая позволяет заранее подставить аргументы на определенные позиции при вызове функционального объекта, тем самым создавая новый.
R-value ссылки - ссылки на right hand sentence expression - выражение по правую сторону знака равно. Как правило - ссылки на временные объекты. Принимают любые cv-квалификаторы, а так же записываются как T&&.
В новом стандарте все ссылки делятся на три категории glvalue, xvalue, prvalue. И обозначают cоотвественно чистые левосторонние значения, временные значения и чистые правосторонние значения. rvalue, получается, перешли в xvalue и prvalue.
Семантика перемещения - концепция переноса данных без их копирования, там где это необходимо. Позволяет ускорить выполнение программы и сократить использование памяти. Например, при необходимости переместить массив в новое место раньше приходилось копировать его целиком. То есть искать такой же последовательный блок памяти и копировать в него значения, вместо того чтобы просто передать данные массива в новое место. Реализуется с помощью конструкторов перемещения и operator= с перемещением.
std::move - шаблонная обертка для static_cast<T&&>, которая принимает любые неконстантные ссылки, снимает их и затем приводит к T&& - rvalue ссылке. При этом в сигантуре функции фигурирует T&& - универсальная ссылка (WUT. Мы ввели тебе rvalue ссылку как T&&, чтобы она не выглядела как T& (а то не понятно, да), но после этого ввели универсальную ссылку которая выглядит как rvalue ссылка, но может принимать как lvalue, так и rvalue. ???).
std::forward - подобная move шаблонная функция, которая вместо приведения полученных значений к rvalue передает их в таком виде в каком приняла.
RVO - return value optimization. Компиляторозависимая штука, которая позволяет избегать копирования объектов при их возврате из функции.
Обработка ошибок с использованием механизма обработки исключений. RAII. Примеры классов, использующих RAII. Ключевое слово noexcept.
С++ предоставляет определенные средства для обработки исключений - ключевые слова try и catch. В try-блок помещается код потенциально выбрасывающий исключения. В catch блоке обрабаются исключения указанного типа, либо все исключения (при указании ... в аргументах catch. Работает в духе if else, то есть, указывая (...) в начале обработки, этот случай будет вызваться всегда и обработка никогда не пройдет дальше него.
try {
// потенциально опасный код
}
catch (ex& e) {
// обработка исключения типа ex
// удаление выделенной памяти (к примеру)
}
...
catch (...) { // Ловим исключения не обработанные сверху
}Если исключение выходит из main-функции, то вызывается std::terminate, которая роняет программу. Но ее поведение может быть переопределено пользователем с помощью специальных методов. Поскольку в С++ нет final, идеома RAII - единсвтенный адекватный способ зачистки памяти в случе исключений. RAII - resource aquasition is initialization. То есть, концепция владения объектом ресурсов. Он получает их в конструкторе и освобождает в деструкторе. Классические примеры - умные указатели. Тесно связана с семантикой переноса.
noexcept - ключевое слово, показывающее, что функция не выдает исключений. Впрочем, компилятор и сам в большинстве случаев определяет где исключения не кидаются.
RAII в предыдущем вопросе. std::shared_ptr - RAII обертка, владеющая указателем на данные. При этом, таких объектов, содержащих указатель на одни и те же данные, может быть несколько. Память, ассоциированная с вложенным указателем очищается лишь в случае отсутсвтия shared_ptr, указывающих на него. Внутри работает через подсчет ссылок - ведется учет количества shared_pointer'ов, указывающих на один и тот же объект. При этом счетчик атомарный, то есть, shared_ptr можно безопасно использовать в условиях многопоточных программ. Так же учитываются слабые ссылки - weak_ptr. Объект копируемый, т.е имеет оператор копирования. Так же имеет стандартные для указателя возможности - разыменование и обращение в частности, а так же reset и пр. Создаются такие указатели с помощью make_shared или allocate_shared
RAII в предыдущем вопросе. std::unique_ptr - RAII обертка, владеющая указателм на данные. Причем, указывать на одни и те же данные может лишь один std::unique_ptr, т.е данный тип не копируемый. Зато он перемещаемый. Имеет функции для работы с указателем, создается с помощью make_unique и allocate_unique.
RAII в предыдущем вопросе. std::weak_ptr - RAII обертка, не владеющая указателем на данные. Содержит "слабую" ссылку на объект, выделенный std::shared_ptr. Для доступа к вложенным данным должен быть сконвертирован в std::shared_ptr.Реализует врменное владение. Дотуп к объекту осуществляется лишь в том случае, если объект еще существует. Призван решать проблему перекрестных ссылок - случая, когда shared_ptr указывают друг на друга
Управление потоками. Состояния гонок в интерфейсе структур данных. Класс std::future, функция std::async
Состояния гонок в интерфейсе стурктур данных - гонки, возникающие при обращении к объекту, в ходе которых нарушаются его инварианты. Инвариант - некое условие, выполнение которого необходимо для правильной работы струтктуры. К примеру поле size класса vector хранит количество элементов в массиве. Если это не так (допустим, произошла ошибка доступа к соотвествующему объекту и поле было изменено некорректно), то инвариант нарушен. Помимо этого Вильямс упоминает, что методы доступа и получения информации о структурах нельзя считать валидными, поскольку данные, полученные с помощью этих методов, были правильными лишь в момент их получения. То есть, после их получения и перед использованием данные могут быть изменены другим потоком.
std::async - функция, позволяющая запустить выполнение операции в новом потоке. В отличие от std::thread, для std::async существует способ получения возвращаемого функцией значения. async возвращает объект std::future, потенциально содержащий результат выполнения операции (или исключение, в случае ошибки).
async имеет конструктор подобный std::thread, так же принимает функцию и ее аргументы. Дополнительно первым аргументом может быть указано правило запуска потока - std::launch::async или std::launch::deferred. В первом случае новый поток запустится асинхронно, во втором же случае новый поток создан не будет, а результат начнет вычисляться в текущем потоке по первому запросу. Если же указаны оба флага - поведение зависит от реализации, ни одного - аналогично.
std::future - обертка над реазультатом асинхронной операции. Такой объект возвращает std::async.
Присутствует метод get, позволяющий получить результат, но его вызов обязан быть однократным (в противном случае - неопределенное поведение). std::future имеет метод valid, позволяющий проверить был ли получен результат. Так же имеет фунции ожидания (wait, в частности), которые испольузуются методом get если результат еще не готов.
Переключение контекста потоков. Класс std::thread. Ключевое слово thread_local. Примеры использования thread_local. Примеры использования std::thread.
Переключение контекста потоков - для создания иллюзии параллельного выполнения задач, процессор постоянно переключается между ними. Переключение проиходит быстро, но не бесплатно - сохраняются необходимые данные, например, для обратного переключения, а посему выполение замедляется.
std::thread - объект, конструктор которого принимает функтор и аргументы, которые он принимает при вызове. Указанная функция начинает выполняться в новом потоке. Ради безопасности все аргументы, переданные в эту функцию, принимаются по значению. Таким образом, для передачи ссылки в поток, который создает std::thread, необходимо использовать обертки (например, std::ref). Стоит отметить, что в std::thread можно передавать лямда-функции, что не только очень удобно, но может оказаться и опасно. Например, при захвате всех локальных переменных по ссылке ([&]) и передаче в std::thread, ссылки остаются ссылками, и, соответственно, могут "обвиснуть" при уничтожении материнского потока.
Для корректной работы, до вызова деструктора std::thread необходимо вызвать либо метод join, либо метод detach. При вызове первого метода материнский поток дождется завершения дочернего. В противном случае дочерний поток будет отсоединен и перейдет во власть библиотеки времени выполнения C++. Такие потоки еще называют потоками-демонами.
thread_local - квалификатор, указываемый при создании переменной. Показывает, что переменная создается в памяти, ассоциированной потоком и, соответственно, если это переменная глобальна для инициализировавшего ее потока, имеет время жизни потока. Может быть скобирнировано со static, для ограничения времени жизни статической переменной.
Синхронизация потоков. Состояние гонок. Классы std::mutex, std::lock_guard, std::recursive_mutex, boost::shared_mutex, std::unique_lock. Функция std::lock. Примеры использования мьютексов.
Состояние гонок - состояние, при котором результат выполнения программы зависит от порядка доступа потоков к данным.
std::mutex - mutual exclusion. Примитив синхронизации, позволяющий обеспечить своеобразную "атомарность" в месте его применения. Может быть заблокирован (lock) и разблокирован (unlock). Поток, захвативший мьютекс, может "видеть" все, что происходит до разблокировки. Остальные потоки, пытающиеся захватить мьютекс, ждут, пока его не освободят. Мьютекс нельзя захватить или разблокировать несколько раз. Так же имеет функцию try_lock, используя которую, можно проверять занят ли сейчас мьютекс и захватывать его, если нет. В противном случае, например, можно делать полезную работу.
std::lock_guard - RAII обертка для мьютекса. Принимает мьютекс в своеобразное владение, при котором в своем конструкторе захватывает мьютекс (если не указано std::adopt_lock, при котором мьютекс принимается уже в захваченном виде), а в деструкторе мьютекс освобождает.
std::recursive_mutex - мьютекс, который можно захватить несколько раз. Для его освобождения метод unlock должен быть вызвать столько же раз, сколько и метод lock, в одном потоке. Как правило, использование рекурсивных мьютексов не приветствуется. Но, все же, они полезны при работе с рекурсивными функциями и пр.
boost::shared_mutex - мьютекс, реализующий монопольное владение для одного потока и разделяемое для остальных. Таким образом организуется поток-писатель и, например, потоки-читатели. Потоки читатели не изменяют данные и их жоступ к данным не синхронизируются, но они все прекращают работу, когда поток-писатель изменяет данные.
std::unique_lock - более функциональная обертка для мьютекса. Устроена подобным std::lock_guard образом, но реализует более гибкое управление вложенным мьютексом - его можно блокировать и разблокировать во время существования объекта. При этом внутри такого объекта хранится флаг, отражающий состояние вложенного мьютекса. Таким образом, в деструкторе этот флаг проверяется и, если мюьтекс уже освобожден, то объект просто уничтожается.
std::lock - функция, назначение которой - решить проблему взаимоблокировок, возникающих, когда два или более потоков при захвате нескольких мьютексов уже удерживают мьютексы друг друга. Принимает несколько мьютексов и освобождает их, если неско хотя бы один из них не удалось захватить. Таким образом, реализуется "все или ничего".
std::lock(m1, m2);
std::lock_guard<std::mutex> lm1(m1, std::adopt_lock);
std::lock_guard<std::mutex> lm2(m2, std::adopt_lock);std::condition_variable - условная переменная. Особый флаг, спотыкаясь об метод wait которого, поток засыпает (то есть, не тратится процессорное время, а так же отпускается соответствующий мьютекс), и просыпается при поступлении уведомления через методы notify_one и notify_all. При пробуждении мьютекс захватывается. Причем засыпающие потоки не организуют никакую очередь, уведомление приходит случайным потокам. Более того, потоки имеют тенденцию просыпаться сами (spurious wake), то есть, придется обзавестись каким-то условием, которое надо бы проверять при пробуждении и таким образом, нивелировать эффект ложных пробуждений. Существует версия wait, дополнительно к мьютексу принимающая предикат. Если предикат, при пробуждении, венет false, то поток отдаст мьютекс и снова уснет.
Потокобезопасные структуры данных с блокировками - структуры данных, доступ к которым организован с помощью блокировок. Как правило в таком случае структура теряет множество методов (таких как, size, front, top и прочее) для того чтобы избежать гонок в интерфейсе структур данных.
Синхронизация потоков. Пул потоков. Класс std::condition_variable. Примеры работы с std::condition_variable.
Пул потоков - некая сущность, распределяющая доступные ей потоки на приходящие в нее задачи.
Атомарные операции - неделимые операции. То есть, операции, промежуточные резальтаты выполнения которых, не пособен увидеть ни один поток. То есть, операции, которые не могут быть частично выполнеными или частично не выполнеными.
std::atomic - шаблонная обертка для типа, доступ к которому необходимо обеспечивать атомарно. Имеет специализации для bool, T* и для целочисленных типов. Методы load, store, exchange, compare_exchange_weak, compare_exchange_weak - доступны всем типам. Операции +=, -=, ++, -- доступны указателям и целочисленным типам. Побитовые операции с присваиванием - лишь целочисленным.
std::atomic_flag - единственная переменная, атомарность без блокировок которой, гарантируется стандартом. Очень прост, а посему очень ограничен. При инициализации переменной этого типа необходимо присваивать значение ATOMIC_FLAG_INIT, и доступны всего два метода - test_and_set и clear. Реализован лишь как крипичик, на основе которого предполагается делать типы без блокировок. Например, с помощью атомик флаг можно организовать простой спинлок.
Программам без блокировок также присущи некоторые проблемы. К примеру - временные блокировки. Опять же в случае, когда два потока ожидают друг друга. Но такие блокировки не вешают программы намертво. Как правило через какое-то время они разрешаются сами по себе, например, когда одному потоку удается 'проскочить'.
Классический пример работы с std::atomic - стек без блокировок.
Псевдо-реализация CAS - compare and swap.
bool compare_exchange(T& obj, T& expected, T value) {
bool result = (obj == expected);
if (result) {
obj = value;
} else {
expected = obj;
}
return result;
}Паттерн “простая фабрика” – это класс, в котором есть один метод с большим условным оператором, выбирающим создаваемый продукт. Этот метод вызывают с неким параметром, по которому определяется какой из продуктов нужно создать.
struct Barrack {
Unit* CreateUnit(UnitID unit_id) {
switch (unit_id) {
case UnitID::Knight:
return new Knight();
case UnitID::Archer:
return new Archer();
default:
return nullptr;
}
}
};Паттерн “фабричный метод” – это устройство классов, при котором подклассы могут переопределять тип создаваемого в суперклассе продукта. В таком случае органиуется несколько параллельных иерархий классов. В зависимости от того, метод какого подкласса был вызван, будет определяться объект какого подкласса из другой иерархии вернуть.
struct Barrack {
virtual Unit* CreateUnit() = 0;
void Hire(Player& player) {
auto* unit = CreateUnit();
player.AddToArmy(unit);
}
};
struct KnightBarrack : public Barrack {
Unit* CreateUnit() override {
return new Knight();
}
};
struct ArcherBarrack : public Barrack {
Unit* CreateUnit() override {
return new Archer();
}
};
ArcherBarrack archer_barrack;
archer_barrack.Hire(player);Наблюдатель – это поведенческий паттерн проектирования, который создаёт механизм подписки, позволяющий одним объектам следить и реагировать на события, происходящие в других объектах.
class Publisher {
std::vector<Observer*> observers;
public:
void method() {
// smth
notify();
// smth
}
void notify() {
for (const auto& obs : observers) {
obs->on_update();
}
}
void add_observer(const Observer& obs);
void remove_observer(const Observer& ons);
}
class Observer {
public:
void on_update();
}Асинхронное программирование имеет два основных преимущества - разделение обязанностей и параллельная обработка данных. Разделение обязанностей - способ проектирования, когда разделение на потоки сопустствует логическому разделению на обязанности сущностей в программе. Асинхронное выполнение так же позволяет произодить одну и ту же операцию над несколькими данными одновременно, то есть, уменьшение времени работы достигается путь обработки большего количества данных за то же время, нежели засчет увеличения скорости исполнения. К отрицательным сторонам относят общую сложность реализации (ведь в таком случае необходимо особое проектирвоание), сложность поиска неисправностей, плохую читаемость и прочее. Порой даже самые типичные проблемы требуют невероятно сложных решений.
В асинхронной модели программирования поток может приостановить выполнение задачи, сохранив текущее состояние, и начать выполнение другой задачи.
Сопрограмми называются функции, имеющие несколько точек входа, в то время как, у обычных функций есть только одна. Использование сопрограмм позволяет писать асинхронный код, который выглядит как синхронный. Такой код проще реализовывать, отлаживать и использовать.
Спорограммы (Корутины) - это потоки исполнения кода, которые организуются поверх аппаратных (системных) потоков.
Поток исполнения кода - это последовательность операций, которые выполняются друг за другом. В нужные моменты эта последовательность может быть приостановлена, и вместо нее может начать выполняться часть другой последовательности операций.
Основной вариант: функции обратного вызова (callback) – функции, которые будут вызываны после того, как завершится задача, запущенная в асинхронном режиме.
Функции обратного вызова (Коллбэки) - функции, передающиеся в другие функции для изменения их поведения.
Шаблон проектирования, подразумевающий, что какой-либо класс всегда представлен единственным объектом.
Для данной реализации характерно создание объекта при первом вызове функции get_instance.
Общение с объектом такого класса реализуется посредством вызова этого же метода.
class Singleton {
public:
static Singleton& get_instance() {
static Singleton instance;
return instance;
}
Singleton(const& Singleton) = delete;
void operator=(const& Singleton) = delete;
private:
Singleton() {}
};Чуть более фундаментальный вариант, позволяющий "осинглтонить" любой класс.
template <typename T>
class Singleton<T> {
public:
static T& get_instance() {
static T instance;
return instance;
}
Singleton() = delete;
Singleton(const& Singleton) = delete;
void operator=(const& Singleton) = delete;
};Или еще проще:
template <typename T>
T& get_instance() {
static T instance;
return instance;
}Такой вариант пусть и удобнее, но, как и предыдущий, логически не совсем верен. Singleton имеет множество недостатков и в принципе, с учетом нынешних традиций в среде разработчиков c++, не используется. Во многом благодаря тому, что любой синглтон - глобальный объект, а значит, делает связи между сущностями в программе куда менее явными. Также, время жизни такого объекта - время жизни статического объекта, то есть все время с первого его использования, до окончания программы. Хотя на его глобальности можно уже можно было остановиться.
Структуры данных без блокировок уже были описаны в вопросе про std::atomic
lock-free stack. Данная реализация работает лишь с учетом атомарности std::shared_ptr без блокировок (то есть почти никогда). Проблема протухания ссылок в данном случае решается через оборачивание всех нод в шаред поинтеры.
template <typename T>
class lock_free_stack {
private:
struct node {
std::shared_ptr<T> data_;
std::shared_ptr<node> next_;
node (const& T data) : data_(std::make_shared<T>(data)) {}
};
std::shared_ptr<node> head_;
public:
void push(const T& data) {
std::shared_ptr<node> new_node = std::male_shared<node>(data);
new_node->next = head_.load();
while (!std::atomic_compare_exchange_weak(&head_, &new_node->next, new_node));
}
std::shared_ptr<T> pop() {
std::shared_ptr<node> old_head = std::atomic_load(&head);
while (old_head && !std::atomic_compare_exchange_weak(&head_, &old_head, old_head->next));
return old_head ? old_head->data : std::shared_ptr<T>();
}
};Взаимодействие в сети рассматривается на основе понятия сокетов, которые позволяют приложениям рассматривать сетевые подключения как файлы, и программа может читать из сокета или писать в сокет, как она делает это с файлом. Существуют два механизма, предназначенных для сетевого взаимодействия программ, - это сокеты датаграмм, которые используют пользовательский датаграммный протокол (User Datagram Protocol) (UDP) без установления соединения, и сокеты, использующие Протокол управления передачей / Межсетевой протокол (Transmission Control Protocol/Internet Protocol) (TCP/IP), устанавливающий соединение.
Boost.Asio - кросс-платформенная С++ библиотека для программирования сетевых приложений и других низкоуровневых программ ввода/вывода. Boost.Asio успешно абстрагирует понятия input и output, которые работают не только для работы в сети, но и для последовательных COM-портов, файлов и так далее. Кроме этого вы можете делать input или output программирование синхронным или асинхронным.
Программа должна иметь экземпляр io_service. Boost.Asio использует io_service для общения с сервисом ввода/вывода операционной системы. Обычно одного экземпляра io_service бывает достаточно. Далее необходимо создать адрес и порт к которому нужно подключиться, затем создать сокет и поключить его к адресу и порту.
using boost::asio;
io_service service;
ip::tcp::endpoint ep( ip::address::from_string("127.0.0.1"), 2001);
ip::tcp::socket sock(service);
sock.connect(ep);Затем создаем акцептор (приемник) — один объект, который принимает клиентские подключения.создаем поток, обрабатывающий связь. В потоке, в функции client_session слушаем запросы клиента, интерпретируем их и отвечаем.
typedef boost::shared_ptr<ip::tcp::socket> socket_ptr;
io_service service;
ip::tcp::endpoint ep( ip::tcp::v4(), 2001)); // listen on 2001
ip::tcp::acceptor acc(service, ep);
while (true) {
socket_ptr sock(new ip::tcp::socket(service));
acc.accept(*sock);
boost::thread(boost::bind(client_session, sock));
}
void client_session(socket_ptr sock) {
while ( true) {
char data[512];
size_t len = sock->read_some(buffer(data));
if (len > 0) write(*sock, buffer("ok", 2));
}
}Вуаля, синхронный сервер. Для асинхронного треш.
Сетевое взаимодействие описано в предыдущем вопросе. Для работы с сетью традиционно используются сокеты. Сокет – это абстракция, которая позволяет работать с сетевыми ресурсами, как с файлами. Мы можем писать и читать данные из сокета почти так же, как из обычного файла. Функции для работы с сокетами:
- socket - новый сокет с заданными параметрами
- bind - связывание сокета с конкретным адресом сетевого интерфейса
- listen - перевод сокета в пассивный режим. Принимает размер очереди запроса, по заполнению очереди запросы игнорируются
- accept - ожидает клиентские соединения. В случае успеха создается новый сокет. Является блокирующей.
- connect - соединят пользовательский сокет с удаленным сокетом. Эта функция используется на клиентской стороне подключения, т.к. именно клиент является инициатором подключения.
- recv, recvfrom, recvmsg - получение сообщения от сокета.
- send, sendto, sendmsg - отправка сообщения сокету.
- close - закрытие сокета. Очищает ассоциированные с ним ресурсы?