vector中std::remove和erase的区别是什么？

Question

我有一个疑点需要澄清。我知道std::vector在erase和std::remove之间具有不同的行为。其中，erase可以从向量中物理删除元素，减小向量大小，而std::remove只是移动元素而不改变容量。

这只是为了效率考虑吗？使用erase时，std::vector中的所有元素都会向前移动一个位置，导致大量的复制操作；std::remove仅仅进行逻辑删除并通过移动保持向量不变。如果对象很重，那么这种差异可能很重要，对吗？

- Abruzzo Forte e Gentile

---

@larsmans，你错了。OP是正确的——有一个std::remove模板函数可以做到OP说的那样。 - sasha.sochka

@larsmans 不正确。std::remove是一种将集合中的元素标记为已删除的算法。 - Zac Howland

请参阅Scott Meyers的《Effective STL》（Addison-Wesley，2001年，第139-143页）中的“条款32”。 - Adam Burry

Answer 1

这种用法的原因正是出于效率考虑。尽管单次删除不会有太大影响，但如果需要从向量中删除多个元素，则可以获得性能上的优势。在这种情况下，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
                    );

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

- David Rodríguez - dribeas

---

这是一个很好的解释！我一直在专注于删除一个元素，而完全忘记了 std::remove 可以去除多个元素。非常感谢。 - Abruzzo Forte e Gentile

@AbruzzoForteeGentile：在删除单个元素的情况下，两种方法在成本方面完全相同。从被删除元素的位置到末尾的所有元素都需要被复制/移动，只有最后一个元素需要被销毁。 - David Rodríguez - dribeas

Answer 2

std::remove是STL中的一个算法，它与容器无关。它需要一些概念，但是它也被设计成可以与大小固定的C数组一起使用。

- yves Baumes

Answer 3

std::remove函数只是返回一个新的end()迭代器，指向最后一个未被删除元素之后的位置（从返回值到end()的项数将与要删除的项数相匹配，但不能保证它们的值与您要删除的相同 - 它们处于有效但未指定的状态）。这样做是为了使其适用于多种容器类型（基本上任何ForwardIterator可以遍历的容器类型）。 std::vector::erase实际上是在调整大小后设置新的end()迭代器。这是因为vector的方法实际上知道如何处理调整其迭代器（同样可以使用std::list::erase、std::deque::erase等方法）。 remove函数对给定的容器进行组织以删除不需要的对象。容器的erase函数实际上处理了容器需要执行的“删除”操作。这就是它们分开的原因。

- Zac Howland

---

“将所有已删除的项目移动到容器的末尾后”，std::remove并不会这样做。从返回位置开始的末尾元素将保留在未指定的状态下。 - Benjamin Lindley

由于remove基本上是将要删除的元素与不会被删除的元素进行交换，因此返回到end()的位置都是将要被删除的元素（并且仍处于有效状态），但您是正确的 - 不能保证它们“匹配”已经交换出去的元素。我稍微澄清一下。 - Zac Howland

@ZacHowland：现在最大的区别是，在C++11中，std::remove允许使用移动赋值，这将导致范围[result，end（））仅成为已移动元素。那些元素的状态取决于相关类。 - Dave S

@ZacHowland，最自然的remove实现方式不会交换任何内容，它只是进行覆盖。remove本质上将所有未删除的项移动到向量的头部，并覆盖已删除的项。 - Adam Burry

@AdamBurry 我之前把“swap”和“replace”混用了，但是没错。 - Zac Howland

Answer 4

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

请参考Yves Baumes的答案，了解std :: remove为什么设计成这样。

- Nathan Monteleone

Answer 5

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

- Jon

Answer 6

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

这很好，因为它允许算法通用地处理任何容器，也可以处理整个集合的子集范围。

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

- Duncan Smith

Answer 7

标准库算法操作的对象是序列。序列由一对迭代器定义；第一个指向序列中的第一个元素，第二个指向序列末尾的下一个位置。这就是全部内容；算法不关心序列来自哪里。

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

- Pete Becker