Karteikarten
2. Контейнеры. Умные указатели. Аллокаторы.
Karten in diesem Stapel (14)
- 1Контейнеры-массивыstd::vector - динамический массив
std::array - статический массив - 2Контейнеры-спискиstd::list - двусвязный список
std::forward_list - односвязный список (С++11)
std::deque - смесь списка и массива - 3Упорядоченные ассоциативные контейнерыРеализуются красно-чёрными деревьями.
std::set - упорядоченное множество
std::multiset - упорядоченное множество с поддержкой дублирующихся значений
std::map - неупорядоченное множество пар "ключ-значение"
std::multimap - как map, но каждый ключ поддерживает множество значений - 4Неупорядоченные ассоциативные контейнерыПоявились в С++11. Реализуются хеш-таблицами с разрешением коллизий методом цепочек (sequencing).
std::unordered_set
std::unordered_multiset
std::unordered_map
std::unordered_multimap - 5Типы итераторовПростые, константные, обратные, обратные константные.
- 62-3 деревоДерево, поддерживающее 2 типа вершин:
2-вершины - вершины с одним значением и двумя потомками;
3-вершины - вершины с двумя значениями и тремя потомками;
Растут вверх, поэтому всегда сбалансированы. - 7Красно-чёрное деревоПо сути это 2-3 дерево, но вместо 3-вершин в нём 2-вершины с ребром между ними, которое окрашено в красный цвет. Но обычно красят вершины по цвету входящего в него ребра.
- 8Способы разрешения коллизий в хеш-таблицахSequencing (цепочки) - поддержка списков объектов с одинаковым значением хеш-функции
Открытая адресация - несколько хеш-функций. Частный случай - Linear Probing - h(i) = h(i-1)+1 - 9Кольцевой буферБуфер, при переполнении перезаписывающий своё начало.
boost::circular_buffer
boost::circular_buffer_optimized - память не выделяется без необходимости
Не имеет аналогов в STL. - 10Умные указателиУказатели, реализующие какую-либо дополнительную функциональность. Могут использоваться для: защиты от nullptr, подсчёта ссылок и многого другого.
- 11Умные указатели в C++11std::unique_ptr - владеющий указатель, может только передавать объект, но не "делиться" им;
std::shared_ptr - указатель с подсчётом ссылок;
std::weak_ptr - указатель, не учитывающийся при подсчёте ссылок. Имеет функцию lock() - 12АллокаторыЗадача аллокатора - выделение и освобождение памяти и, возможно, борьба с фрагментацией.
Аллокатор можно указать для любого контейнера STL. - 13Примеры аллокаторовdmalloc - отладочный аллокатор, с его помощью можно ловить утечки памяти;
tmalloc - аллокатор от Google, в среднем быстрее;
jemalloc - аллокатор из FreeBSD - 14Способы уплотнения памятиАлгоритм Бейкера - две области памяти, при фрагментации уплотняем блоки из одной в другую.
Уплотнение на месте - просто перетаскиваем всё вверх.
Informationen
- Beschreibung
- Карточки по второй лекции курса "Многопоточное программирование на C/C++" на stepic.org
- Erstellt von
- Sergei Fomin
- Aufrufe
- 97
- Tags
- Bewertung