Какая структура данных находится внутри std::map в C++?

Question

Я новичок и изучаю C++. Мне трудно понять концепции std:: map, потому что код, с которым я играю, подразумевает, что map является деревом поиска, т.е. все имена объектов std:: map имеют * дерево в нем, а также комментарии.

Однако после прочтения этого материала http://www.cprogramming.com/tutorial/stl/stlmap.html я склонен думать, что std:: map не имеет ничего общего с деревом или хэшем.

Так что я запутался - либо переменные и комментарии в коде лгут мне, либо тема более сложная, чем я думаю:)

Answer 1

Шаг отладки в g++ 6.4 stdlibC++ source

Знаете ли вы, что по умолчанию в Ubuntu 16.04 g++-6 пакет или сборку GCC 6.4 из исходного кода, вы можете войти в библиотеку C++ без дальнейшей настройки?

Делая это, мы легко заключаем, что красно-черное дерево используется.

Это имеет смысл, так как std::map, В отличие от std::unordered_map, может быть пройден в ключевом порядке, что было бы неэффективно в случае использования хэш-карты.

a.cpp:

#include <cassert>
#include <map>

int main() {
    std::map<int, int> m;
    m.emplace(1, -1);
    m.emplace(2, -2);
    assert(m[1] == -1);
    assert(m[2] == -2);
}

Компилировать и отлаживать:

g++ -g -std=c++11 -O0 -o a.out ./a.cpp
gdb -ex 'start' -q --args a.out

Теперь, если вы вступите в s.emplace(1, -1) вы сразу достигнете /usr/include/c++/6/bits/stl_map.h:

556       template<typename... _Args>
557     std::pair<iterator, bool>
558     emplace(_Args&&... __args)
559     { return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }

который явно только вперед _M_t._M_emplace_unique,

Итак, мы открываем исходный файл в vim и найти определение _M_t:

    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
            key_compare, _Pair_alloc_type> _Rep_type;

    /// The actual tree structure.
    _Rep_type _M_t;

Так _M_t имеет тип _Rep_type а также _Rep_type это _Rb_tree,

Хорошо, теперь это достаточно доказательств для меня. Если вы не верите этому _Rb_tree черно-красное дерево, шагните немного дальше и прочитайте алгоритм

unordered_map использует хэш-таблицу

Та же процедура, но заменить map с unordered_map на коде.

Это имеет смысл, так как std::unordered_map не может быть пройден по порядку, поэтому стандартная библиотека выбрала хэш-карту вместо красно-черного дерева, так как хэш-карта имеет большую амортизированную сложность времени вставки.

Шагая в emplace приводит к /usr/include/c++/6/bits/unordered_map.h:

377       template<typename... _Args>
378     std::pair<iterator, bool>
379     emplace(_Args&&... __args)
380     { return _M_h.emplace(std::forward<_Args>(__args)...); }

Итак, мы открываем исходный файл в vim и искать определение _M_h:

      typedef __umap_hashtable<_Key, _Tp, _Hash, _Pred, _Alloc>  _Hashtable;
      _Hashtable _M_h;

Так что хэш-таблица это.

std::set а также std::unordered_set

Аналогично с std::map против std::unordered_map: Какова основная структура данных набора STL в C++?

Характеристики производительности

Вы также можете сделать вывод о структуре данных, используемой для их синхронизации.

поскольку std::map аналогично std::set мы ясно видим для:

• std::map, логарифмическое время вставки

• std::unordered_map, более сложный шаблон hashmap pattern:

  • на не масштабированном графике мы отчетливо видим удвоение динамического массива на огромном от линейно увеличивающихся пиков

  • на увеличенном графике мы видим, что времена в основном постоянны и идут к 250 нс, поэтому намного быстрее, чем std::map кроме очень маленьких размеров карты

    Несколько полос хорошо видны, и их наклон становится меньше, когда массив удваивается.

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

График создан с:

• код: https://github.com/cirosantilli/cpp-cheat/blob/15066739601a701d5f4d702ec28c6c615cdbb17b/cpp/interactive/bst_vs_heap.cpp
• Система: Ubuntu 18.04, GCC 7.3, процессор Intel i7-7820HQ, оперативная память DDR4 2400 МГц, Lenovo Thinkpad P51.

Анализ кучи против BST в: Кучи против дерева двоичного поиска (BST)

Answer 2

std::map это ассоциативный контейнер. Единственным требованием стандарта является то, что контейнер должен иметь ассоциативный интерфейс и поведение контейнера, реализация не определена. Хотя реализация соответствует сложности и требованиям интерфейса, является допустимой реализацией.

С другой стороны, std::map обычно реализуется с красно-черным деревом, как говорится в ссылке.

Answer 3

Внешне карта - это просто ассоциативный контейнер: она ведет себя внешне как "массив" (поддерживает a[x] выражение) где x может быть любым типом (не обязательно целым числом), "сопоставимым по <" (следовательно, упорядоченным).

Но:

• Так как x может быть любым значением, это не может быть простой массив (в противном случае он должен поддерживать любое значение индекса: если вы присваиваете [1] и [100], вам также нужны элементы 2..99 в середине)
• Поскольку он должен быть быстрым при вставке и обнаружении в любой позиции, он не может быть "линейной" структурой (в противном случае элементы должны быть смещены, а поиск должен быть последовательным, а требования "меньше времени пропорционального поиска").

Наиболее распространенная реализация использует внутренне самобалансирующееся дерево (каждый узел является парой ключ / значение, и они связаны друг с другом, так что левая сторона имеет более низкие ключи, а правая сторона имеет более высокие ключи, так что поиск выполняется повторно в двоичный поиск), список с несколькими пропусками (быстрее, чем дерево при извлечении, медленнее при вставке) или таблица на основе хеша (где каждое значение x перенаправляется в индекс массива)

Answer 4

Карта внутренне использует самобалансирующийся BST . Пожалуйста, посмотрите на эту ссылку. самобалансирующиеся бинарные поисковые деревья

Answer 5

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

Answer 6

Я бы сказал, что если вы думаете о карте как о паре, вы не ошибетесь. Карта может быть реализована в виде дерева или хеш-карты, но способ ее реализации не так важен, так как вы можете быть уверены, что любая реализация STL является эффективной.