std::stable_partition()和std::partition()有什么区别？

Question

stable_partition(vect.begin(), vect.end(), [](int x) { return x % 2 == 0; });

partition(vect.begin(), vect.end(), [](int x) {
  return x % 2 == 0;
});

上面的代码是为了解释两者之间的区别。

Answer 1

“稳定”表示等价元素的顺序不会改变：

来自cppreference.com的std::stable_partition

对范围[first，last]中的元素进行重新排序，使谓词p返回true的所有元素都在谓词p返回false的元素之前。保留元素的相对顺序。

Answer 2

解决这个问题的最好方法可能是举个例子。让我在这里抄袭一下cppreference的例子：

#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
    std::vector<int> v{0, 0, 3, 0, 2, 4, 5, 0, 7};
    std::stable_partition(v.begin(), v.end(), [](int n){return n>0;});
    for (int n : v) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

运行这个命令会得到：3 2 4 5 7 0 0 0 0。3、2、4、5、7对于由> 0谓词定义的关系是等价的，并且正如预期的那样，它们不会被重新排序。

但是，如果将相同示例的stable_partition替换为partition，则会得到：7 5 3 4 2 0 0 0 0。这一次，没有保证保持等价元素的顺序，显然也没有保证。

Answer 3

正如在其他答案中所解释的那样，std::stable_partition保留了谓词返回true和false的组中元素的相对顺序。

但这是有代价的：std::stable_partition具有更高的时间/空间复杂度。如果您可以分配额外的存储空间，则可以在O(n)时间内实现std::stable_partition。但是，不能在O(n)时间内实现就地稳定分区。它可以在O(n log n)时间内完成。一个简单的分而治之算法的例子可以在here中找到。

适用于std::stable_partition reads的C++参考

Complexity (**std::stable_partition**)

给定N = last - first，

如果有足够的额外内存，谓词和O(N)的N应用程序完全可以互换。如果内存不足，最多只能交换N log N。

另请注意，std::stable_partition requires bidirectional iterators，而std::partition可以在前向操作。然而，在双向迭代器上，它是more efficient

Complexity (**std::partition**)

给定N = std::distance(first,last)，

谓词的N应用程序。如果ForwardIt满足LegacyBidirectionalIterator的要求，则最多交换N/2，否则最多交换N。

如果分区后元素的相对顺序并不重要，请使用std::partition。