C++中partition()和remove()函数的区别

Question

partition() 和 remove() 函数在 C++ 中有什么区别？

remove() 函数并不会真正删除容器中的任何元素，而是将“已删除”的元素放在元素序列的开头；partition() 函数也会执行相同的操作。

- David Willis

Answer 1

使用 remove() 函数会将“已删除”的元素放在序列开头

不是这样的。无论是 remove_if 还是 partition 函数都会将“好”的元素放在序列的前面。而 partition 函数会将“坏”的元素放在后面，而 remove_if 函数没有指定其后面的元素是什么，它可能是坏元素，也可能是任何一个（好或坏）元素的副本。

例如，如果你在偶数上使用 partition 函数对序列 1 2 3 4 5 进行分区，你可能得到 2 4 5 3 1（注意每个元素恰好出现一次），而如果你删除奇数元素，你可能得到 2 4 3 4 5（注意重复元素）。

- fredoverflow

---

为了完整起见：remove_if 保持“好”的元素的相对顺序，而 partition 可能会重新排列它们，因此 partition 可以输出 4 2 5 1 3。如果好元素的相对顺序很重要，请使用 stable_partition，其输出保证是 2 4 1 3 5，保持每个组的相对顺序不变。 - Fabian

Answer 2

remove_if并不把删除的元素放到任何地方；新结尾后面的元素将保留原值，因此有些被删除的元素可能会丢失，有些保留的元素可能会重复。这比partition更快，并且可以使用前向迭代器完成，而partition需要双向迭代器。

更新：在 C++0x 中，partition 只需要前向迭代器，但如果迭代器不是双向的，则速度会更慢。

- Mike Seymour

---

如果“partition”需要双向迭代器，那么它为什么可以在“forward_list”上工作？ - fredoverflow

@FredOverflow：因为C++0x更改了partition的契约以使用前向迭代器。 - Mike Seymour

在某些情况下，partition比remove_if快得多。如果要删除的元素位于一个巨大向量的开头，remove_if会将整个向量向左移动，而partition只会将要删除的元素与最后一个元素交换。 - aberaud

@MikeSeymour 一般来说，从返回的迭代器开始的元素被视为具有“未指定”的值，而不是“保留其旧值”。 - Arne Vogel

Answer 3

如果我理解正确的话，remove并不会交换任何元素，而只是将谓词（在remove_if的情况下）为false的元素移动到序列的开头。如果你有一个数组：

a = [1,1,1,2,3]

然后调用 remove(a.begin(),a.end(),1)，你将得到：

a = [2,3,1,2,3]

之后，remove返回一个迭代器，这种情况下是第三个元素（如果我没记错的话...）

另一方面，partition保留了序列的所有原始元素，但改变它们的顺序，使谓词为true的元素放在谓词为false的元素前面。

partition(a.begin(), a.end(), not_equal<int>(1))得到：

a = [2,3,1,1,1]

- MartinStettner

---

请注意，std::remove()返回新的结束迭代器之后留下的内容是不保证的。虽然您展示的结果很可能正确，但并不是保证的。 - sbi

我曾认为std::remove保证不会改变新结尾迭代器后面的元素（它们仍然可以被访问）。但是标准可能会证明我是错的 :) ... - MartinStettner

标准没有规定新范围结束后元素的处理方式。虽然很难想象任何明智的实现会触及它们，但并不保证不会这样做。 - Mike Seymour

可以想象 std::remove_if 在 std::list 上做一些巧妙的事情。交换节点可能比赋值它们的 value_type 更便宜。 - MSalters

此外，有可能某些实现会在 std::vector<std::string> 中 移动 值，因为这比复制它们更便宜。或者甚至 交换 它们，让调用者决定是否销毁剩余的对象。 - sbi

Answer 4

来自C++标准库:教程和参考资料

remove() - 通过用后面未被删除的元素覆盖它们来逻辑地删除具有给定值的元素。不会改变它们所操作的范围中的元素数量。相反，它们返回范围的新“结尾”的位置。

partition() - 更改元素的顺序，使满足条件的元素位于前面

stable_partition() - 与partition()相同，但保留匹配和非匹配元素的相对顺序

- DumbCoder

Answer 5

partition - 根据特定的谓词（例如 std::vector 中的奇数和偶数）将容器的元素“分组”

remove - 从容器中删除某个值；实际上，元素被移动到初始容器的末尾，返回一个指向新末尾的迭代器，并且“已删除”的元素仍然可以访问

编辑：

remove - 从容器中删除某个值；与上述所述不同，元素不会被移动到初始容器的末尾，而是返回一个指向新末尾的迭代器，但范围 [newEnd，last) 中的迭代器仍然可解引用，因此可访问，但它们指向的元素是未指定的。

- celavek

---

这是错误的，删除操作会用后面的元素覆盖“已删除”的元素，因此之后可能无法访问所有元素... - MartinStettner

如果可以的话，我想知道我的答案错在了哪里，也许在这个过程中我能学到一些东西。 - celavek

@MartinStettner 我认为你错了。根据文档，“remove从范围[first，last）中删除所有等于value的元素。也就是说，remove返回一个迭代器new_last，使得范围[first，new_last）不包含任何等于value的元素。[1]范围[new_last，last）中的迭代器仍然可以解引用，但它们指向的元素是未指定的。Remove是稳定的，这意味着不等于value的元素的相对顺序保持不变。” http://www.sgi.com/tech/stl/remove.html - celavek

从STL文档中引用：“范围[new_last，last)中的迭代器仍然可以被解引用，但它们指向的元素是未指定的。” 这就是你回答中的问题所在。并没有将任何元素移动到容器的末尾，不过也不一定。 - haffax

@MartinSttetner @haffax 确实我错了。已经编辑答案以反映这一点。谢谢。 - celavek