如何从给定另一个迭代器向量的向量中删除元素

Question

我有两个向量

vector<int> vint;
vector<vector<int>::iterator> viter;

删除vint中迭代器位于viter中的所有元素的最佳方法是什么。目前，我暂时转向list

编辑：（更多背景）

这是我当前的代码。我希望我能避免移动到列表并返回到矢量

void foo(std::vector<Blah>& bvec)
{
  std::list<Blah> blist;
  std::move(bvec.begin(), bvec.end(), std::back_inserter(blist));
  bvec.clear();
  std::vector<std::list<Blah>::iterator> selectedElements;
  { 
     //Critical section which holds a mutex. Should be as fast as possible
     for(auto it = blist.begin(), it_end= blist.end(); it != it_end; ++it)
     {
        if(shouldElementBeRemoved(*it))
           selectedElements.push_back(it);
     }
  }
  for(auto& it: selectedElements)
  {
     if(shouldElementReallyBeRemoved(*it))
        blist.erase(it);
  }
  std::move(blist.begin(), blist.end(), std::back_inserter(bvec));
}

如果我可以直接从向量中删除，就可以在没有列表的情况下简化。

void foo(std::vector<Blah>& bvec)
{
  std::vector<std::vector<Blah>::iterator> selectedElements;
  { 
     //Critical section which holds a mutex. Should be as fast as possible
     for(auto it = bvec.begin(), it_end= bvec.end(); it != it_end; ++it)
     {
        if(shouldElementBeRemoved(*it))
           selectedElements.push_back(it);
     }
  }
  for(auto& it: selectedElements)
  {
     if(shouldElementReallyBeRemoved(*it))
        // bvect.erase(it);              //Not safe!
  }
}

Answer 1

您应该能够使用您的第二个代码段，只需进行一个小的修改——而不是在selectedElements上向前迭代，而是向后迭代。那么对bvec.erase的调用将永远不会使保留在selectedElements中的任何迭代器无效。

void foo(std::vector<Blah>& bvec)
{
  std::vector<std::vector<Blah>::iterator> selectedElements;
  selectedElements.reserve(bvec.size());  // avoid growing the vector while you hold a mutex lock
  { 
     //Critical section which holds a mutex. Should be as fast as possible
     for(auto it = bvec.begin(), it_end= bvec.end(); it != it_end; ++it)
     {
        if(shouldElementBeRemoved(*it))
           selectedElements.push_back(it);
     }
  }
  for(auto first = selectedElements.rbegin(),
           last  = selectedElements.rend();
           first != last;
           ++first)
  {
      if(shouldElementReallyBeRemoved(**first)) 
        bvec.erase(*first);
  }
}

实时演示

Answer 2

这似乎对我来说是正确的：

#include <algorithm>
  for (auto current = vint.end();
       current >= vint.begin();) {
    current--;
    if (any_of(
          viter.begin(),
          viter.end(),
          [current](std::vector<int>::iterator it) {
            return current == it;
          })) {
      vint.erase(current);
    }
  }

使用any_of可以使迭代器向量不排序。

Answer 3

也许这适合您的情况：

struct Blah
{
    bool deleted = false; // add a special field
    // other data
};
void foo(std::vector<Blah>& bvec)
{
    {
        //Critical section which holds a mutex. Should be as fast as possible
        // mark them quickly
        for(auto& b: bvec)
            if(shouldElementBeRemoved(b))
                b.deleted = true;
    }
    // remove them slowly
    for(auto i = bvec.begin(); i != bvec.end();)
    {
        if(i->deleted && shouldElementReallyBeRemoved(*i))
            i = bvec.erase(i);
        else
        {
            i->deleted = false;
            ++i;
        }
    }
}