2. Контейнеры. Умные указатели. Аллокаторы.

Sergei Fomin
Flashcards by Sergei Fomin, updated more than 1 year ago
Sergei Fomin
Created by Sergei Fomin over 5 years ago
23
0

Description

Карточки по второй лекции курса "Многопоточное программирование на C/C++" на stepic.org

Resource summary

Question Answer
Контейнеры-массивы std::vector - динамический массив std::array - статический массив
Контейнеры-списки std::list - двусвязный список std::forward_list - односвязный список (С++11) std::deque - смесь списка и массива
Упорядоченные ассоциативные контейнеры Реализуются красно-чёрными деревьями. std::set - упорядоченное множество std::multiset - упорядоченное множество с поддержкой дублирующихся значений std::map - неупорядоченное множество пар "ключ-значение" std::multimap - как map, но каждый ключ поддерживает множество значений
Неупорядоченные ассоциативные контейнеры Появились в С++11. Реализуются хеш-таблицами с разрешением коллизий методом цепочек (sequencing). std::unordered_set std::unordered_multiset std::unordered_map std::unordered_multimap
Типы итераторов Простые, константные, обратные, обратные константные.
2-3 дерево Дерево, поддерживающее 2 типа вершин: 2-вершины - вершины с одним значением и двумя потомками; 3-вершины - вершины с двумя значениями и тремя потомками; Растут вверх, поэтому всегда сбалансированы.
Красно-чёрное дерево По сути это 2-3 дерево, но вместо 3-вершин в нём 2-вершины с ребром между ними, которое окрашено в красный цвет. Но обычно красят вершины по цвету входящего в него ребра.
Способы разрешения коллизий в хеш-таблицах Sequencing (цепочки) - поддержка списков объектов с одинаковым значением хеш-функции Открытая адресация - несколько хеш-функций. Частный случай - Linear Probing - h(i) = h(i-1)+1
Кольцевой буфер Буфер, при переполнении перезаписывающий своё начало. boost::circular_buffer boost::circular_buffer_optimized - память не выделяется без необходимости Не имеет аналогов в STL.
Умные указатели Указатели, реализующие какую-либо дополнительную функциональность. Могут использоваться для: защиты от nullptr, подсчёта ссылок и многого другого.
Умные указатели в C++11 std::unique_ptr - владеющий указатель, может только передавать объект, но не "делиться" им; std::shared_ptr - указатель с подсчётом ссылок; std::weak_ptr - указатель, не учитывающийся при подсчёте ссылок. Имеет функцию lock()
Аллокаторы Задача аллокатора - выделение и освобождение памяти и, возможно, борьба с фрагментацией. Аллокатор можно указать для любого контейнера STL.
Примеры аллокаторов dmalloc - отладочный аллокатор, с его помощью можно ловить утечки памяти; tmalloc - аллокатор от Google, в среднем быстрее; jemalloc - аллокатор из FreeBSD
Способы уплотнения памяти Алгоритм Бейкера - две области памяти, при фрагментации уплотняем блоки из одной в другую. Уплотнение на месте - просто перетаскиваем всё вверх.
Show full summary Hide full summary

Similar

3. Сокеты Беркли. Мультиплексирование.
Sergei Fomin
FEH C/C++ Quiz
Jared Sherrick
Data Types
Jacob Sedore
Data Types
Santiago Castillo
Data Types
Santiago Castillo
The main reason knowledge is produced is to solve problems.
Darrel Hong
Mapa Conceptual - Arreglos
ciroivan94
French Future Tense Verbs
PEACEout
EQUIPAMIENTO COMUNAL Y PUBLICO (Areas Verdes)
Karla Salinas7200
Essbase Certification
Bob Costas