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

Question

我有两个向量

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

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

的解决方法

编辑：（更多背景）

这是我当前的代码。我希望我可以避免移动到 list 并返回 vector

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

如果我可以直接从 vector 中删除，则可以在没有列表的情况下进行简化。

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

这似乎对我来说是对的：

#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 2

也许这适合您的情况：

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

Answer 3

您应该可以使用您的第二个代码段并稍加修改 - 与其向前迭代 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);
  }
}

Live demo

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

How to remove elements from vector given another vector of iterators

c++

c++11

stdvector