Get map from map by vector of keys

user_9227188 0
Viewed 146

I was wondering, if there is a function of std::map to receive a sub-map defined by a std::vector of keys. So just like the std::map.at(key) function but with a std::vector of keys. I know I can iterate over the map and adding the map pairs to a new map, but I was wondering, if there is a built in function, or maybe a faster way to get a sub-map.

example code:

std::map<std::string, int> map = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};
std::vector<std::string> keys = {"a", "c", "d"};
// using iteration:
std::map<std::string, int> new_map;
for(auto it = map.begin(); it != map.end(); ++it){
    if(std::find(keys.begin(), keys.end(), it->first) != keys.end()){
        new_map.insert(*it);
    }
}
// new_map should be {{"a",1}, {"c",3}, {"d",4}}

// What I am hoping to find is something like:
new_map = map.at(keys);

//resulting in the same new_map {{"a",1}, {"c",3}, {"d",4}}.

Is there such a function or in general a smarter way than iterating over the whole map and using the find function every time (I know I could iterate over the vector, but this doesn't make much of a difference, or does it?).

c++17 stdmap c++
3 Answers

I know I could iterate over the vector, but this doesn't make much of a difference, or does it?

It does make a difference, because iterating in order is typically faster for a vector than for a map (vectors data is local in memory, a maps elements are not) and finding an element is faster in a map than in a vector (O(log(N)) vs O(N) for an unsorted vector).

Lets say you have M elements in the map and N keys in the vector, then your approach is O( M * N) while swapping iteration and finding would be only O( N * log(M)). This only takes into account the complexity for find. Taking into account the iteration is more involved as it very much depends on cache.

Otherwise, I think your approach is fine. I am not aware of an algorithm that would make your code more concise or expressive.

PS you might consider this as a nitpick on wording, but as it happens too often that one overthinks a problem I will mention it: "a smarter way" is not always "a better way". Dont try to be too smart. Most algorithms can be replaced by a simple loop, but often they are considered more expressive and readable than the handwritten loop. Trying to squeeze something into algorithms when there is no algorithm for the problem at hand, often results in less readable and less expressive code. If someone finds an algorithm that can be used here, I'll take back everything in this PS :P

user_41177280

I would also consider using std::copy_if algorithm. It does not save too many characters in the source code here, but it's more explicit:

std::map<std::string, int> map = {{"a", 1}, {"b", 2}, {"c", 3}, {"d", 4}, {"e", 5}};
std::unordered_set<std::string> keys = {"a", "c", "d"};
std::map<std::string, int> new_map;

std::copy_if(map.begin(), map.end(),
             std::inserter(new_map, new_map.end()),
             [&keys](const auto& e){ return keys.find(e.first) != keys.end(); });

Live demo here.

In C++20, we will be able to write this even more compactly:

std::copy_if(map.begin(), map.end(),
             std::inserter(new_map, new_map.end()),
             [&keys](const auto& e){ return keys.contains(e.first); });
user_5800830

Starting from formerlyknownas_463035818's answer (so iterating over keys instead over map) seems to me that the "algorithm way" (meaning: using the standard algorithms in <algorithm> header) could be the use of std::transform()

std::transform(keys.cbegin(), keys.cend(),
               std::inserter(new_map, new_map.end()),
               [&](auto const & k) -> std::pair<std::string, int>
                { return {k, map[k]}; });

but (IMHO) is far more readable the good-old loop way

for ( auto const & k : keys )
   new_map[k] = map[k];

Off Topic Unrequested Suggestion: don't use "map" (the same name of the class, ignoring the namespace) for a "std::map" variable. Maybe works and nobody add a using std;... but why challenge fate?

user_60226560
Related