迭代时从STL集中删除元素

我需要通过一个集合并删除满足预定义条件的元素。

这是我写的testing代码：

#include <set> #include <algorithm> void printElement(int value) { std::cout << value << " "; } int main() { int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; std::set<int> numbers(initNum, initNum + 10); // print '0 1 2 3 4 5 6 7 8 9' std::for_each(numbers.begin(), numbers.end(), printElement); std::set<int>::iterator it = numbers.begin(); // iterate through the set and erase all even numbers for (; it != numbers.end(); ++it) { int n = *it; if (n % 2 == 0) { // wouldn't invalidate the iterator? numbers.erase(it); } } // print '1 3 5 7 9' std::for_each(numbers.begin(), numbers.end(), printElement); return 0; } 

起初，我认为在迭代过程中擦除集合中的元素会使迭代器失效，并且for循环中的增量将具有未定义的行为。 尽pipe如此，我执行了这个testing代码，一切顺利，我无法解释为什么。

我的问题：这是为std集定义的行为还是这个实现特定？ 顺便说一句，我在ubuntu 10.04（32位版本）上使用gcc 4.3.3。

谢谢！

build议解决scheme：

这是迭代和擦除集合中元素的正确方法吗？

 while(it != numbers.end()) { int n = *it; if (n % 2 == 0) { // post-increment operator returns a copy, then increment numbers.erase(it++); } else { // pre-increment operator increments, then return ++it; } } 

编辑：预置解决scheme

我来到了一个似乎对我更优雅的解决scheme，即使它完全一样。

 while(it != numbers.end()) { // copy the current iterator then increment it std::set<int>::iterator current = it++; int n = *current; if (n % 2 == 0) { // don't invalidate iterator it, because it is already // pointing to the next element numbers.erase(current); } } 

如果在这个时间内有几个testing条件，它们中的每一个都必须递增迭代器。 我更喜欢这个代码，因为迭代器只在一个地方递增，使得代码更容易出错，更易读。

Answer 1

这是依赖于实现的：

标准23.1.2.8：

插入成员不应影响迭代器和对容器的引用的有效性，并且擦除成员只应使迭代器和对被擦除元素的引用无效。

也许你可以尝试这个 – 这是标准符合：

 for (it = numbers.begin(); it != numbers.end(); ) { if (*it % 2 == 0) { numbers.erase(it++); } else { ++it; } } 

请注意，它++是后缀，因此它通过旧的位置擦除，但由于操作员首先跳到一个较新的位置。

2015.10.27更新： C ++ 11已经解决了这个缺陷。 iterator erase (const_iterator position); 返回一个迭代器到最后一个元素被移除的元素（或者set :: end，如果最后一个元素被移除）。 所以C ++ 11风格是：

 for (it = numbers.begin(); it != numbers.end(); ) { if (*it % 2 == 0) { it = numbers.erase(it); } else { ++it; } } 

Answer 2

如果你通过valgrind运行你的程序，你会看到一堆读取错误。 换句话说，是的，迭代器被取消了，但是在你的例子中你很幸运（或者真的很不幸，因为你没有看到未定义行为的负面影响）。 对此的一个解决scheme是创build一个临时迭代器，增加temp，删除目标迭代器，然后将目标设置为temp。 例如，重新编写你的循环如下：

 std::set<int>::iterator it = numbers.begin(); std::set<int>::iterator tmp; // iterate through the set and erase all even numbers for ( ; it != numbers.end(); ) { int n = *it; if (n % 2 == 0) { tmp = it; ++tmp; numbers.erase(it); it = tmp; } else { ++it; } } 

Answer 3

你误解了“未定义行为”的含义。 未定义的行为并不意味着“如果你这样做，你的程序将崩溃或产生意想不到的结果。” 这意味着“如果你这样做，你的程序可能会崩溃或产生意想不到的结果”，或者做任何事情，取决于你的编译器，操作系统，月相等等。

如果一些东西没有崩溃而执行，并且performance得如你所期望的那样，这并不能certificate它不是未定义的行为。 它certificate的是，它的行为恰好是在该特定操作系统上编译该特定编译器后所观察到的特定运行。

从集合中删除一个元素将使迭代器无效到被擦除的元素。 使用失效的迭代器是未定义的行为。 恰好如此，所观察到的行为就是你在这个特定情况下的意图。 这并不意味着代码是正确的。

Answer 4

只是为了警告，在deque容器的情况下，所有检查与number.end（）迭代器相等的解决scheme可能会在gcc 4.8.4上失败。 也就是说，擦除deque的元素通常使指向numbers.end的指针无效（）：

 #include <iostream> #include <deque> using namespace std; int main() { deque<int> numbers; numbers.push_back(0); numbers.push_back(1); numbers.push_back(2); numbers.push_back(3); //numbers.push_back(4); deque<int>::iterator it_end = numbers.end(); for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) { if (*it % 2 == 0) { cout << "Erasing element: " << *it << "\n"; numbers.erase(it++); if (it_end == numbers.end()) { cout << "it_end is still pointing to numbers.end()\n"; } else { cout << "it_end is not anymore pointing to numbers.end()\n"; } } else { cout << "Skipping element: " << *it << "\n"; ++it; } } } 

输出：

 Erasing element: 0 it_end is still pointing to numbers.end() Skipping element: 1 Erasing element: 2 it_end is not anymore pointing to numbers.end() 

请注意，虽然在这种特殊情况下deque转换是正确的，但是一直沿用终止指针。 随着大小不同的错误更为明显：

 int main() { deque<int> numbers; numbers.push_back(0); numbers.push_back(1); numbers.push_back(2); numbers.push_back(3); numbers.push_back(4); deque<int>::iterator it_end = numbers.end(); for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) { if (*it % 2 == 0) { cout << "Erasing element: " << *it << "\n"; numbers.erase(it++); if (it_end == numbers.end()) { cout << "it_end is still pointing to numbers.end()\n"; } else { cout << "it_end is not anymore pointing to numbers.end()\n"; } } else { cout << "Skipping element: " << *it << "\n"; ++it; } } } 

输出：

 Erasing element: 0 it_end is still pointing to numbers.end() Skipping element: 1 Erasing element: 2 it_end is still pointing to numbers.end() Skipping element: 3 Erasing element: 4 it_end is not anymore pointing to numbers.end() Erasing element: 0 it_end is not anymore pointing to numbers.end() Erasing element: 0 it_end is not anymore pointing to numbers.end() ... Segmentation fault (core dumped) 

这是解决这个问题的方法之一：

 #include <iostream> #include <deque> using namespace std; int main() { deque<int> numbers; bool done_iterating = false; numbers.push_back(0); numbers.push_back(1); numbers.push_back(2); numbers.push_back(3); numbers.push_back(4); if (!numbers.empty()) { deque<int>::iterator it = numbers.begin(); while (!done_iterating) { if (it + 1 == numbers.end()) { done_iterating = true; } if (*it % 2 == 0) { cout << "Erasing element: " << *it << "\n"; numbers.erase(it++); } else { cout << "Skipping element: " << *it << "\n"; ++it; } } } } 

Answer 5

这种行为是特定于实现的。 为了保证迭代器的正确性，你应该使用“it = numbers.erase（it）;” 语句是否需要在其他情况下删除元素并简单地使用迭代器。