Namespaces
Variants

    std::stable_partition

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围算法 (C++20)
    受约束算法，例如 ranges::copy、ranges::sort...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分搜索操作
    (在划分的范围上)
    集合操作(在有序范围上)
    合并操作(在有序范围上)
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <algorithm> 
    template< class BidirIt, class UnaryPred >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p );
    		(1) (自 C++26 起为 constexpr) 
    template< class ExecutionPolicy, class BidirIt, class UnaryPred >
BidirIt stable_partition( ExecutionPolicy&& policy,
                          BidirIt first, BidirIt last, UnaryPred p );
    		(2) (自 C++17 起)
    1) 重排范围 [first, last) 中的元素，使得所有谓词 p 返回 true 的元素排在谓词 p 返回 false 的元素之前。元素的相对顺序得以保持。
    2) 同 (1)，但按照 policy 执行。
    仅当下列表达式的值为 true 时，此重载参与重载决议：

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(至 C++20)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(自 C++20 起)

    如果满足下列任何条件，则行为未定义：

    (至 C++11)
    (自 C++11 起)

    参数

    first, last - 定义待重排元素 范围 的迭代器对
    policy - 要使用的 执行策略
    p - 一元谓词，若元素应排序于其他元素之前则返回​ true 。

    表达式 p ( v ) 必须可转换为 bool ，其中 v 为类型（可能为 const） VT 的参数， VT 是 BidirIt 的值类型，且与 值类别 无关，同时不得修改 v 。因此不允许参数类型为 VT & ，也不允许为 VT （除非对于 VT 移动操作等价于拷贝操作） (C++11 起) 。 ​

    类型要求
    -
    BidirIt 必须满足 LegacyBidirectionalIterator 的要求。
    -
    UnaryPred 必须满足 Predicate 的要求。

    返回值

    指向第二组第一个元素的迭代器。

    复杂度

    给定 N 为 std:: distance ( first, last ) ：

    1) 恰好 N 次对 p 的应用。
    O(N) 次交换（若有足够额外内存），否则最多 N⋅log 2 (N) 次交换。
    2) O(N) 次对 p 的调用。
    N⋅log(N) 次交换。

    异常

    带有名为 ExecutionPolicy 模板参数的重载按以下方式报告错误：

    • 如果作为算法一部分调用的函数执行抛出异常，且 ExecutionPolicy 是某个 标准策略 ，则调用 std::terminate 。对于其他任何 ExecutionPolicy ，其行为由实现定义。
    • 如果算法无法分配内存，则抛出 std::bad_alloc 。

    注释

    此函数尝试分配临时缓冲区。若分配失败，将选择效率较低的算法。

    在 libc++ 和 libstdc++ 中的实现还通过扩展功能接受由 LegacyForwardIterator s 表示的区间范围。

    功能测试 宏 值 标准 功能
    __cpp_lib_constexpr_algorithms 202306L (C++26) constexpr 稳定排序 ( 1 )

    示例

    运行此代码 
    #include <algorithm>
#include <iostream>
#include <vector>
int main()
{
    std::vector<int> v{0, 0, 3, -1, 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 -1 0

    缺陷报告

    下列行为变更缺陷报告被追溯应用于先前发布的 C++ 标准。

    缺陷报告 应用于 发布时的行为 正确行为
    LWG 2150 C++98 std::stable_partition 仅要求将满足 p 的一个元素
    置于不满足 p 的元素之前     		修正了
    该要求

    参见

    		 将元素范围分成两组
    (函数模板 & 算法函数对象)
    (C++20)
    (C++20)
    		 将元素分成两组，同时保留每组内元素的相对顺序
    (算法函数对象)