Как мультикарты внутренне обрабатывают повторяющиеся ключи?

С картами я могу понять, что это реализуется как двоичное дерево поиска (например, красное/черное дерево) и его временная сложность.

Но как внутри мультикарты обрабатываются коллизии клавиш? Список поддерживается для всех узлов с одинаковыми ключами? Или какая-то другая обработка предпринимается. Я столкнулся с ситуацией, когда я мог бы использовать либо map<int,vector<strings>>, либо multimap<int,string>, и хотел бы знать компромиссы.


c++ dictionary data-structures multimap
person basav    schedule 23.01.2015    source источник
comment
Ваш вопрос, какой конкретный базовый механизм используется для обработки коллизий, или использовать ли map с vector ключами или multimap? На самом деле это совсем другие вопросы.   -  person templatetypedef    schedule 23.01.2015
comment
Я хотел знать конкретную внутреннюю реализацию мультикарты...   -  person basav    schedule 23.01.2015
comment
@basav Разные компиляторы могли реализовать это по-разному. Просто что бы ты знал. Нет никаких конкретных ограничений на то, как их реализовать, подразумеваемых стандартом C++.   -  person mostruash    schedule 23.01.2015
comment
Как мне решить, имеет ли смысл карта вектора строк или мультикарта строк с точки зрения временной сложности для вставки и поиска ??   -  person basav    schedule 23.01.2015
comment
@mostruash Интересно, что ограничения спецификации фактически запрещают множество потенциальных реализаций. Интересно работать в обратном направлении и смотреть, что можно разрешить, а что нельзя.   -  person templatetypedef    schedule 23.01.2015

Ответы (1)


arrow_upward
6
arrow_downward

Спецификация C++ не дает конкретной реализации для std::multimap, а вместо этого дает требования к тому, насколько быстрыми должны быть операции с std::multimap и какие гарантии должны соблюдаться для этих операций. Например, insert на multimap необходимо вставить пару ключ/значение в multimap и сделать это таким образом, чтобы он шел после всех существующих записей с тем же ключом. Это должно сработать за время O(log n) и, в частности, амортизировать O(1), если вставка происходит с подсказкой, а подсказка находится прямо перед тем, куда должен идти элемент. Только с этой информацией multimap может работать, имея красно-черное дерево со многими узлами, по одному на ключ, или это может быть красно-черное дерево, хранящее vector значений для каждого ключа. (Однако это исключает дерево AVL, потому что повороты, связанные с вставкой дерева AVL, не выполняются за амортизированное время O (1). Однако это также допускает такие вещи, как деревья 2-3-4 или детерминированные списки пропусков).

Однако по мере того, как мы добавляем новые требования, некоторые реализации исключаются. Например, операция erase должна выполняться в амортизированное постоянное время, если элементу для стирания задан итератор. Это исключает использование одного узла с ключом и vector значений, но не исключает одного узла с ключом и двусвязным списком значений. Тип iterator должен иметь возможность разыменовывать тип value_type, который должен соответствовать базовому типу allocator value_type. Это исключает возможность того, что у вас могут быть отдельные узлы в красно-черном дереве с одним ключом и связанным списком значений, поскольку таким образом вы не сможете получить ссылку на value_type.

В целом ограничения таковы, что одна допустимая реализация — это красно-черное дерево с одним узлом на пару ключ/значение, хотя возможны и другие варианты. Другие идеи, такие как использование дерева AVL или объединение значений для данного ключа в vector или list, невозможны.

Надеюсь это поможет!

person templatetypedef    schedule 23.01.2015
comment
работа в обратном направлении от спецификации и выяснение того, что подходит, было бы отличным способом изучить stl . - person basav; 23.01.2015