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 是到目前为止已删除/删除的元素数)
注意:答案应该假设序列大小非常大,+1 百万个元素,并且平均有 1/3 的元素会被擦除。