c++ - 如何删除 vector 中与另一个 vector 中的某些元素匹配的元素

Question

我想删除 vector v2 中与另一个 vector v1 中的元素匹配的元素，其中 v1 中的每个元素都有对应的v2 中的元素，但反之则不然。

我的想法是像这样使用 std::vector::erase、std::remove_if 和 std::find:

std::vector<int> v1{ 6, 2, 4 };
std::vector<int> v2{ 8, 2, 9, 4, 5, 3, 7, 1, 6 };

v2.erase(
  std::remove_if(v2.begin(), v2.end()
  , [&v1](auto& item)
  {
    return std::find(v1.begin(), v1.end(), item) != v1.end();
  })
);

哪个有效。但是，我想知道我是否可以不匹配已经匹配的那些，因为从 v1 -> v2 开始时这是 1:1 的关系。 v1之后会被吹走，所以可以修改。

Answer 1

排序 v1。使用 std equal range 在其中查找元素。将其与您的删除-删除习语代码一起使用(带有错误修复)。

这是 O((M+N)lg N)

std::sort( v1.begin(), v1.end() );
auto removed=std::remove_if(
  v2.begin(), v2.end(), 
  [&v1](auto& item)
  {
    auto r= std::equal_range(v1.begin(), v1.end(), item);
    return r.first!=r.second;
  }
);
v2.erase(removed, v2.end());

请注意，您在删除调用中忘记了 .end，这是执行删除删除时常见的严重错误。

如果您有合理数量的条目，编辑源 vector 以消除元素是不值得的，除非非常奇特的数据结构。