CODEWITHSUNDEEP
c++dictionary
iammilind
iammilind

Reputation: 69988

What's the best way to search from several map<key,value>?

I have created a vector which contains several map<>.

vector<map<key,value>*> v;
v.push_back(&map1);
// ...
v.push_back(&map2);
// ...
v.push_back(&map3);

At any point of time, if a value has to be retrieved, I iterate through the vector and find the key in every map element (i.e. v[0], v[1] etc.) until it's found. Is this the best way ? I am open for any suggestion. This is just an idea I have given, I am yet to implement this way (please show if any mistake).

Edit: It's not important, in which map the element is found. In multiple modules different maps are prepared. And they are added one by one as the code progresses. Whenever any key is searched, the result should be searched in all maps combined till that time.

Upvotes: 0

Views: 304

Answers (4)

Kerrek SB
Kerrek SB

Reputation: 477010

It depends on how your maps are "independently created", but if it's an option, I'd make just one global map (or multimap) object and pass that to all your creators. If you have lots of small maps all over the place, you can just call insert on the global one to merge your maps into it.

That way you have only a single object in which to perform lookup, which is reasonably efficient (O(log n) for multimap, expected O(1) for unordered_multimap).

This also saves you from having to pass raw pointers to containers around and having to clean up!

Upvotes: 1

Xeo
Xeo

Reputation: 131789

If the keys do not overlap, i.e., are unique througout all maps, then I'd advice a set or unordered_set with a custom comparision functor, as this will help with the lookup. Or even extend the first map with the new maps, if profiling shows that is fast enough / faster.

If the keys are not unique, go with a multiset or unordered_multiset, again with a custom comparision functor.

You could also sort your vector manually and search it with a binary_search. In any case, I advice using a tree to store all maps.

Upvotes: 1

Ben Voigt
Ben Voigt

Reputation: 283624

If you need to know which submap the key was found in, try:

unordered_set<key, pair<mapid, value>>

This has much better complexity for searching.

Upvotes: 1

Mark Wilkins
Mark Wilkins

Reputation: 41222

Without more information on the purpose and use, it might be a little difficult to answer. For example, is it necessary to have multiple map objects? If not, then you could store all of the items in a single map and eliminate the vector altogether. This would be more efficient to do the lookups. If there are duplicate entries in the maps, then the key for each value could include the differentiating information that currently defines into which map the values are put.

Upvotes: 3

Related Questions