Является ли boost :: bimap избыточным для инъективных функций?
Пусть T_1 и T_2 — два типа, а f: Dom (T_1) -> Dom (T_2) — инъективная функция, которая не является биекцией; и ради обсуждения предположим, что я получаю представление f как разнородные пары, а не код для ее вычисления. Теперь мне нужно относительно быстро применить и f, и f ^ {- 1}, поэтому я думал о карте в каждом направлении. Затем мне пришло в голову, что мне может понадобиться структура данных для этих двух карт вместе — так как у меня есть несколько таких f.
Я естественно подумал: «Хм, я уверен, что у Boost должно быть что-то подобное», и действительно, у Boost есть Bimap состав. Дело в том, что он предназначен для общих бинарных отношений; Кроме того, он должен учитывать возможность повторных вставок без повторной оптимизации структуры каждый раз, в то время как в моем случае я вставляю только один раз, а затем выполняю много поисков. Итак, я чувствую, что bimap может быть немного излишним для меня и неоптимизированным для моего варианта использования. Это правда?
Заметки:
- Меня интересует сложность времени (и фактическое время) за счет пространства.
- Тот же вопрос для неинъективного f (где f ^ {- 1} — нефункциональное отношение).
Решение
Нормальное поведение контейнера C ++ (подкрепленное вашей подсказкой о размере объекта) хранить каждый ключ и значение (какие понятия различны только в неинъективном случае) только один раз. Отдельные фазы вставки и поиска предлагают непрерывное хранение (для кеша, если ничего другого). «Время за счет пространства» говорит, что вы хотите хеш-таблица.
Так что храните массив pair<T1,T2> и пара с низким коэффициентом нагрузки, открыть имя хеш-таблицы, отображающие ключи и значения (соответственно) на индексы в массиве. Каждый из них является не чем иным, как массивом индексов (или указателей, вычисленных после выделения (полного) массива) и имеет приличную производительность кэша.
Сортировать (или хотя бы группировать) пары по (неуникальному) T2 значение и сохраните в хеш-таблице (для каждого такого уникального значения) индекс начало бега. Тогда все соответствующие T1 объекты могут быть найдены вместе (остановка на первом отличающемся T2 или в конце массива).
Если есть много T2 объекты, которые == и они взаимозаменяемый, вместо этого вы можете хранить отдельные массивы pair<T1,index> а также pair<T2,index>каждый хранит индексы в другом, как указано выше. Каждая запись в и то и другое Затем хеш-таблицы хранят индексы в T1 массив, так как любой ключ всегда необходим для проверки на равенство после поиска в хэш T2 Объект в паре сразу и однозначно доступен из индекса, хранящегося рядом с T1,
Другие решения
Других решений пока нет …
detector