39

我有一个疑问，我想在脑海中澄清一下。我知道在第一个从向量中物理删除一个元素，减小大小，而另一个只是移动一个元素而使容量保持不变的位置std::vector之间erase和位置的不同行为。std::remove

这仅仅是出于效率原因吗？使用erase时，a 中的所有元素std::vector都会移位 1，造成大量副本；std::remove只是进行“逻辑”删除，并通过移动东西来保持向量不变。如果物体很重，那么这种差异可能很重要，对吧？

4

7 回答 7

38

这仅仅是出于效率的原因吗？通过使用擦除 std::vector 中的所有元素将被移动 1 导致大量副本；std::remove 仅执行“逻辑”删除，并通过移动事物使向量保持不变。如果物体很重，那么差异可能很重要，对吗？

使用这个成语的原因正是如此。在性能上有好处，但在单次擦除的情况下没有。重要的是您是否需要从向量中删除多个元素。在这种情况下，将每个未删除std::remove的元素仅复制一次到其最终位置，而该方法会将所有元素从该位置移动到末尾多次。考虑：vector::erase

std::vector<int> v{ 1, 2, 3, 4, 5 };
// remove all elements < 5

如果您逐个删除元素，则会删除 1，从而导致剩余元素的副本被移动 (4)。然后，您将删除 2 并将所有剩余元素移动一 (3) ... 如果您看到模式，这是一种O(N^2)算法。

在算法的情况下，std::remove维护一个读写头，并迭代容器。对于前 4 个元素，将移动读取头并测试元素，但不会复制任何元素。仅对于第五个元素，对象将从最后一个位置复制到第一个位置，并且算法将以单个副本完成并将迭代器返回到第二个位置。这是一个O(N)算法。带有范围的后者std::vector::erase将导致所有剩余元素的破坏并调整容器的大小。

正如其他人所提到的，在标准库中，算法被应用于迭代器，并且缺乏对被迭代序列的了解。这种设计比算法知道容器的其他方法更灵活，因为算法的单个实现可以与任何符合迭代器要求的序列一起使用。例如，std::remove_copy_if通过使用生成/接受序列的迭代器，即使没有容器也可以使用它：

std::remove_copy_if(std::istream_iterator<int>(std::cin),
                    std::istream_iterator<int>(),
                    std::ostream_iterator<int>(std::cout, " "),
                    [](int x) { return !(x%2); } // is even
                    );

该单行代码将过滤掉标准输入中的所有偶数并将其转储到标准输出，而无需将所有数字加载到容器中的内存中。这是拆分的优点，缺点是算法不能修改容器本身，只能修改迭代器引用的值。

于 2013-10-10T13:39:36.200 回答
8

std::remove是一种来自 STL 的算法，它与容器完全无关。它需要一些概念，没错，但它被设计为也可以与 C 数组一起使用，这些数组的大小是静态的。

于 2013-10-10T13:28:30.977 回答
6

std::remove只需返回一个新的end()迭代器以指向最后一个未删除元素之后的一个（返回值中end()的项目数将与要删除的项目数匹配，但不能保证它们的值与您的值相同移除 - 它们处于有效但未指定的状态）。这样做是为了它可以适用于多种容器类型（基本上是任何ForwardIterator可以迭代的容器类型）。

std::vector::erase实际上是end()在调整大小后设置新的迭代器。这是因为vector' 方法实际上知道如何调整它的迭代器（同样可以用std::list::erase,std::deque::erase等来完成）。

remove组织给定容器以删除不需要的对象。容器的擦除功能实际上以容器需要的方式处理“删除”。这就是为什么它们是分开的。

于 2013-10-10T13:31:12.460 回答
5

我认为这与需要直接访问向量本身才能调整它的大小有关。std::remove 只能访问迭代器，所以它无法告诉向量“嘿，你现在有更少的元素”。

请参阅 yves Baumes 关于 std::remove 为何以这种方式设计的回答。

于 2013-10-10T13:29:45.953 回答
4

是的，这就是它的要点。请注意，erase其他标准容器也支持它的性能特征不同（例如list::erase是 O(1)），而std::remove它与容器无关并且适用于任何类型的前向迭代器（因此它适用于例如裸数组以及）。

于 2013-10-10T13:27:10.640 回答
0

有点儿。诸如 remove 之类的算法在迭代器（这是表示集合中元素的抽象）上工作，它们不一定知道它们正在操作哪种类型的集合 - 因此不能调用集合上的成员来进行实际的删除。

这很好，因为它允许算法在任何容器以及作为整个集合子集的范围上通用。

此外，正如您所说，为了性能 - 如果您只需要访问逻辑结束位置以传递给另一个算法，则可能不需要实际删除（和销毁）元素。

于 2013-10-10T13:39:00.790 回答
0

标准库算法对序列进行操作。序列由一对迭代器定义；第一个指向序列中的第一个元素，第二个指向序列的末尾。就这样; 算法不关心序列来自哪里。

标准库容器保存数据值，并提供一对迭代器，指定算法使用的序列。它们还提供成员函数，通过利用容器的内部数据结构，可以更有效地执行与算法相同的操作。

于 2013-10-10T13:39:34.223 回答