你可以从std::list中删除元素，同时遍历它吗?

我有这样的代码:

for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
bool isActive = (*i)->update();
//if (!isActive)
//  items.remove(*i);
//else
other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);

我想在更新后立即删除不活跃的项目，以避免再次浏览列表。但是如果我添加注释掉的行，当我到达i++时，我会得到一个错误:“列表迭代器不可递增”。我尝试了一些在for语句中不增加的替代方法，但我不能让任何东西工作。

什么是最好的方法来删除项目，因为你正在走std::列表?

278639 次浏览
小开
最佳答案

你必须先增加迭代器(使用i++)，然后删除前一个元素(例如，通过使用i++的返回值)。你可以像这样将代码更改为while循环:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
bool isActive = (*i)->update();
if (!isActive)
{
items.erase(i++);  // alternatively, i = items.erase(i);
}
else
{
other_code_involving(*i);
++i;
}
}
小开

你想做的是:

i= items.erase(i);

这将正确地更新迭代器，使其指向您删除的迭代器之后的位置。

小开

使用std::remove_if算法。

< p > 编辑: < br > 处理集合的方法应该是:

  1. 准备收集。
  2. 收集过程。

如果你不把这些步骤混在一起，生活会更容易。

  1. std::remove_if。或list::remove_if(如果你知道你使用的是list而不是TCollection)
  2. std::for_each
小开

删除只会使指向被删除元素的迭代器失效。

所以在这种情况下，删除*i后，i是无效的，你不能对它做增量操作。

你能做的是首先保存要删除的元素的迭代器，然后增加迭代器，然后删除保存的迭代器。

小开

你需要结合Kristo的回答和MSN的回答:

// Note: Using the pre-increment operator is preferred for iterators because
//       there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
//       along the way you can safely save end once; otherwise get it at the
//       top of each loop.


std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end  = items.end();


while (iter != end)
{
item * pItem = *iter;


if (pItem->update() == true)
{
other_code_involving(pItem);
++iter;
}
else
{
// BTW, who is deleting pItem, a.k.a. (*iter)?
iter = items.erase(iter);
}
}

当然，最高效的和SuperCool®STL精明的事情会是这样的:

// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
if (m_needsUpdates == true)
{
m_needsUpdates = other_code_involving(this);
}


return (m_needsUpdates);
}


// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));
小开

Kristo回答的循环版本的替代方案。

你会损失一些效率，你在删除的时候会向后再向前，但作为交换，你可以在循环范围内声明迭代器，代码看起来更干净一些。选择什么取决于当前的优先事项。

我知道这个答案完全过时了……

typedef std::list<item*>::iterator item_iterator;


for(item_iterator i = items.begin(); i != items.end(); ++i)
{
bool isActive = (*i)->update();


if (!isActive)
{
items.erase(i--);
}
else
{
other_code_involving(*i);
}
}
小开

我认为你有一个错误，我这样编码:

for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
itAudioChannel != audioChannels.end(); )
{
CAudioChannel *audioChannel = *itAudioChannel;
std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
itAudioChannel++;


if (audioChannel->destroyMe)
{
audioChannels.erase(itCurrentAudioChannel);
delete audioChannel;
continue;
}
audioChannel->Mix(outBuffer, numSamples);
}
小开

下面是一个使用for循环的示例，该循环迭代列表，并在遍历列表期间删除项的情况下递增或重新验证迭代器。

for(auto i = items.begin(); i != items.end();)
{
if(bool isActive = (*i)->update())
{
other_code_involving(*i);
++i;


}
else
{
i = items.erase(i);


}


}


items.remove_if(CheckItemNotActive);
小开

如果你把std::list看作一个队列，那么你可以对你想保留的所有项进行出队列和入队列，但只能对你想删除的项进行出队列(而不是入队列)。下面是一个例子，我想从包含数字1-10的列表中删除5…

std::list<int> myList;


int size = myList.size(); // The size needs to be saved to iterate through the whole thing


for (int i = 0; i < size; ++i)
{
int val = myList.back()
myList.pop_back() // dequeue
if (val != 5)
{
myList.push_front(val) // enqueue if not 5
}
}

myList现在只有数字1-4和6-10。

小开

你可以写

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
bool isActive = (*i)->update();
if (!isActive) {
i = items.erase(i);
} else {
other_code_involving(*i);
i++;
}
}

你可以用std::list::remove_if写相同的代码，它更简洁，更显式

items.remove_if([] (item*i) {
bool isActive = (*i)->update();
if (!isActive)
return true;


other_code_involving(*i);
return false;
});

当items是一个向量而不是一个列表时，应该使用std::vector::erase std::remove_if习语，以保持复杂度在O(n) -或者如果您编写通用代码，而items可能是一个容器，没有有效的方法来删除单个项(如vector)

items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
bool isActive = (*i)->update();
if (!isActive)
return true;


other_code_involving(*i);
return false;
}));
小开

我总结了一下，下面是这三种方法的例子:

1. 使用while循环

list<int> lst{4, 1, 2, 3, 5};


auto it = lst.begin();
while (it != lst.end()){
if((*it % 2) == 1){
it = lst.erase(it);// erase and go to next
} else{
++it;  // go to next
}
}


for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

2. 在list中使用remove_if成员函数

list<int> lst{4, 1, 2, 3, 5};


lst.remove_if([](int a){return a % 2 == 1;});


for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

3.使用std::remove_if函数结合erase成员函数:

list<int> lst{4, 1, 2, 3, 5};


lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
return a % 2 == 1;
}), lst.end());


for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2

4. 使用for循环时，应注意更新迭代器:

list<int> lst{4, 1, 2, 3, 5};


for(auto it = lst.begin(); it != lst.end();++it){
if ((*it % 2) == 1){
it = lst.erase(it);  erase and go to next(erase will return the next iterator)
--it;  // as it will be add again in for, so we go back one step
}
}


for(auto it:lst)cout<<it<<" ";
cout<<endl;  //4 2
小开

向后迭代避免了在要遍历的剩余元素上擦除一个元素的效果:

typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
--it;
bool remove = <determine whether to remove>
if ( remove ) {
items.erase( it );
}
}

PS:参见这，例如，关于向后迭代。

PS2:我没有彻底测试它是否处理好擦除元素在结束。

小开

做while循环，它灵活，快速，易于读写。

auto textRegion = m_pdfTextRegions.begin();
while(textRegion != m_pdfTextRegions.end())
{
if ((*textRegion)->glyphs.empty())
{
m_pdfTextRegions.erase(textRegion);
textRegion = m_pdfTextRegions.begin();
}
else
textRegion++;
}
小开

我想分享一下我的方法。此方法还允许在迭代期间将元素插入到列表的后面

#include <iostream>
#include <list>


int main(int argc, char **argv) {
std::list<int> d;
for (int i = 0; i < 12; ++i) {
d.push_back(i);
}


auto it = d.begin();
int nelem = d.size(); // number of current elements
for (int ielem = 0; ielem < nelem; ++ielem) {
auto &i = *it;
if (i % 2 == 0) {
it = d.erase(it);
} else {
if (i % 3 == 0) {
d.push_back(3*i);
}
++it;
}
}


for (auto i : d) {
std::cout << i << ", ";
}
std::cout << std::endl;
// result should be: 1, 3, 5, 7, 9, 11, 9, 27,
return 0;
}

提交答案