CODEWITHSUNDEEP
c++algorithmc++11dictionarystl
DuckQueen
DuckQueen

Reputation: 800

How to find all elements that correspond to a vector of keys?

I have a std::vector<std::string> k; with keys values of witch I seek for. I have a std::map<std::string, void*> table; I search in. I want to get a std::vector<void*> v; of values for all keys that are in k (if such values exist in table, not all keys can be presented in the table and this fact is not important for me, while the fact that there can be much more keys than in k is important). How to find all values that correspond to keys?

Using table[k_element] of table.find(k_element) for each element in k seems like a really bad way to do it also I could not find any algorithm in STL that could do it in a group manner...(

Upvotes: 1

Views: 164

Answers (2)

dlavila
dlavila

Reputation: 1212

There are differents solutions to your problem, some of them:

  • Put all the keys in k into a unordered_set, iterate over the table and lookup for each key in the set, you will obtain O(n). You could consider change the table for a data structure that store elements in continuous memory (perhaps the map using a pool allocator or a data structure with a std::vector behind the curtains), that way the algorithm will be more cache friendly (thus, probably considerable faster), although the insertion time into this data structure will be slow.
  • Iterate over k and lookup for each key in the table, you will obtain O(k*log(n)), if you change your table for a unordered_map you can obtain O(k). Although, you have to take into account that calculating the hash of a string can be very slow, sometimes is better to compare strings and have log time for the lookup, than calculate the hash of the key and have constant time for the lookup. The choice depends on the extension and nature of the keys.
  • You can sort the elements in k and iterate over the ordered set, after each lookup you will know the starting point for the next search, thus each lookup will be faster than the previous one. As the std::map don´t allow you to provide a starting point for the search, you could implement your own binary search tree with this functionality.

And many many more, the best solution depends on the size of your data sets, the nature of your keys and other factors. Study the problem, pick one or two solutions, implement it, test it and iterate if necessary.

Upvotes: 0

Oliver Dain
Oliver Dain

Reputation: 9953

using table[k_element] or table.find(k_element) for each element in k seems like a really bad way

I'm not sure why that feels like a bad way. Even if there were an aglorithm in the STL to do this for you, it would have to either iterate through each value in k -- there's isn't a solution to this problem that's faster than linear time. I think sometimes people think that one line of code is always faster than a loop even if that one line of code calls a function containing a loop.

There are ways to do this in a line with lambdas, map and such, but that's not "better" or faster, just less readable.

Upvotes: 3

Related Questions