Как реализован мультикартовый контейнер C ++?

Question

Например, вектор C ++ реализован с использованием динамического массива, где каждый элемент использует последовательные пространства памяти.

Я знаю, что мультикарта C ++ является отношением один ко многим, но какова внутренняя структура?

Answer 1

Стандарт C ++ не определяет, как должны реализовываться стандартные контейнеры, он только дает определенные ограничения, подобные тем, которые вы говорите для векторов.

мультикарты имеют определенную сложность во время выполнения (O (lg n) для интересногооперации) и другие гарантии, и могут быть реализованы как красно-черные деревья .Вот как они реализованы в стандартной библиотеке C ++ GNU.

Answer 2

Очень часто, красно-черное дерево . Смотрите, например Красно-черные деревья STL от Доктора Добба.

Answer 3

Добавление к «предпочтительному» ответу, потому что ТАК не позволяет мне комментировать:

Учитывая ключ со значениями B, C, D, поведение итераторов намного проще реализовать, если каждый элемент имеет свой собственный узел. Функция Find () определена так, чтобы вернуть первый результат в серии, а последующая итерация проведет вас по оставшимся элементам. Различие de facto между картой и мультикартой состоит в том, что мультикарта сортируется с использованием <по всему типу value_type, где карта использует <только по ключу </p>

Исправление: стандарт C ++ 11 явно указывает, что новые пары (ключ, отображение) вставляются в конце любых существующих значений, имеющих тот же ключ. Это поднимает вопрос, который я не рассматривал: может ли мультикарта содержать два узла, в которых и ключ, и сопоставленная цель совпадают. Стандарт, похоже, не занимает четкой позиции по этому вопросу, но следует отметить, что для сопоставленного типа не требуется оператор сравнения. Если вы напишите тестовую программу, вы обнаружите, что мультикарта может отображать X на 1, 2, 1. То есть: «1» может появляться несколько раз в качестве цели, и два экземпляра не будут объединены , Для некоторых алгоритмов это недостаток.

Эта статья от доктора Доббса рассказывает о базовой реализации rb-дерева, которая обычно используется. Главное, на что следует обратить внимание, это то, что операция перебалансировки на самом деле совершенно не заботится о ключах, поэтому вы можете создать rb-дерево, которое допускает дублирование ключей.

Answer 4

Мультикарта, как и ее более простая версия, то есть std :: map, в основном построена с использованием красных черных деревьев.Сам стандарт C ++ не определяет реализацию.Но в большинстве случаев (я лично проверял SGI STL) используются красные чёрные деревья.Красные Черные деревья являются деревьями, сбалансированными по высоте, и, следовательно, операция выборки / чтения для них всегда гарантированно будет иметь время O (log (n)).Но если вам интересно, как хранятся значения ключа.каждый key->pair сохраняется как отдельный узел в красном черном дереве (даже если один и тот же ключ может появляться несколько раз, как в случае с ключом 'b' ниже).Ключ используется для поиска / поиска в rb-дереве.Как только ключ найден, его значение, сохраненное в узле, возвращается.

  std::multimap<char,int> mmp;

  mmp.insert(std::pair<char,int>('a',10));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('b',10));
  mmp.insert(std::pair<char,int>('b',15));
  mmp.insert(std::pair<char,int>('b',20));
  mmp.insert(std::pair<char,int>('c',25));
  mmp.insert(std::pair<char,int>('a',15));
  mmp.insert(std::pair<char,int>('a',7));


for (std::multimap<char,int>::iterator it=mmp.begin(); it!=mmp.end(); ++it){

    std::cout << (*it).first << " => "  << (*it).second << " . Address of (*it).second = " << &((*it).second) << '\n';
}

Вывод:

a => 10 . Address of (*it).second = 0x96cca24
a => 15 . Address of (*it).second = 0x96ccae4
a => 7 . Address of (*it).second = 0x96ccb04
b => 20 . Address of (*it).second = 0x96cca44
b => 10 . Address of (*it).second = 0x96cca64
b => 15 . Address of (*it).second = 0x96cca84
b => 20 . Address of (*it).second = 0x96ccaa4
c => 25 . Address of (*it).second = 0x96ccac4

Изначально я думал, что значения одного ключа, такого как 'b' , могут храниться в std :: vector.

template <class K, class V>
struct Node {
  K key;
  std::vector<V> values; 
  struct Node* left;
  struct Node* right;
}

Но позже я понял, что это нарушит гарантированное время выборки O (log (n)).Кроме того, распечатка адресов значений подтверждает, что значения с общим ключом не являются смежными.

Эти ключи вставляются с использованием оператора <, поэтому значения с одинаковыми ключами сохраняются в том порядке, в котором они были вставлены. </p>

Поэтому, если мы вставим сначала (key = 'b', значение= 20), а затем (key = 'b', value = 10) Вставка выполняется с помощью оператора <, так как второе 'b' НЕ меньше первого вставленного 'b', оно вставляется в 'правую ветвьдвоичное дерево '. </p>

Я использовал компилятор gcc-5.1 (C ++ 14).