调用擦除时STL迭代器失效的问题
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的元素将用于擦除。
我会使用擦除删除成语。 我认为维基百科的文章甚至显示你在做什么 - 去除奇怪的元素。
remove_if所做的复制不会比从容器中间删除元素时发生的代价更高。 它甚至可能更有效率。
调用.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前面运行。
请记住，deque是一个连续的内存容器（如向量，可能共享实现），因此在容器中移除元素必然意味着将随后的元素复制到洞中。 你只是想确保你正在做一次迭代，并将每个不被删除的对象直接复制到最终位置，而不是在每次删除时逐一移动所有对象。 remove_if在这方面是高效和适当的，你的erase循环不是：它会进行大量的不必要的复制。
FWIW - 备选方案：
选择什么取决于特定操作的性质，相对频率和性能要求（例如，如果它们在非关键时刻完成，但需要尽可能快的迭代 - 无论它是什么，您可以承受慢速清除，确保你了解你的需求和各种数据结构的含义）。
链接地址: http://www.djcxy.com/p/73323.html上一篇: Problem with invalidation of STL iterators when calling erase