std :: deque的错误？

Question

我试图使用循环和迭代器从双端队列中删除一个元素.我正在关注在线示例,但看到了一个错误.

我正在使用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"下面看到了(强调我的):

迭代器有效性如果擦除操作包括序列中的最后一个元素,则结束迭代器以及引用已擦除元素的迭代器,指针和引用无效.如果擦除包括第一个元素但不包括最后一个元素,则只有那些涉及擦除元素的元素无效.如果它发生在deque中的任何其他位置,则与容器相关的所有迭代器,指针和引用都将失效.

那么这是否意味着在我的代码中,即使我在删除之前对其进行了后期增量,我的迭代器也会失效？即除了我删除的迭代器之外的迭代器是无效的？

如果是这样,那么它很好,但它似乎是一个鲜为人知的bug.这意味着在使用deque时,循环中迭代器删除的常见实现无效.

Answer 1

来自cppreference deque::erase():

除非擦除的元素位于容器的末尾或开头,否则所有迭代器和引用都将失效,在这种情况下,只有迭代器和对擦除元素的引用才会失效.

所有迭代器.他们都是.当你这样做:

mydeque.erase(it++);

你后增量并不重要,it新的迭代器也是无效的.这正是为什么erase() 回报:

Iterator跟随最后删除的元素.如果迭代器pos引用最后一个元素,则返回end()迭代器.

这样你就可以做到:

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

有关迭代器失效的更多信息,另请参阅此问题.

Answer 2

您引用的代码仅适用于关联容器（set等map）。

Scott Meyers 的有效 STL第 9 项（恰当地命名为“在擦除选项中仔细选择”）展示了它如何用于序列容器（向量、双端队列、字符串）

for (SeqContainer<int>::iterator it = c.beqin(); it != c.end();) {
    if (predicate(*it)){
        it = c.erase(it); // keep it valid by assigning
    }                     // erase's return value to it
    else ++it;
}

在这里，erase()返回值正是我们所需要的：它是一个有效的迭代器，一旦擦除完成，它就会指向被擦除元素后面的元素。