在C++中如何从一个向量中删除包含在另一个向量中的所有元素？

Question

我有两个向量vc和v2，我想从vc中删除所有包含在v2中的元素。我试图通过两个嵌套循环来实现这一目标。然而，编译器报错：Debug Assertion Failed。我想问一下，为什么会这样，我该如何解决这个问题？谢谢！

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector <string> vc;
vector <string> v2;
int main()
{
    vc.push_back("ala");
    vc.push_back("bala");
    vc.push_back("test");
    vc.push_back("sample");
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
    v2.push_back("test");
    v2.push_back("bala");
    for (auto i = vc.begin(); i != vc.end(); i++) {
        for (auto j = v2.begin(); j != v2.end(); j++) {
            if (i == j) {
                vc.erase(i);
            }
        }
    }
    //it should print only ala and sample after  the removal process, but it gives
    //debug assertion error
    for (int i = 0; i < vc.size(); i++) {
        cout << vc[i] << endl;
    }
}

- D.Devletliev

---

从向量中删除项目会使在for循环中使用的迭代器无效，但是比较迭代器将始终失败，因为这些迭代器属于不同的向量，您应该比较值。 - user7860670

它必须是同一个向量吗，还是可以新建一个？目前你的程序崩溃，因为vc.erase(i)使得该点之后的所有迭代器无效。 - Qubit

迭代器可以进行比较吗？ - Jabberwocky

@Jabberwocky 显然它们可以被比较，但前提是两个迭代器必须属于同一个容器。 - user7860670

@VTT...这里并不是这种情况。 - Jabberwocky

Answer 1

正如评论中指出的那样，您的代码片段有两个未定义行为。首先，您比较了两个不引用相同容器的迭代器。其次，在调用vc.erase(i)时，vc迭代器和循环变量i会被使无效。

修复此问题是利用<algorithm>头文件和常见惯用语的好例子，因为手动实现此类操作容易出错。您需要使用所谓的删除-移除习惯用法。

#include <algorithm>

auto isInV2 = [&v2](const auto& element){
    return std::find(v2.cbegin(), v2.cend(), element) != v2.cend(); };

vc.erase(std::remove_if(vc.begin(), vc.end(), isInV2), vc.end());

根据您的应用情况，保持向量排序（或在某个时间点进行排序）并使用二进制搜索来检查元素是否存在可能更合适，这对于较大的序列具有更好的可扩展性。

auto isInV2LogN = [&v2](const auto& element){
    return std::binary_search(v2.cbegin(), v2.cend(), element); };

// Important: v2 must be sorted, otherwise std::binary_search doesn't work:
std::sort(v2.begin(), v2.end());

vc.erase(std::remove_if(vc.begin(), vc.end(), isInV2LogN), vc.end());

- lubgr

---

请在使用erase函数之前检查remove_if函数是否返回了end()，因为这是未定义的行为！ - Gelldur

如果remove_if返回一个end()迭代器，那么传递给std::vector::erase的半开区间[end, end)是空的，而且根据cppreference："如果first == last，则迭代器first不需要被解引用：擦除一个空范围是无操作。"@DawidDrozd我不同意。 - lubgr

@DawidDrozd 不用道歉 :) - lubgr

Answer 2

如果您被允许对输入进行排序，您可以使用std::set_difference函数：

std::vector<std::string> vc { "ala", "bala", "test", "sample" };
std::vector<std::string> v2 { "test", "bala" };

std::sort(vc.begin(), vc.end());
std::sort(v2.begin(), v2.end());

std::vector<std::string> res;
std::set_difference(vc.begin(), vc.end(),
                    v2.begin(), v2.end(), 
                    std::back_inserter(res));

演示

- Jarod42