4274557
Description
Flashcards by Sergei Fomin, updated more than 1 year ago
|
Created by Sergei Fomin
over 8 years ago
|
|
| 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 |
| Способы уплотнения памяти | Алгоритм Бейкера - две области памяти, при фрагментации уплотняем блоки из одной в другую. Уплотнение на месте - просто перетаскиваем всё вверх. |
Want to create your own Flashcards for free with GoConqr? Learn more.