C++删除vector中存在于另一vector的元素方案是否合理？

我想要删除vector容器v中所有被另一vector容器v2包含的元素，编写了如下实现代码，运行输出结果为4 5，咨询该实现方案是否合理，是否需要改用其他实现方式。

原实现代码 #

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    std::vector<int> v = {1,2,3,4,5,1,2};
    std::vector<int> v2 = {1,2,3};
    
    v.erase(std::remove_if(v.begin(), v.end(), [v2](int x)
    {   
        auto it = std::find(v2.begin(), v2.end(), x);
        return it != v2.end();  
    }), v.end());
    
    for (auto i : v)
    {
        std::cout<<i<< " ";
    }

    return 0;
}

运行输出 #

4 5

你的实现逻辑正确，在测试用例下可以得到预期结果，但是否需要调整取决于实际使用场景下的容器数据规模：

• 如果两个容器的元素量都很小（比如均为数十个元素级别），当前写法逻辑直白、可读性强，完全可以正常使用，不需要修改。
• 如果容器元素量较大，当前实现的时间复杂度为O(N*M)（N为v的元素总数，M为v2的元素总数）：remove_if会遍历v的每一个元素，每次判断元素是否需要删除时，都会线性遍历v2做查找，数据量上升后性能衰减非常明显，建议做优化。

可选优化方案 #

方案1：哈希集合查找（平均性能最优） #

先把v2的所有元素存入unordered_set，把单次元素查找的时间复杂度降到O(1)，整体时间复杂度为O(N+M)，适合绝大多数数据规模较大的场景：

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>

using namespace std;

int main()
{
    std::vector<int> v = {1,2,3,4,5,1,2};
    std::vector<int> v2 = {1,2,3};
    std::unordered_set<int> delete_set(v2.begin(), v2.end());
    
    v.erase(std::remove_if(v.begin(), v.end(), [&delete_set](int x)
    {   
        // C++20及以上版本可直接写 return delete_set.contains(x);
        return delete_set.count(x) > 0;
    }), v.end());
    
    for (auto i : v)
    {
        std::cout << i << " ";
    }

    return 0;
}

方案2：排序+二分查找（无额外哈希开销） #

如果不想引入哈希结构的额外内存开销，可以先对v2排序，之后用二分查找判断元素是否存在，单次查找时间复杂度为O(logM)，整体时间复杂度为O(NlogM + MlogM)，缓存友好性更好：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    std::vector<int> v = {1,2,3,4,5,1,2};
    std::vector<int> v2 = {1,2,3};
    std::sort(v2.begin(), v2.end());
    
    v.erase(std::remove_if(v.begin(), v.end(), [&v2](int x)
    {   
        return std::binary_search(v2.begin(), v2.end(), x);
    }), v.end());
    
    for (auto i : v)
    {
        std::cout << i << " ";
    }

    return 0;
}

注意：以上两种优化方案都不受v2内存在重复元素的影响，删除逻辑和原实现完全一致。

内容的提问来源于stack exchange，提问作者Karl D