Является ли 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> и пару хэш-таблиц с низким коэффициентом загрузки *1013* с открытым адресом, отображающих ключи и значения (соответственно) в индексы в массиве. Каждый из них представляет собой не что иное, как массив индексов (или указателей, вычисленных после выделения (полного) массива) и имеет приличную производительность кэша.

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

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

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