当我正在迭代std :: list时，我能否从中删除元素？

Question

当我在迭代std::list时，我能够从中删除元素吗？例如：

std::list<int> lst;
//....
for (std::list<int> itr = lst.begin(); itr != lst.end(); itr++)
{
    if (*itr > 10)
         lst.remove(*itr);
}

为什么？

And why?

- Siarhei Fedartsou

---

可能是从STL列表中删除项目的重复问题。 - sth

可能是在遍历std :: list时删除元素吗？的重复问题。 - AShelly

Answer 1

正确的代码如下:

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); /*nothing*/)
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

从列表中删除一个项时，如果迭代器指向要删除的项，则可能会使迭代器失效。因此，您需要使用erase进行删除（它返回指向下一项的有效迭代器）。

更好的方法是使用std::remove_if：

bool greater_than_10(int x)
{
    return x > 10;
}

lst.remove_if(greater_than_10);

如果您的编译器支持lambda表达式，您可以将其缩短：

lst.remove_if([](int x){ return x > 10; });

(我的编译器太旧了，无法测试此代码；lambda函数来自@John Dibling的回答。)

---

事实上，从列表中删除元素仅会使指向被删除项的迭代器失效，仅仅如此。但要注意，其他STL容器没有这种属性。

---

简而言之：通常情况下，在通过列表进行迭代时不应该删除其中的项，因为删除可能会使迭代器失效（程序可能会崩溃）。但是，如果你完全确定你要删除的项不是任何你在删除时使用的迭代器引用的值，那么你可以进行删除操作。

请注意，对于其他STL容器（例如向量），限制会更严格：从容器中删除项不仅会使指向已删除项的迭代器失效，还可能使其他迭代器失效！因此，在遍历这些容器时进行删除操作更加棘手。

- Vlad

---

哈。当两个 Stack Overflow 的人发布几乎相同的示例代码时，这一定是一个好主意。 - aschepler

哦，我举的例子不好。我想使用remove方法（如果满足某个条件，我想删除所有具有特定值的项目）。 - Siarhei Fedartsou

@miksayer：你不能这样做，因为删除元素可能会使迭代器失效，导致下一次迭代失败。 - Vlad

删除-移除惯用语适用于向量，而不是列表！ - fredoverflow

我添加了一个 remove_if 的示例代码，希望你不介意。此外，我将 itr 的类型从 std::list 更正为 std::list<int>::iterator。 - fredoverflow

Answer 2

不行。示例代码使 itr 无效，导致未定义的行为。但是以下代码可以正常工作：

for (std::list<int>::iterator itr = lst.begin(); itr != lst.end(); )
{
    if (*itr > 10)
        itr = lst.erase(itr);
    else
        ++itr;
}

- aschepler

---

对迭代器进行前置递增是一个好主意，我已经改变了我的代码来匹配这个。现在示例代码完全一样 :) - Vlad

Answer 3

不行，你不能这样做。 但你可以（也应该）使用std::remove_if和一个表明“大于10”的函数对象，就像这样：

#include <list>
#include <algorithm>


int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), std::bind2nd(std::greater<int>(), 10)), lst.end());
}

另一种更通用的方法是编写自己的自定义函数对象(functor)。下面是一个名为is_a_match的函数对象，如果被检查的值大于10，则返回true。您可以重新定义operator()以返回true，以对应于在您的情况下“匹配”的含义：

#include <list>
#include <algorithm>
#include <functional>

struct is_a_match : public std::unary_function<int, bool>
{
    is_a_match(int val) : val_(val) {};
    bool operator()(int victim) const { return victim > val_; }
private:
    int val_;
};

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), is_a_match(10) ));
}

如果你使用符合C++0x标准的编译器，你也可以使用lambda表达式，在许多情况下，这使得摆脱函数对象并编写更具表现力的代码成为可能。

#include <list>
#include <algorithm>

int main()
{
    std::list<int> lst;
    lst.push_back(1);
    lst.push_back(12);
    lst.push_back(1);
    //....
    lst.erase(std::remove_if(lst.begin(), lst.end(), [](int v) {return v > 10;}));
}

- John Dibling

---

实际上，list有自己的remove_if成员函数：lst.remove_if(std::bind2nd(std::greater<int>(), 10)); - Fred Larson

擦除-删除惯用语在列表上真的是一个糟糕的想法。它将单个元素的移除速度从O(1)降低到了O(n)。不要这样做。小心容器无关代码的幻觉。 - fredoverflow

@Fred：嗯，过早优化。 - John Dibling

@John：你真的认为O(1)与O(n)之间的过早优化很重要吗？你一定在开玩笑。我们使用erase-remove操作对*向量(vectors)*进行处理的原因是将时间复杂度从O(n^2)降至O(n)。在速度方面，选择高效算法比选择C ++而不是“更慢”的语言更加重要，这是数量级上的差别。 - fredoverflow

如果你在程序启动时创建一个包含10个整数的列表，那么这并不重要。 - John Dibling

Answer 4

我认为你可以这样做，但是在删除元素后，你必须重新分配迭代器，这可以通过使用erase方法而不是remove来完成。

否则，这将是不安全的，不应该这样做。

- Jack

Answer 5

请查看 http://www.cppreference.com/wiki/iterator/start 获取迭代器的描述。

几个注意事项：

• 您应该使用前缀递增运算符（++itr）而不是后缀递增运算符（itr++）
• 作废取决于迭代器及其关联集合的具体实现。

- TreDubZedd