你能在遍历std::list时删除元素吗？

Question

我有这样的代码：

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++ 时会出现错误："List iterator not incrementable"。我尝试了一些未在 for 语句中增加计数器的替代方法，但是什么都没用。

如何在遍历 std::list 时删除项目的最佳方法？

- AShelly

---

我还没有看到基于反向迭代的解决方案。我发布了这样一个。 - sancho.s ReinstateMonicaCellio

Answer 1

您需要先增加迭代器（使用 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;
    }
}

- Kristo

---

实际上，这并不能保证可行。使用“erase(i++)”时，我们只知道预增值被传递给了erase()函数，在分号之前i被增加了，但不一定在调用erase()函数之前增加。"iterator prev = i++; erase(prev);" 是可行的，使用返回值也是可行的。 - James Curran

不，詹姆斯，在调用 erase 之前我已经增加了 i 的值，并将先前的值传递给函数。函数的参数必须在调用函数之前完全求值。 - Brian Neal

@ James Curran：这不正确。在调用函数之前，所有参数都将被完全评估。 - Martin York

马丁·约克是正确的。 在调用函数之前，所有函数调用参数都将被完全评估，没有例外。 这就是函数工作的方式。 而这与您的 foo.b(i++).c(i++) 示例无关（在任何情况下都是未定义的）。 - jalf

替代使用 i = items.erase(i) 更加安全，因为在列表中等同，但如果有人将容器更改为向量仍然可以正常工作。 对于向量，erase()会将所有内容移到左侧以填充空隙。 如果您尝试使用在删除迭代器后递增迭代器的代码删除最后一个项目，则结尾会向左移动，迭代器会向右移动-- 超过 末尾。 然后你就会崩溃。 - Eric Seppanen

Answer 2

您想要做的是：

i= items.erase(i);

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

- MSN

---

请注意，不能将该代码简单粗暴地插入到您的for循环中。否则每次删除一个元素后，您都会跳过一个元素。 - Michael Kristofik

他可不可以在自己的代码后面加上 i--，以避免跳过？ - enthusiasticgeek

@enthusiasticgeek，如果 i==items.begin() 会发生什么？ - MSN

@MSN 在执行 i-- 前或许需要添加一个条件。如果检查一下 !items.empty() 呢？ - enthusiasticgeek

@enthusiasticgeek，那你应该只需执行i= items.erase(i);。这是规范的形式，已经处理了所有这些细节。 - MSN

Michael指出了一个巨大的“陷阱”，我刚刚也遇到了同样的问题。我发现避免这个问题最简单的方法是将for()循环分解成while()循环，并小心地进行递增。 - Anne Quinn

Answer 3

您需要结合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);
    }
}

当然，最高效和超酷的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)));

- Mike

---

我确实考虑过你的SuperCool方法，但我犹豫的是调用remove_if并没有清楚地表明目标是处理项目，而不是将它们从活动列表中删除。（这些项目并没有被删除，因为它们只是变得不活跃了，而不是不需要了） - AShelly

我想你是对的。一方面，我倾向于建议更改“update”的名称以消除其模糊性，但事实上，这段代码配备了功能对象，但它绝不是不清晰的。 - Mike

公正的评论，要么修复while循环以使用end，要么删除未使用的定义。 - Mike

附注：std::not1和std::mem_fun已被弃用。 - luizfls

Answer 4

我总结了一下，这里是三种方法和示例：

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 

- Jayhello

---

在C++20中，您可以只使用std::erase_if(lst, pred)。它基本上与选项2和3相同，但更短，并适用于任何类型的容器。 - sklott

Answer 5

使用std::remove_if算法。

编辑：
处理集合应该如下：

1. 准备集合。
2. 处理集合。

如果不混淆这些步骤，生活会更轻松。

1. std::remove_if或list::remove_if（如果您知道自己正在使用列表而不是TCollection）
2. std::for_each

- Mykola Golubyev

---

std::list有一个remove_if成员函数，比remove_if算法更高效（而且不需要“remove-erase”习惯用语）。 - Brian Neal

@brianneal 这取决于您是否可以访问C++20功能，否则C++17仅提供std::remove_if https://en.cppreference.com/w/cpp/algorithm/remove - Antonio

@Antonio，我在谈论std::list的remove_if 成员函数。我已经离开C++很长时间了，但当我写下我的评论（超过11年前！）时，那还是一个东西，我相信现在它仍然存在。http://www.cplusplus.com/reference/list/list/remove_if/ - Brian Neal

@BrianNeal 是的，我不知道我误解了你的评论，实际上它非常清楚。 - Antonio

Answer 6

这是 Kristo 回答的替代 for 循环版本。

你会失去一些效率，因为在删除时需要向后再向前移动，但作为额外的迭代器增量，你可以将迭代器声明在循环范围内，使代码看起来更加清晰。选择取决于当前的优先级。

我知道这个回答已经过时了...

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

- Rafael Gago

---

这也是我使用的方法。但是，如果要删除的元素是容器中的第一个元素，我不确定它是否保证可行。对于我来说，它可以工作，但我不确定它是否跨平台可移植。 - trololo

我没有执行“-1”，但是列表迭代器无法递减？至少我从Visual Studio 2008得到了断言。 - milesma

只要将链表实现为一个带有头/存根节点的循环双向链表（用作end() rbegin()，当为空时也用作begin()和rend()），这将起作用。我记不清我在哪个平台上使用过它，但是对于std::list来说，上述实现是最常见的实现，所以它对我也有效。但无论如何，几乎可以肯定这是利用了一些未定义的（由C++标准）行为，因此最好不要使用它。 - Rafael Gago

关于“迭代器无法递减”的问题，这是因为erase方法需要一个“随机访问迭代器”。一些集合实现提供了“仅向前迭代器”，这会导致断言错误。 - Jesse Chisholm

@Jesse Chisholm 这个问题是关于 std::list 的，而不是任意容器。std::list 提供了 erase 和双向迭代器。 - Rafael Gago

Answer 7

以下是使用 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);

- David Cormack

Answer 8

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

因此，在这种情况下，删除 *i 后，i 将失效，您不能对其进行增量操作。

您可以做的是先保存要删除的元素的迭代器，然后增加迭代器，然后删除已保存的迭代器。

- Alien01

---

使用后加法运算符更加优雅。 - Brian Neal

Answer 9

反向迭代可以避免擦除元素对其余需要遍历的元素产生影响：

最初的回答

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：我没有彻底测试它是否能够很好地处理删除末尾的元素。

最初的回答

- sancho.s ReinstateMonicaCellio

---

关于列表的“避免删除元素对其余元素产生影响”的问题，可能是可以的。但对于向量可能不行。这并非对任意集合都有保证。例如，映射可能会决定重新平衡自身。 - Jesse Chisholm

Answer 10

如果你将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的数字。

- Alex Bagg

---

有趣的方法，但我担心它可能会很慢。 - sg7