调用擦除时STL迭代器无效的问题 [英] Problem with invalidation of STL iterators when calling erase

问题描述

STL标准定义当在容器（例如std :: deque，std :: list等）上进行擦除时，迭代器无效。

我的问题如下，假设std :: deque中包含的整数列表，以及指示std :: deque中元素范围的一对指示符，删除所有偶数元素的正确方法是什么？

到目前为止，我有以下问题，但是这里的问题是假设结束在擦除后无效：

  #include< cstddef> 
 #include< deque> 
 
 int main（）
 {
 std :: deque< int> deq; 
 for（int i = 0; i <100; deq.push_back（i ++））; 
 
 //范围，第11到第51元素
 std :: pair< std :: size_t，std :: size_t> r（10,50）; 
 
 std :: deque< int> :: iterator it = deq.begin（）+ r.first; 
 std :: deque< int> :: iterator end = deq.begin（）+ r.second; 
 
 while（it！= end）
 {
 if（* it％2 == 0）
 {
 it = deqererase ）; 
} 
 else 
 ++ it; 
} 
 
 return 0; 
} 
  

检查std :: remove_if是如何实现的，复制/减速过程继续。

• 有没有所有复制/ b $ b

• 一般来说，删除/删除比在序列中下一个第n个值交换的元素更为昂贵（其中n是到目前为止删除/删除的元素的数量）。

  li>
  

注意：答案应该假定序列大小相当大，+ 1mil元素，平均1/3

解决方案

我会使用擦除 - 删除成语。我认为维基百科文章链接甚至显示你在做什么 - 删除奇怪的元素。

复制 remove_if 确实不会比从容器中间删除元素时发生的更昂贵。它甚至可能更有效率。

The STL standard defines that when an erase occurs on containers such as std::deque, std::list etc iterators are invalidated.

My question is as follows, assuming the list of integers contained in a std::deque, and a pair of indicies indicating a range of elements in the std::deque, what is the correct way to delete all even elements?

So far I have the following, however the problem here is that the assumed end is invalidated after an erase:

#include <cstddef>
#include <deque>

int main()
{
   std::deque<int> deq;
   for (int i = 0; i < 100; deq.push_back(i++));

   // range, 11th to 51st element
   std::pair<std::size_t,std::size_t> r(10,50);

   std::deque<int>::iterator it = deq.begin() + r.first;
   std::deque<int>::iterator end = deq.begin() + r.second;

   while (it != end)
   {
      if (*it % 2 == 0)
      {
         it = deq.erase(it);
      }
      else
        ++it;
   }

   return 0;
}

Examining how std::remove_if is implemented, it seems there is a very costly copy/shift down process going on.

• Is there a more efficient way of achieving the above without all the copy/shifts

• In general is deleting/erasing an element more expensive than swapping it with the next nth value in the sequence (where n is the number of elements deleted/removed so far)

Note: Answers should assume the sequence size is quite large, +1mil elements and that on average 1/3 of elements would be up for erasure.

解决方案

I'd use the Erase-Remove Idiom. I think the Wikipedia article linked even shows what you're doing -- removing odd elements.

The copying that remove_if does is no more costly than what happens when you delete elements from the middle of the container. It might even be more efficient.

这篇关于调用擦除时STL迭代器无效的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！