c – 优雅的方式去除另一个向量中包含的向量的所有元素？

发布时间：2020-12-16 03:16:57 所属栏目：百科来源：网络整理

导读：在查找一些代码时,我发现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,

在查找一些代码时,我发现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,但这需要分配新的内存(请参阅我最近的Q Can output of set difference be stored in first input?为什么它不能完成“inplace”).
所以我的解决方案将是：

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的范围内,Q被定义为更清晰的代码(理想的是STL算法的东西,但是我认为它不能完成),但没有内存分配,并且alg复杂度没有增加.

解决方法

假设这两个数组都被排序,这个在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);
                     });

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!