高效查找std::vector元素并将缺失元素补充至另一vector的方法

嘿，我来帮你搞定这个需求，先补全并修正你的代码，再聊聊怎么优化效率～

基础实现代码 #

首先修正你代码里的笔误（MatTempVe应该是MatTempVec），这是最直接的实现方式：

#include <vector>
#include <algorithm> // 必须包含这个头文件才能使用std::find

int main() {
    std::vector<long> Matvec = {1, 3, 5, 7, 9}; // 示例5个元素
    std::vector<long> MatTempVec(100, 2); // 示例100个元素，这里用2填充
    
    for (auto it = Matvec.begin(); it != Matvec.end(); ++it) {
        // 在大vector中查找当前元素
        auto findIt = std::find(MatTempVec.begin(), MatTempVec.end(), *it);
        if (findIt == MatTempVec.end()) {
            // 元素不存在，添加到大vector末尾
            MatTempVec.push_back(*it);
        }
    }
    
    return 0;
}

代码说明 #

• 遍历小容器Matvec的每一个元素
• 用std::find在大容器MatTempVec中做线性查找
• 如果返回的迭代器等于MatTempVec.end()，说明该元素不存在，就把它追加到大容器末尾

高效优化方案 #

如果大容器的元素数量特别多（比如上万条），上面的线性查找会比较慢（每次查找时间复杂度是O(n)）。这时候可以用std::unordered_set来优化查找速度，平均查找时间是O(1)：

#include <vector>
#include <unordered_set>

int main() {
    std::vector<long> Matvec = {1, 3, 5, 7, 9};
    std::vector<long> MatTempVec(100, 2);
    
    // 先把大容器的元素存入哈希集合，建立快速查找索引
    std::unordered_set<long> tempElementSet(MatTempVec.begin(), MatTempVec.end());
    
    for (const auto& elem : Matvec) {
        if (tempElementSet.find(elem) == tempElementSet.end()) {
            // 元素不存在，添加到大容器
            MatTempVec.push_back(elem);
            // 同步加入集合，避免Matvec有重复元素时重复添加
            tempElementSet.insert(elem);
        }
    }
    
    return 0;
}

优化说明 #

• std::unordered_set是哈希表实现的容器，查找效率远高于vector的线性遍历
• 如果你的Matvec里可能有重复元素，加入集合可以避免重复添加同一个元素；如果希望重复元素也全部追加，去掉tempElementSet.insert(elem)这一行即可

内容的提问来源于stack exchange，提问作者Kawin Anto