ChatGPT解决这个技术问题 Extra ChatGPT

从向量中删除项目,而在 C++11 范围“for”循环中?

我有一个 IInventory* 向量,我正在使用 C++11 范围遍历列表,以便对每个列表进行处理。

在用一个做一些事情之后,我可能想将它从列表中删除并删除该对象。我知道我可以随时在指针上调用 delete 来清理它,但是在范围 for 循环中从向量中删除它的正确方法是什么?如果我从列表中删除它,我的循环是否会失效?

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

for (IInventory* index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
}
如果您想变得花哨,可以将 std::remove_if 与“做事”的谓词一起使用,然后如果您希望删除该元素,则返回 true。
为什么你不能只添加一个索引计数器然后使用像 inv.erase(index) 这样的东西有什么原因吗?
@TomJ:那仍然会搞砸迭代。
@BenVoigt i-- 删除后。或者使用整数索引向后迭代。
@BenVoigt 我建议切换到下面的 std::list

P
Peter Mortensen

不,你不能。基于范围的 for 适用于您需要访问容器的每个元素一次的情况。

如果您需要在进行过程中修改容器、多次访问元素或以非线性方式遍历容器,则应该使用普通的 for 循环或其表亲之一。

例如:

auto i = std::begin(inv);

while (i != std::end(inv)) {
    // Do some stuff
    if (blah)
        i = inv.erase(i);
    else
        ++i;
}

在这里不适用擦除删除成语吗?
@Naveen 我决定不尝试这样做,因为显然他需要遍历每个项目,对其进行计算,然后可能将其从容器中删除。 Erase-remove 表示您只是擦除谓词为其返回 true、AFAIU 的元素,并且不将迭代逻辑与谓词混合使用这种方式似乎更好。
@SethCarnegie Erase-remove 使用 lambda 作为谓词优雅地允许这样做(因为这已经是 C++11)
不喜欢这个解决方案,对于大多数容器来说它是 O(N^2)。 remove_if 更好。
这个答案正确的,erase 返回一个新的有效迭代器。它可能效率不高,但可以保证工作。
B
Branko Dimitrijevic

每次从向量中删除一个元素时,您必须假设擦除元素处或之后的迭代器不再有效,因为擦除元素之后的每个元素都被移动了。

基于范围的 for 循环只是使用迭代器的“正常”循环的语法糖,因此上述适用。

话虽如此,您可以简单地:

inv.erase(
    std::remove_if(
        inv.begin(),
        inv.end(),
        [](IInventory* element) -> bool {
            // Do "some stuff", then return true if element should be removed.
            return true;
        }
    ),
    inv.end()
);

因为向量有可能重新分配了保存其元素的内存块” 不,由于调用 erasevector 永远不会重新分配。迭代器无效的原因是被擦除元素之后的每个元素都被移动了。
[&] 的默认捕获将是合适的,以允许他使用局部变量“做一些事情”。
这看起来并不比基于迭代器的循环简单,此外,您必须记住用 .eraseremove_if 括起来,否则不会发生任何事情。
@bobobobo 如果“基于迭代器的循环”是指Seth Carnegie's answer,则平均为 O(n^2)。 std::remove_if 是 O(n)。
@bobobobo 除非您确实需要随机访问。
d
dirkgently

理想情况下,您不应该在迭代向量时修改它。使用擦除删除成语。如果这样做,您可能会遇到一些问题。由于在 vector 中,erase 使从被擦除的元素开始到 end() 的所有迭代器都无效,因此您需要使用以下方法确保迭代器保持有效:

