5

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 的元素会被擦除。

4

4 回答 4

8

我会使用Erase-Remove Idiom。我认为链接的维基百科文章甚至显示了您正在做的事情——删除奇怪的元素。

这样做的复制remove_if成本并不比从容器中间删除元素时发生的成本高。它甚至可能更有效。

于 2010-12-03T03:56:43.323 回答
5

调用.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 前面运行。

于 2010-12-03T05:26:43.410 回答
2

请记住，双端队列是一个连续的内存容器（类似于向量，并且可能共享实现），因此删除容器中间的元素必然意味着将后续元素复制到洞上。您只想确保进行一次迭代并将每个不可删除的对象直接复制到其最终位置，而不是在每次删除期间一个接一个地移动所有对象。 remove_if在这方面是有效且适当的，但您的erase循环不是：它会进行大量不必要的复制。

FWIW - 替代品：

  • 为您的对象添加“已删除”状态并将它们标记为已删除，但是每次对容器进行操作时，您都需要检查自己
  • 使用一个列表，它是使用指向前一个和下一个元素的指针来实现的，这样删除一个列表元素会改变相邻的点以绕过该元素：没有复制，有效的迭代，只是没有随机访问，更小的（即低效的）堆分配和指针开销

选择什么取决于特定操作的性质、相对频率和性能要求（例如，如果它们在非关键时间完成，您可能可以承受缓慢的删除，但需要尽可能快的迭代 - 无论是什么，确保您了解您的需求以及各种数据结构的含义）。

于 2010-12-03T04:43:00.670 回答
0

尚未提及的一种替代方法是创建一个新deque的 ，将要保留的元素复制到其中，并将swap其与旧的deque.

void filter(std::deque<int>& in, std::pair<std::size_t,std::size_t> range) {
    std::deque<int> out;
    std::deque<int>::const_iterator first = in.begin();
    std::deque<int>::const_iterator curr = first + range.first;
    std::deque<int>::const_iterator last = first + range.second;
    out.reserve(in.size() - (range.second-range.first));
    std::copy(first, curr, std::back_inserter(out));
    while (curr != last) {
        if (*curr & 1) {
            out.push_back(*curr);
        }
        ++curr;
    }
    std::copy(last, in.end(), std::back_inserter(out));
    in.swap(out);
}

我不确定您是否有足够的内存来创建副本，但创建副本通常更快更容易，而不是尝试从大型集合中内联擦除元素。std::count_if如果你仍然看到内存抖动，那么通过调用并保留那么多元素来计算你要保留多少元素。这样你将有一个单一的内存分配。

于 2010-12-04T02:42:51.207 回答