c++ - 如何有效地从给定另一个 vector 的 vector 中删除元素

Question

从给定另一个 vector 的 vector 中删除元素的最佳方法是什么？

我想出了以下代码:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() 
{
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    for(auto i:v3)
        cout << i << endl;
    return 0;
}

这里的输出将是:

7
8
9

Answer 1

我的版本如下，我只申请了erase vector 中的所有元素 vSource已被std::remove移到最后并跟踪指向 vector 末尾的指针 vDestination不要无缘无故地迭代它。

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    auto last = std::end(vDestination);
    std::for_each(std::begin(vSource), std::end(vSource), [&](const int & val) {
        last = std::remove(std::begin(vDestination), last, val);
    });
    vDestination.erase(last, std::end(vDestination));
}

参见大肠杆菌:http://coliru.stacked-crooked.com/a/6e86893babb6759c

---

更新

这里是一个模板版本，所以你不用关心容器类型:

template <class ContainerA, class ContainerB>
void remove_elements(ContainerA & vDestination, const ContainerB & vSource) 
{
    auto last = std::end(vDestination);
    std::for_each(std::begin(vSource), std::end(vSource), [&](typename ContainerB::const_reference val) {
        last = std::remove(std::begin(vDestination), last, val);
    });
    vDestination.erase(last, std::end(vDestination));
}

---

注意

此版本适用于没有任何约束的 vector ，如果您的 vector 已排序，您可以采取一些快捷方式，避免反复迭代 vector 以删除每个元素。