Заметки для лекции про стандартные контейнеры C++

gistfile1.txt

/***

https://en.cppreference.com/w/cpp/container

*/

/***

Задача стандартной библиотеки -- быть стандартной библиотекой.

Стандартная библиотека не должна быть самой быстрой в своем классе.
Или самой универсальной.
Или покрывать вообще все возможные случаи.

Первая задача стандартной библиотеки -- предоставлять общий словарь,
на который могут опираться разработчики разных компонент.

Вторая задача -- позволить собрать готовое приложение из тех частей, которые
идут "из коробки". И чтобы это не тормозило безбожно.

*/

/***

Стандартные контейнеры не thread-safe.

Вообще.

Одновременное чтение из контейнера из нескольких нитей -- OK.

Одновременное чтение и модификация или просто одновременная модификация
с нескольких нитей одновременно -- не OK.

*/

/***

Характеристики на которые нужно обращать внимание:

- эффективность тех или иных операций:
  1) вставка в начало,
  2) вставка в конец,
  3) доступ по индексу,
  4) вставка в произвольное место,
  5) удаление из произвольного места,
  6) удаление из начала;
  7) удаление с конца.

- инвалидация итераторов (и ссылок) при модификации;

- накладные расходы, связанные с контейнером

*/

/***

Последовательные контейнеры

*/

//
// std::array
//
// Это то, что в современном C++ хорошо было бы использовать вместо чисто-сишных
// массивов.
//
// Фиксированного размера. Не может уменьшаться или увеличиваться, поэтому многие
// из вышеупомянутых характеристик для него не актуальны.
// Минимальные накладные расходы.

//
// std::vector
//
// Последовательный блок памяти.
// Для эффективной работы нужно следить за его емкостью (capacity).
// Очень желательно использовать reserve.
//
// Метод clear(), в отличии от других контейнеров, не освобождает память.
// Есть метод shrink_to_fit.
//
// Эффективная вставка/удаление в конец, если достаточная емкость.
// Эффективный произвольный доступ.
// Итераторы могут инвалидироваться при модификации.
//
// Минимальные накладные расходы.
//
// Есть operator[] (не контролирует индексы), есть метод at (контролирует индексы).

//
// std::deque
//
// Возможно, серия блоков.
// Эффективная вставка/удаление в начало/конец.
//
// Эффективный доступ по индексу.
// Если вставка/удаление в начало/конец, то итераторы на уже существующие элементы
// не должны инвалидироваться.
//
// Могут быть дополнительные накладные расходы даже на пустом контейнере.
// 
// Есть operator[] (не контролирует индексы), есть метод at (контролирует индексы).

//
// std::list
//
// Как правило, простой двусвязный список.
//
// Эффективная вставка/удаление в любом месте, если у нас уже есть готовый итератор
// (для начала/конца это всегда так).
//
// Нет эффективного доступа по индексу.
//
// Не инвалидирует итераторы при модификации.
//
// Накладные расходы на каждый элемент (+2 указателя, если это двусвязный список).

//
// std::forward_list
//
// Как правило, односвязный список.
// Эффективная вставка/удаление в любом месте, если у нас уже есть готовый итератор.
//
// Двигаться можно только в одном направлении.
//
// Нет эффективного доступа по индексу.
//
// Не инвалидирует итераторы при модификации.
//
// Накладные расходы меньше, чем в случае std::list, но все-таки есть.

/***

Ассоциативные контейнеры

Хранят значения в упорядоченном виде.

*/

// Как правило, реализуются в виде сбалансированных деревьев. Соответственно,
// свойства практически у всех общие.
//
// Вставка/удаление O(log N).
//
// Нет прямого доступа, только через поиск.
//
// Не инвалидируют указатели при модификации.
//
// Есть накладные расходы на каждый элемент.
// В случае пустого контейнера накладные расходы могут быть, а могут и не быть,
// это зависит от реализации (но это не точно).

//
// std::set, std::multiset
//
// Не позволяют менять элемент после того, как он был помещен в контейнер.

//
// std::map, std::multimap
//
// После помещения в контейнер ключ поменять нельзя, а вот значение -- можно.

/***

Неупорядоченные ассоциативные контейнеры (хэш-таблицы)

*/

// Реализуются на базе хэш-таблиц, соответственно, общие свойства
// практически у всех общие.

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

// Могут быть накладные расходы даже на пустом контейнере.

// Нужно заморачиваться на хэш-функцию, особенно если у нас составной ключ.

// Имеет смысл обращать внимание на load_factor/rehash/reserve.

//
// std::unordered_set, std::unordered_multiset
//
// Аналогично std::set, std::multiset.

//
// std::unordered_map, std::unordered_multimap
//
// Аналогично std::map, std::multimap.

//
// Рекомендации по выбору между упорядоченными и неупорядоченными
// ассоциативными контейнерами.
// Главная: замеряйте!
// Если предполагается, что элементов будет много, что unordered.
// Если совсем мало, то ordered.
// Если составной ключ, то нужно проверять с замерами, т.к. неэффективная функция
// хэширования может убить преимущество хэш-таблицы за счет коллизий.
//

/***

Контейнеры-адаптеры

*/

// std::stack
// https://en.cppreference.com/w/cpp/container/stack
// По умолчанию базируется на std::deque.

// std::queue
// https://en.cppreference.com/w/cpp/container/queue
// По умолчанию базируется на std::deque.

// std::priority_queue
// https://en.cppreference.com/w/cpp/container/priority_queue
// По умолчанию базируется на std::vector.
// Реально эффективная штука.

/***

Задача для самообразования.

*/

// В чем разница между:

std::set<std::string>

// и

std::set<std::string, std::less<>>

/***

Еще одна задача для самообразования.

*/

// Как сделать std::set<std::string>, в котором сортировка шла бы в обратном порядке?