调用erase时STL迭代器失效的问题

Question

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

   // 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;
}

检查如何实现std :: remove_if,似乎有一个非常昂贵的复制/降档过程正在进行.

• 没有所有复制/转换,是否有更有效的方法来实现上述目标

• 一般来说,删除/删除元素比使用序列中的下一个第n个值交换更昂贵(其中n是到目前为止删除/删除的元素数)

注意:答案应该假设序列大小非常大,+ 1mil元素,平均1/3的元素将被删除.

Answer 1

我会使用Erase-Remove Idiom.我认为连接的维基百科文章甚至可以显示你正在做的事情 - 删除奇怪的元素.

执行复制的remove_if成本并不比从容器中间删除元素时的复制成本高.它甚至可能更有效率.

Answer 2

呼叫.erase()还会导致"正在进行非常昂贵的复制/降档过程".从容器中间擦除元素时,该点之后的每个其他元素必须向下移动一个点到可用空间.如果擦除多个元素,则会为每个已擦除元素产生成本.一些未擦除的元素将移动几个点,但是被迫一次移动一个点而不是一次移动一个点.这是非常低效的.

标准库算法std::remove并std::remove_if优化这项工作.他们使用一个聪明的技巧来确保每个移动的元素只移动一次.这比你自己做的要快得多,与你的直觉相反.

伪代码是这样的:

read_location <- beginning of range.
write_location <- beginning of range.
while read_location != end of range:
    if the element at read_location should be kept in the container:
        copy the element at the read_location to the write_location.
        increment the write_location.
    increment the read_location.

正如您所看到的,原始序列中的每个元素都只被认为是一次,如果需要保留它,它只会被复制一次到当前的write_location.它永远不会被再次查看,因为write_location永远不会在read_location之前运行.