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++;

建议使用迭代器删除，这样您的迭代器就不会像上面 link 中提到的那样失效。

然而，当我运行这个时，我得到以下信息：

$ ./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" 下看到以下内容（强调我的）：

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.

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

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

Answer 1

So does that mean that in my code, my iterator is being invalidated even though I did a post increment on it before it is deleted?

就是这个意思。该无效是否对您的结果有任何影响，这取决于您的运行时库中 dequeue 的实现。它也可能在许多情况下运行良好，然后突然失败，例如您的 8。

post 增量技巧仅适用于容器，其中 erase 仅使迭代器对已删除元素无效（如 lists 和 sets） .在这些情况下，post 增量会创建指向 next 元素的迭代器，并在 before 元素被删除之前这样做。 next 元素的迭代器因此不受与擦除相关的失效的影响。然而，在 dequeue 的情况下，规范指出 all 迭代器无效。

Answer 2

来自 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++);

您 post 递增 it 并不重要，新的迭代器也会失效。这就是为什么 erase() returns:

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 了解有关迭代器失效的更多信息。

Answer 3

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

Scott Meyers 的 Effective STL 项目 9（恰如其分地命名为 "Choose carefully among erasing options"）展示了它是如何为 序列容器（向量、双端队列、字符串）

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() return 值正是我们所需要的：它是一旦完成擦除，指向被擦除元素之后的元素的有效迭代器。

Answer 4

C++14 引入了通用 erase_if 算法，可以正确处理所有类型的标准容器。

http://en.cppreference.com/w/cpp/experimental/deque/erase_if

这相当于@Barry提供的最后一个代码块：

#include <experimental/deque>
std::experimental::erase_if(mydeque, [](int i){return i%2 == 0; });

与直接 erase/remove-if 模式相比，使用这种通用算法也更好，因为如果您决定将容器替换为 std::set，例如，您将不需要更新处理删除的代码。

std::deque 错误？

Bug with std::deque?

c++

iterator

deque

c++11