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

Question

Я ищу тип контейнера ассоциативной карты C ++, для которого я могу выполнить несколько ключевых запросов. Карта должна иметь постоянный поиск по времени, но мне все равно, упорядочена она или нет. Это просто должно быть быстро.

Например, я хочу сохранить группу std::vector объектов на карте с int и void* в качестве ключей поиска. И int, и void* должны совпадать, чтобы мой вектор был извлечен.

Такой контейнер уже существует? Или мне придется кататься самостоятельно? Если да, то как я могу это реализовать? Я пытался сохранить boost::unordered_map внутри другого boost::unordered_map, но пока не добился успеха с этим методом. Может быть, я продолжу першировать этот метод, если нет более простого пути.

Answer 1

Постоянный поиск требует хэш-карту. Вы можете использовать boost :: unordered_map (или tr1). Ключом будет объединенный хеш для int и указателя void.

Answer 2

Если вы не хотите использовать повышение, вы можете попробовать map< int, map<void*, vector> >. Однако, поиски O (log (размер карты)).

Answer 3

Так как C ++ 11 , вы также можете использовать std::unordered_map, так как он вполне соответствует вашим требованиям:

Неупорядоченная карта - это ассоциативный контейнер, содержащий пары ключ-значение с уникальными ключами. Поиск, вставка и удаление элементов имеют среднюю сложность с постоянным временем.

Чтобы объединить ваши int и void* в одну клавишу, вы можете использовать std::pair.

Чтобы неупорядоченная карта работала с парой, вы должны указать подходящую хеш-функцию. Чтобы сохранить следующий пример коротким, я использую комбинацию ручной функции std::hash<> вызовов функций внутри лямбда-выражения . В случае, если эта функция вызывает проблемы с производительностью, вы можете создать более сложный хеш.

Вы не указали содержание своих векторов, поэтому я выбрал int для простоты. Однако вы можете адаптировать решение к любому векторному контенту. В целом ваш код может выглядеть следующим образом:

using Key = std::pair<int, void*>;
auto hash = [](const Key & k) {
    return std::hash<int>()(k.first) * 31 + std::hash<void*>()(k.second);
};
std::unordered_map<Key, std::vector<int>, decltype(hash)> um(8, hash);

Код на Ideone

Answer 4

Вы можете использовать boost :: multi_index .

(хотя я думаю, что вы на самом деле хотите использовать тип, который содержит как void *, так и целое число в качестве ключа ккарта, и просто для сравнения необработанных данных для обоих, чтобы обеспечить оператор сравнения для карты)