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

Ответ 1

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

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

Ответ 2

Очень часто, красно-черное дерево. См. STL Red-Black Trees от доктора Добба.

Ответ 3

Дополнить "предпочтительный" ответ, потому что SO не позволит мне прокомментировать:

Учитывая ключ со значениями B, C, D, поведение итераторов намного проще реализовать, если каждый элемент имеет свой собственный node. Функция Find() определена, чтобы вернуть первый результат в серии, и последующая итерация проведет вас по остальным элементам. Де-факто различие между картой и мультимапом состоит в том, что мультимап сортируется с использованием < по всему значению value_type, где используется карта < только за ключ_type

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

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

Ответ 4

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

  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)). Более того, распечатка адресов значений подтверждает, что значения с общим ключом не смежны.

Я думаю, что клавиша node в красном черном дереве мультимапа сделана из key_element + timestamp_of_insertion. Это объясняет, как элементы, имеющие один и тот же ключ, выбираются в порядке вставки (уникальные ключи сортируются, как и обычная карта). Ниже приведен псевдокод.

template<class K>
struct Key {
  K real_key;
  time_t cur_time ;
}

template<class V>
struct Node {
  Key k;
  V value;
  struct Node* left;
  struct Node* right; 
}

Компилятор, который я использовал, - gcc-5.1 (С++ 14).