Эффективный C ++ ассоциативный контейнер с векторным ключом

Question

Я построил карту, в которой ключом является вектор: map<vector<KeyT>, T>, который я сейчас пытаюсь оптимизировать.

Эксперимент с вложенными вручную картами map<vector<KeyT>, map<KeyT,T> >, где первый ключ - исходный вектор минус последний элемент, а второй ключ - последний элемент, показывает разумное ускорение.

Теперь мне интересно, существует ли полустандартная реализация (например, boost или аналогичная) ассоциативного контейнера, в котором векторные ключи реализованы в виде такой иерархической структуры контейнеров.

В идеале это позволило бы создать столько слоев, сколько имеется элементов в векторе ключа, при сохранении единого синтаксиса для векторов разной длины.

Answer 1

Вы уверены, что вам нужно оптимизировать его? std :: string в основном похож на std :: vector, и мы с радостью используем std :: string в качестве ключа массива!

Вы профилировали свой код? std :: map не копирует свои пары ключ / значение без необходимости - чего именно вы боитесь?

Ваши векторные ключи имеют фиксированный размер? std :: tuple может помочь в этом случае.

Если нет, это может помочь разделить ваши контейнеры по длине ключа, хотя эффективность таких схем сильно зависит от домена.

Answer 2

Моя первая догадка - вы хотите улучшить время поиска карты, уменьшив громкость ключа.Для этого и нужны хеш-функции.В C ++ tr1 и Boost есть hash_maps с именем unordered_map

. Я постараюсь разработать небольшой пример здесь через некоторое время