c++ - std::deque 错误？

Question

我正在尝试使用循环和迭代器从双端队列中删除一个元素。我正在关注 online examples但看到一个错误。

我使用的是 g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-9)。

代码如下:

#include <iostream>
#include <deque>

using namespace std;

// Display the contents of a queue
void disp_deque(deque<int>& deque) {
  cout << "deque contains: ";
  for (auto itr = deque.begin(); itr!=deque.end(); ++itr)
    cout << *itr << ' ';
  cout << '\n';
}

int main(int argc, char** argv) {
  deque<int> mydeque;

  // Put 10 integers in the deque.
  for (int i=1; i<=10; i++) mydeque.push_back(i);
  disp_deque(mydeque);

  auto it = mydeque.begin(); 
  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    // Delete even numbered values.
    if ((*it % 2) == 0) {
      cout << "Deleting " << *it << '\n';
      mydeque.erase(it++);
      disp_deque(mydeque);
    } else ++it;
  }
}

这非常简单 - 创建一个包含 10 个元素的列表并删除偶数元素。

注意以下几点(绒毛除外):

if ((*it % 2) == 0) {
  mydeque.erase(it++);
} else it++;

这是使用迭代器删除的推荐方法，这样您的迭代器就不会像上面链接中提到的那样失效。

但是，当我运行它时，我得到以下信息:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
deque contains: 1 3 5 7 9 
Checking 10,Deleting 10
deque contains: 1 3 5 7 
Checking 0,Deleting 0
deque contains: 1 3 5 
Checking 0,Deleting 0
deque contains: 1 3 
Checking 0,Deleting 0
deque contains: 1 
Checking 0,Deleting 0
deque contains: 
Checking 0,Deleting 0
Segmentation fault (core dumped)

翻了一下，貌似还不错，直到把8删掉了，其实9号是直接跳过了，根本没检查过!我期望应该发生的是:

$ ./test
deque contains: 1 2 3 4 5 6 7 8 9 10 
Checking 1,Checking 2,Deleting 2
deque contains: 1 3 4 5 6 7 8 9 10 
Checking 3,Checking 4,Deleting 4
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
deque contains: 1 3 5 7 9 10 
Checking 9,Checking 10,Deleting 10
deque contains: 1 3 5 7 9 

事实上，这正是我将代码更改为:

if ((*it % 2) == 0) {
  it=mydeque.erase(it);
} else it++;

那么，为什么一种方法有效，而另一种方法无效呢？谁能解释一下？

即使我创建了一个临时迭代器来删除，我也会看到完全相同的问题输出:

  while (it!=mydeque.end()) {
    cout << "Checking " << *it << ',';
    auto tmp_it = it++;
    // Delete even numbered values.
    if ((*tmp_it % 2) == 0) {
      cout << "Deleting " << *tmp_it << '\n';
      cout << "IT before delete: " << *it << '\n';
      mydeque.erase(tmp_it);
      cout << "IT after delete: " << *it << '\n';
      disp_deque(mydeque);
    } 
  }

这里我将它的拷贝存储在 tmp_it 中，然后递增它。我添加了更多调试语句并看到了一些非常奇怪的东西:

...
deque contains: 1 3 5 6 7 8 9 10 
Checking 5,Checking 6,Deleting 6
IT before delete: 7
IT after delete: 7
deque contains: 1 3 5 7 8 9 10 
Checking 7,Checking 8,Deleting 8
IT before delete: 9
IT after delete: 10
deque contains: 1 3 5 7 9 10 
Checking 10,Deleting 10
IT before delete: 10
IT after delete: 10
...

然而，删除元素 8 使其指向元素 10，跳过 9!在以前的删除中，它指向前一个元素(例如，当删除 6 时，它指向删除前后的 7)。

我查看了 deque 的实现并在“迭代器有效性”下查看以下内容(强调我的):

Iterator validity If the erasure operation includes the last element in the sequence, the end iterator and the iterators, pointers and references referring to the erased elements are invalidated. If the erasure includes the first element but not the last, only those referring to the erased elements are invalidated. If it happens anywhere else in the deque, all iterators, pointers and references related to the container are invalidated.

那么这是否意味着在我的代码中，我的迭代器正在失效，即使我在它被删除之前对其进行了后递增？即我删除的迭代器以外的迭代器正在失效？

如果是这样，那很好，但它似乎是一个鲜为人知的错误。这意味着 common使用双端队列时，循环内迭代器删除的实现无效。

Answer 1

来自 deque::erase() 上的 cppreference :

All iterators and references are invalidated, unless the erased elements are at the end or the beginning of the container, in which case only the iterators and references to the erased elements are invalidated.

所有 迭代器。他们全部。当您这样做时:

mydeque.erase(it++);

后递增it并不重要，新的迭代器也会失效。这正是 erase() 返回的原因:

Iterator following the last removed element. If the iterator pos refers to the last element, the end() iterator is returned.

这样你就可以:

it = mydeque.erase(it); // erase old it, new it is valid

尽管更好的方法是使用删除-删除习惯用法来完全避免这种错误来源:

mydeque.erase(
   std::remove_if(mydeque.begin(), mydeque.end(), [](int i){return i%2 == 0; }),
   mydeque.end()
);

另见 this question有关迭代器失效的更多信息。