c++ - 通过键 vector 从 map 获取 map

Question

我想知道是否有 std::map 的函数来接收由键的 std::vector 定义的子映射。就像 std::map.at(key) 函数一样，但具有 std::vector 键。我知道我可以迭代 map 并将 map 对添加到新 map 中，但我想知道是否有内置函数，或者可能是获取子 map 的更快方法。

示例代码:

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

是否有这样的函数，或者通常有比迭代整个 map 并每次使用 find 函数更聪明的方法(我知道我可以迭代 vector ，但这并没有多大区别，或者是吗？)。

Answer 1

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

这确实有所不同，因为 vector 的按顺序迭代通常比映射更快( vector 数据位于内存中，而映射元素不是)，并且在映射中查找元素比在 vector 中更快(O(log(N)) 与未排序 vector 的 O(N))。

假设您在映射中有 M 个元素，在 vector 中有 N 个键，那么您的方法是 O( M * N)而交换迭代和查找的时间复杂度仅为O( N * log(M))。这仅考虑了 find 的复杂性。考虑到迭代更加复杂，因为它很大程度上取决于缓存。

否则，我认为你的方法很好。我不知道有什么算法可以使您的代码更加简洁或更具表现力。

PS 你可能会认为这是措辞上的挑剔，但由于人们经常会过度思考问题，我会提到这一点:“更聪明的方法”并不总是“更好的方法” 。不要试图变得太聪明。大多数算法都可以用简单的循环代替，但通常认为它们比手写循环更具表现力和可读性。当手头的问题没有算法时，尝试将某些内容挤入算法中，通常会导致代码可读性和表达能力较差。如果有人找到可以在这里使用的算法，我将收回此 PS 中的所有内容:P