c++ - 删除一个 vector 中包含在另一个 vector 中的所有元素的优雅方法？

Question

在查看一些代码时，我发现 std::set_difference 的实现循环和算法缓慢:

 for(int i = 0; i < a.size(); i++)
 {
  iter = std::find(b.begin(),b.end(),a[i]);
  if(iter != b.end())
  {
     b.erase(iter);
  }
 }

它可以很容易地替换为排序( vector 未排序)+ set_difference，但这需要分配新的内存(参见我最近的问题 Can output of set difference be stored in first input? 为什么它不能“就地”完成)。
所以我的解决方案是这样的:

sort(a.begin(), a.end());
for(size_t i = 0; i < b.size(); i++)
{
 if (binary_search(a.begin(), a.end(), b[i]))
 {
     swap(b[i], b[b.size()-1]); //remove current element by swapping with last
     b.pop_back();     // and removing new last by shrinking
 }
}

可以做得更优雅吗？
优雅是主观的，所以在这个 Q 的范围内被定义为更清晰的代码(最好是来自 STL 算法的东西，但我认为它不能完成)但没有内存分配，也没有增加算法的复杂性。

Answer 1

这一个在 O(N+M) 中完成，假设两个数组都已排序。

  auto ib = std::begin(two);
  auto iter = std::remove_if (
       std::begin(one), std::end(one),
       [&ib](int x) -> bool {
                       while  (ib != std::end(two) && *ib < x) ++ib;
                       return (ib != std::end(two) && *ib == x);
                     });