优雅的方式来删除包含在另一个向量中的矢量的所有元素？ [英] elegant way to remove all elements of a vector that are contained in another vector?

问题描述

在查看一些代码时，我发现std :: set_difference
：

While looking over some code I found loopy and algorithmically slow implementation of 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);
  }
 }

排序）+ set_difference，但这需要分配新的内存（请参阅我最近的问题可以将设置差异的输出存储在第一个输入吗？为什么它不能完成inplace。）

所以我的解决方案是：

It can be easily replaced with sort(vectors are not sorted) + set_difference, but that requires allocation of new memory(see my recent Q Can output of set difference be stored in first input? why it cant be done "inplace").
So my solution would be something like:

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算法，但我认为它不能做），但没有内存分配和没有增加alg复杂性。

can it be done more elegantly?
elegant is subjective so within scope of this Q is defined as clearer code(ideally something from STL algorithms but I think it cant be done) but with no memory allocation and no increase in alg complexity.

推荐答案

这一个在O（N + M）中做，假设两个数组都排序。
$ b

This one does it in O(N+M), assuming both arrays are sorted.

  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);
                     });

这篇关于优雅的方式来删除包含在另一个向量中的矢量的所有元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！