寻找提取经vector键过滤的unordered_map值的最快方法

你的这段代码确实有很大的优化空间——每次遍历unordered_map的元素时，都用std::find在to_find向量里做线性查找，这会让整体时间复杂度达到O(M*N)（M是map的元素数，N是to_find的长度），当其中任意一个容器规模较大时，性能会急剧下降。

核心优化思路：用哈希集合替代线性查找 #

把to_find转换成std::unordered_set<uint32_t>，这样判断某个key是否存在的操作会从O(N)降到O(1)，整体时间复杂度就变成了O(M + N)，效率提升非常明显。

优化后的代码 #

#include <unordered_map>
#include <vector>
#include <unordered_set>

std::unordered_map<uint32_t, user> map;
std::vector<uint32_t> to_find;
std::vector<user> results;

// 先把to_find转换成unordered_set，构建成本是O(N)
std::unordered_set<uint32_t> to_find_set(to_find.begin(), to_find.end());

// 遍历map，每个key的查找是O(1)
for (const auto& pair : map) {
    if (!to_find_set.contains(pair.first)) { // C++20及以上可用contains，更直观
        results.push_back(pair.second);
    }
}

兼容C++20之前版本的写法 #

如果你的编译器不支持C++20的contains方法，可以用find替代：

for (const auto& pair : map) {
    if (to_find_set.find(pair.first) == to_find_set.end()) {
        results.push_back(pair.second);
    }
}

额外场景：如果需要提取存在于to_find中的元素 #

如果你的需求是反过来（收集map中key在to_find里的元素），还可以换一种遍历方式——直接遍历to_find，然后在map中查找，这样避免遍历整个map：

std::vector<user> results;
results.reserve(to_find.size()); // 提前预留空间，避免多次扩容

for (uint32_t key : to_find) {
    auto it = map.find(key);
    if (it != map.end()) {
        results.push_back(it->second);
    }
}

这种方式的时间复杂度也是O(M + N)，但如果to_find的长度远小于map的大小，会更高效。

其他小优化 #

• 提前调用results.reserve(map.size())（或者预估的元素数），可以避免vector在push_back时多次内存扩容，进一步提升性能。

内容的提问来源于stack exchange，提问作者Fabio Zanini