Является ли boost::bimap избыточным для инъективных функций?

Question

Пусть T_1 и T_2 - два типа, а f: Dom(T_1) -> Dom(T_2) - инъективная функция, которая не является биекцией; и ради обсуждения предположим, что я получаю представление f как разнородные пары, а не код для ее вычисления. Теперь мне нужно относительно быстро применить и f, и f^{-1}, поэтому я думал о карте в каждом направлении. Затем мне пришло в голову, что мне может понадобиться структура данных для этих двух карт вместе - так как у меня есть несколько таких f.

Я естественно подумал: "Хм, я уверен, что у Boost должно быть что-то подобное", и действительно, у Boost есть структура Bimap. Дело в том, что он предназначен для общих бинарных отношений; Кроме того, он должен учитывать возможность повторных вставок без повторной оптимизации структуры каждый раз, в то время как в моем случае я вставляю только один раз, затем выполняю много операций поиска. Итак, я чувствую, что bimap может быть немного излишним для меня и неоптимизированным для моего варианта использования. Это правда?

Заметки:

• Меня интересует сложность времени (и фактическое время) за счет пространства.
• Тот же вопрос для неинъективного f (где f^{-1} - нефункциональное отношение).

Answer 1

Обычное поведение контейнера C++ (подкрепленное вашей подсказкой о размере объекта) состоит в том, чтобы хранить каждый ключ и значение (которые различаются только в неинъективном случае) только один раз. Отдельные фазы вставки и поиска предлагают непрерывное хранение (для локальности кэша, если ничего больше). "Время за счет пространства" говорит, что вы хотите хеш-таблицу.

Так что храните массив pair<T1,T2> и пару хеш-таблиц с низким коэффициентом загрузки и открытыми адресами, отображающих ключи и значения (соответственно) на индексы в массиве. Каждый из них является не чем иным, как массивом индексов (или указателей, вычисленных после выделения (полного) массива) и имеет приличную производительность кэша.

Неинъективный случай

Сортировать (или хотя бы группировать) пары по (неуникальному) T2 значение и сохраните в хеш-таблице (для каждого такого уникального значения) индекс начала цикла. Тогда все соответствующие T1 объекты могут быть найдены вместе (остановка на первом отличающемся T2 или в конце массива).

Если есть много T2 объекты, которые == и они являются взаимозаменяемыми, вместо этого вы можете хранить отдельные массивы pair<T1,index> а также pair<T2,index>каждый хранит индексы в другом, как указано выше. Каждая запись в обеих хеш-таблицах затем сохраняет индексы в T1 массив, так как любой ключ всегда необходим для проверки на равенство после поиска в хэш T2 Объект в паре сразу и однозначно доступен из индекса, хранящегося рядом с T1,