CODEWITHSUNDEEP
c++dictionarycontainersstdmap
Morgan
Morgan

Reputation: 1897

How can I implement a fast map having multiple keys?

I'm looking for a C++ associative map container type which I can perform multiple key lookups on. The map needs to have constant time lookups, but I don't care if it's ordered or unordered. It just needs to be fast.

For example, I want to store a bunch of std::vector objects in a map with an int and a void* as the lookup keys. Both the int and the void* must match for my vector to be retrieved.

Does such a container exist already? Or am I going to have to roll my own? If so, how could I implement it? I've been trying to store a boost::unordered_map inside another boost::unordered_map, but I have not had any success with this method, yet. Maybe I will continue Pershing this method if there is no simpler way.

Upvotes: 6

Views: 8651

Answers (4)

honk
honk

Reputation: 9743

Since C++11 you can also use an std::unordered_map, as it seems to fit your requirements quite nicely:

Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

In order to combine your int and void* into a single key, you can make use of std::pair.

To make the unordered map work with the pair, you have to specify a suitable hash function. In order to keep the following example short, I use a handcrafted combination of std::hash<> function calls inside a lambda expression. In case this function causes performance problems, you might want to create a more sophisticated hash.

You didn't specify the content of your vectors, so I chose int for the sake of simplicity. However, you can adapt the solution to any vector content. All in all your code could look as follows:

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);

Code on Ideone

Upvotes: 1

Vlad
Vlad

Reputation: 35584

If you don't want to use boost, you can try map< int, map<void*, vector> >. The lookups are however O(log(map size)).

Upvotes: 2

pmr
pmr

Reputation: 59811

Constant look up requires a hash map. You can use a the boost::unordered_map (or tr1). The key would be the combined hash of the int and the void pointer.

Upvotes: 4

James
James

Reputation: 25513

You could use boost::multi_index.

(although I think what you actually want is to use a type that contains both the void* and the integer as the key to your map, and just to compare the raw data for both in order to provide the comparison operator for the map)

Upvotes: 0

Related Questions