for (MyVector::iterator b = v.begin(); b != v.end();) { 
    if (foo) {
       b = v.erase( b ); // reseat iterator to a valid value post-erase
    else {
       ++b;
    }
}

请注意,您需要按原样进行 b != v.end() 测试。如果您尝试按如下方式对其进行优化:

for (MyVector::iterator b = v.begin(), e = v.end(); b != e;)

您将遇到 UB,因为您的 e 在第一次 erase 调用后无效。


@ildjarn:是的,真的!那是一个错字。
这不是擦除删除成语。没有调用 std::remove,它是 O(N^2) 而不是 O(N)。
@Potatoswatter:当然不是。我试图指出迭代时删除的问题。我猜我的措辞没有通过?
Y
Yexo

在该循环中删除元素是否有严格要求?否则,您可以将要删除的指针设置为 NULL 并再次通过向量以删除所有 NULL 指针。

std::vector<IInventory*> inv;
inv.push_back( new Foo() );
inv.push_back( new Bar() );

for ( IInventory* &index : inv )
{
    // do some stuff
    // ok I decided I need to remove this object from inv...?
    if (do_delete_index)
    {
        delete index;
        index = NULL;
    }
}
std::remove(inv.begin(), inv.end(), NULL);

l
lilbigwill99

抱歉,如果我的 c++ 专业知识妨碍了我的回答,也很抱歉,但是如果您尝试遍历每个项目并进行可能的更改(例如擦除索引),请尝试使用 backwords for 循环。

for(int x=vector.getsize(); x>0; x--){

//do stuff
//erase index x

}

擦除索引 x 时,下一个循环将针对上一次迭代“前面”的项目。我真的希望这对某人有所帮助


只是不要忘记使用 x 访问某个索引时,做 x-1 大声笑
我喜欢这个答案,因为它非常明显发生了什么(不依赖于“这个和那个迭代器在删除时设置为这个和那个”)。正如 lilbigwill99 提到的,您需要使用 (x-1) 进行索引。然而,重新评估到处都是语法和性能的痛苦。我建议将向量初始化为 x=(size-1),比较 x>=0(不仅仅是>),然后“正常”地进行索引。
我确实想为向量类型添加它(根据 OP 的要求),从性能的角度来看,这也是最快的(因为我们从最后删除,所以没有重新组织向量的内存)。
A
Aconcagua

好的,我迟到了,但无论如何:抱歉,到目前为止我读到的内容不正确 - 有可能,你只需要两个迭代器:

std::vector<IInventory*>::iterator current = inv.begin();
for (IInventory* index : inv)
{
    if(/* ... */)
    {
        delete index;
    }
    else
    {
        *current++ = index;
    }
}
inv.erase(current, inv.end());

仅修改迭代器指向的值不会使任何其他迭代器无效,因此我们可以这样做而不必担心。实际上,std::remove_if(至少 gcc 实现)做了一些非常相似的事情(使用经典循环......),只是不删除任何东西,也不擦除。

但是请注意,这不是线程安全的(!) - 但是,这也适用于上述其他一些解决方案......


有没有搞错。这是矫枉过正。
@Kesse 真的吗?这是使用向量可以获得的最有效的算法(无论是基于范围的循环还是经典的迭代器循环):这样,您最多移动向量中的每个元素一次,并且您只对整个向量进行一次迭代。如果您通过 erase 删除每个匹配元素(当然,前提是您删除了多个单个元素),您将移动后续元素并迭代向量多少次?
J
Jayhello

我将举例说明,下面的示例从向量中删除奇数元素:

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};

    //method 1
    for(auto it = vecInt.begin();it != vecInt.end();){
        if(*it % 2){// remove all the odds
            it = vecInt.erase(it);
        } else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 2
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 2
    for(auto it=std::begin(vecInt);it!=std::end(vecInt);){
        if (*it % 2){
            it = vecInt.erase(it);
        }else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 3
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 3
    vecInt.erase(std::remove_if(vecInt.begin(), vecInt.end(),
                 [](const int a){return a % 2;}),
                 vecInt.end());

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

}

下面输出aw:

024
024
024

请记住,方法 erase 将返回传递的迭代器的下一个迭代器。

here 开始,我们可以使用更多的 generate 方法:

template<class Container, class F>
void erase_where(Container& c, F&& f)
{
    c.erase(std::remove_if(c.begin(), c.end(),std::forward<F>(f)),
            c.end());
}

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};
    //method 4
    auto is_odd = [](int x){return x % 2;};
    erase_where(vecInt, is_odd);

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;    
}

请参阅此处了解如何使用 std::remove_ifhttps://en.cppreference.com/w/cpp/algorithm/remove


S
Sooth

与此线程标题相反,我将使用两次通行证:

#include <algorithm>
#include <vector>

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

std::vector<IInventory*> toDelete;

for (IInventory* index : inv)
{
    // Do some stuff
    if (deleteConditionTrue)
    {
        toDelete.push_back(index);
    }
}

for (IInventory* index : toDelete)
{
    inv.erase(std::remove(inv.begin(), inv.end(), index), inv.end());
}

C
Community

