通过键向量从地图获取地图

Question

我在想，是否有std::map的功能来接收由std::vector键定义的子地图。所以就像 std::map.at(key) 函数一样，但有一个 std::vector 键。我知道我可以遍历地图并将地图对添加到新地图，但我想知道是否有内置函数，或者是否有更快的方法来获取子地图。

示例代码：

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}}.

是否有这样的函数或通常比遍历整个地图并每次都使用查找函数更聪明的方法（我知道我可以遍历向量，但这并没有太大的区别，或者是吗？）。

Answer 1

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

它确实有所不同，因为按顺序迭代向量通常比地图更快（向量数据在内存中是本地的，地图元素不是）并且在地图中查找元素比在地图中查找元素更快向量（O(log(N)) vs O(N) 对于未排序的向量）。

假设您在地图中有 M 个元素，在向量中有 N 个键，那么您的方法是 O( M * N) 而交换迭代和查找只会 O( N * log(M)).这仅考虑了 find 的复杂性。考虑到迭代更多地涉及，因为它在很大程度上取决于缓存。

否则，我觉得你的做法没问题。我不知道有什么算法可以使您的代码更简洁或更具表现力。

PS 你可能会认为这是措辞上的吹毛求疵，但由于这种情况经常发生，以至于人们想得太多了，我会提到它："a smarter way" 并不总是 "a better way"。不要自作聪明。大多数算法都可以用一个简单的循环代替，但它们通常被认为比手写循环更具表现力和可读性。当手头的问题没有算法时，试图将某些东西塞进算法中，通常会导致代码的可读性和表达力较差。如果有人在这里找到可以使用的算法，我会收回这PS中的所有内容：P

Answer 2

我也会考虑使用 std::copy_if 算法。这里的源代码中并没有保存太多的字符，而是更加明确：

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

现场演示 here。

在C++20中，我们可以写得更简洁：

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

Answer 3

从 formerlyknownas_463035818 的回答开始（因此遍历 keys 而不是 map）在我看来 "algorithm way"（意思是：使用标准算法<algorithm> header) 可以使用 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]}; });

但是（恕我直言）good-old 循环方式

更具可读性

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

题外话不请自来的建议：不要对“std::map”变量使用“map”（与class同名，忽略名称空间）。也许可行，但没有人添加 using std;... 但为什么要挑战命运？

通过键向量从地图获取地图

Get map from map by vector of keys

c++

stdmap

c++17