Namespaces
Variants

    std::partition

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

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


     
    定义于头文件 <algorithm> 
    template< class ForwardIt, class UnaryPred >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPred p );
    		(1) (constexpr，C++20 起) 
    template< class ExecutionPolicy, class ForwardIt, class UnaryPred >
ForwardIt partition( ExecutionPolicy&& policy, 
                     ForwardIt first, ForwardIt 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 起)

    如果 ForwardIt 的类型*first不是 Swappable(C++11 前)ForwardIt不是 ValueSwappable(C++11 起)，则行为未定义。

    参数

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

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

    类型要求
    -
    ForwardIt 必须满足 LegacyForwardIterator 的要求。
    -
    UnaryPred 必须满足 Predicate 的要求。

    返回值

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

    复杂度

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

    1) 恰好 N 次对 p 的应用。
    最多进行 N/2 次交换（若 ForwardIt 满足 LegacyBidirectionalIterator 的要求），否则最多进行 N 次交换。
    2) O(N) 次对 p 的调用。
    O(N·log(N)) 次交换。

    异常

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

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

    可能的实现

    实现重载 (1) 并保持 C++11 兼容性。 

    template<class ForwardIt, class UnaryPred>
ForwardIt partition(ForwardIt first, ForwardIt last, UnaryPred p)
{
    first = std::find_if_not(first, last, p);
    if (first == last)
        return first;
    for (auto i = std::next(first); i != last; ++i)
        if (p(*i))
        {
            std::iter_swap(i, first);
            ++first;
        }
    return first;
}

    示例

    运行此代码 
    #include <algorithm>
#include <forward_list>
#include <iostream>
#include <iterator>
#include <vector>
template<class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
    if (first == last)
        return;
    auto pivot = *std::next(first, std::distance(first, last) / 2);
    auto middle1 = std::partition(first, last, [pivot](const auto& em)
    {
        return em < pivot;
    });
    auto middle2 = std::partition(middle1, last, [pivot](const auto& em)
    {
        return !(pivot < em);
    });
    quicksort(first, middle1);
    quicksort(middle2, last);
}
int main()
{
    std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::cout << "Original vector: ";
    for (int elem : v)
        std::cout << elem << ' ';
    auto it = std::partition(v.begin(), v.end(), [](int i) {return i % 2 == 0;});
    std::cout << "\nPartitioned vector: ";
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << "* ";
    std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
    std::forward_list<int> fl {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
    std::cout << "\nUnsorted list: ";
    for (int n : fl)
        std::cout << n << ' ';
    quicksort(std::begin(fl), std::end(fl));
    std::cout << "\nSorted using quicksort: ";
    for (int fi : fl)
        std::cout << fi << ' ';
    std::cout << '\n';
}

    可能的输出： 

    Original vector: 0 1 2 3 4 5 6 7 8 9 
Partitioned vector: 0 8 2 6 4 * 5 3 7 1 9 
Unsorted list: 1 30 -4 3 5 -4 1 6 -8 2 -5 64 1 92 
Sorted using quicksort: -8 -5 -4 -4 1 1 1 2 3 5 6 30 64 92

    缺陷报告

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

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

    另见

    (C++11)
    		 确定范围是否按给定谓词分区
    (函数模板 & 算法函数对象)
    (C++20)
    		将元素分成两组，同时保留每组内的相对顺序
    (函数模板 & 算法函数对象)
    (C++20)
    (C++20)
    		 将元素范围分成两组
    (算法函数对象)