一个更优雅的解决方案是切换到 std::list(假设您不需要快速随机访问)。

list<Widget*> widgets ; // create and use this..

然后,您可以在一行中使用 .remove_if 和 C++ 仿函数进行删除:

widgets.remove_if( []( Widget*w ){ return w->isExpired() ; } ) ;

所以在这里我只是在编写一个接受一个参数(Widget*)的函子。返回值是从列表中删除 Widget* 的条件。

我觉得这种语法很可口。我认为我永远不会将 remove_if 用于 std::vectors - 那里有太多的 inv.begin()inv.end() 噪音,你可能最好使用 an integer-index-based delete 或只是一个普通的旧的基于常规迭代器的删除(如下图)。但是无论如何,您不应该真的从 std::vector 的中间删除太多,因此建议在这种频繁删除列表中间的情况下切换到 list

但是请注意,我没有机会在已删除的 Widget* 上调用 delete。为此,它看起来像这样:

widgets.remove_if( []( Widget*w ){
  bool exp = w->isExpired() ;
  if( exp )  delete w ;       // delete the widget if it was expired
  return exp ;                // remove from widgets list if it was expired
} ) ;

您还可以像这样使用基于迭代器的常规循环:

//                                                              NO INCREMENT v
for( list<Widget*>::iterator iter = widgets.begin() ; iter != widgets.end() ; )
{
  if( (*iter)->isExpired() )
  {
    delete( *iter ) ;
    iter = widgets.erase( iter ) ; // _advances_ iter, so this loop is not infinite
  }
  else
    ++iter ;
}

如果您不喜欢 for( list<Widget*>::iterator iter = widgets.begin() ; ... 的长度,可以使用

for( auto iter = widgets.begin() ; ...

我认为您不了解 std::vector 上的 remove_if 是如何实际工作的,以及它如何将复杂性保持在 O(N)。
那没关系。从 std::vector 的中间删除总是会在您删除的元素之后滑动每个元素,使 std::list 成为更好的选择。
不,它不会“将每个元素向上滑动一个”。 remove_if 会将每个元素向上滑动释放的空格数。当您考虑缓存使用情况时,std::vector 上的 remove_if 可能优于从 std::list 中删除。并保留 O(1) 随机访问。
然后你有一个很好的答案来寻找一个问题。这个问题讨论了迭代列表,这对于两个容器都是 O(N) 。并删除 O(N) 元素,这对于两个容器来说也是 O(N)。
不需要预先标记;完全有可能一次性完成。您只需要跟踪“要检查的下一个元素”和“要填充的下一个插槽”。将其视为构建列表的副本,根据谓词进行过滤。如果谓词返回 true,则跳过该元素,否则复制它。但是列表副本是就地制作的,并且使用交换/移动而不是复制。
a
ajpieri

我想我会做以下...

for (auto itr = inv.begin(); itr != inv.end();)
{
   // Do some stuff
   if (OK, I decided I need to remove this object from 'inv')
      itr = inv.erase(itr);
   else
      ++itr;
}

s
suraj kumar

您不能在循环迭代期间删除迭代器,因为迭代器计数不匹配,并且在某些迭代之后您将拥有无效的迭代器。

解决方案:1)获取原始向量的副本 2)使用此副本迭代迭代器 2)做一些事情并将其从原始向量中删除。

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

std::vector<IInventory*> copyinv = inv;
iteratorCout = 0;
for (IInventory* index : copyinv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
    inv.erase(inv.begin() + iteratorCout);
    iteratorCout++;
}  

S
Sergiy Kanilo

一个接一个地擦除元素很容易导致 N^2 性能。最好标记应该擦除的元素并在循环后立即擦除它们。如果我可以假定您的向量中的无效元素为 nullptr,那么

std::vector<IInventory*> inv;
// ... push some elements to inv
for (IInventory*& index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
    {
      delete index;
      index =nullptr;
    }
}
inv.erase( std::remove( begin( inv ), end( inv ), nullptr ), end( inv ) ); 

应该管用。

如果您的“做一些事情”没有更改向量的元素并且仅用于决定删除或保留元素,您可以将其转换为 lambda(如某人之前的帖子中所建议的那样)并使用

inv.erase( std::remove_if( begin( inv ), end( inv ), []( Inventory* i )
  {
    // DO some stuff
    return OK, I decided I need to remove this object from 'inv'...
  } ), end( inv ) );