命名空间
变体
操作

std::stable_partition

来自 cppreference.cn
< cpp‎ | 算法
 
 
算法库
有约束算法与针对范围的算法 (C++20)
有约束的算法,例如 ranges::copyranges::sort 等……
执行策略 (C++17)
排序及相关操作
划分操作
(C++11)  
stable_partition
排序操作
二分搜索操作
(于已划分范围上)
集合操作(于已排序范围上)
归并操作(于已排序范围上)
堆操作
最小/最大值操作
(C++11)
(C++17)
字典序比较操作
排列操作
C 库
数值操作
未初始化内存上的操作
 
定义于头文件 <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) 重新排列范围 [firstlast) 中的元素,使得谓词 p 返回 true 的所有元素都在谓词 p 返回 false 的元素之前。元素间的相对顺序保持不变。
2)(1),但根据 policy 执行。
仅当满足以下所有条件时,此重载才参与重载决议

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

(C++20 前)

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

(C++20 起)

如果满足以下任何条件,则行为是未定义的:

(C++11 前)
(C++11 起)

目录

[编辑] 参数

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

表达式 p(v) 必须可转换为 bool,对于类型为 (可能为 const) VT 的每个参数 v,其中 VTBidirIt 的值类型,无论其值类别如何,且不得修改 v。因此,不允许参数类型为 VT&,除非对于 VT,移动等同于复制,否则也不允许 VT(C++11 起)

类型要求
-
BidirIt 必须满足 旧版双向迭代器 (LegacyBidirectionalIterator) 的要求。
-
UnaryPred 必须满足 Predicate 的要求。

[编辑] 返回值

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

[编辑] 复杂度

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

1)p 进行精确 N 次调用。
如果有足够的额外内存,则进行 O(N) 次交换,否则最多 N⋅log2(N) 次交换。
2)p 进行 O(N) 次调用。
N⋅log(N) 次交换。

[编辑] 异常

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

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

[编辑] 注意

此函数尝试分配临时缓冲区。如果分配失败,则选择效率较低的算法。

libc++libstdc++ 中的实现也作为扩展接受由旧版前向迭代器 (LegacyForwardIterator) 表示的范围。

特性测试 标准 特性
__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 的元素之前
已更正
要求

[编辑] 参阅

将一个范围的元素分成两组
(函数模板) [编辑]
将元素分成两组,同时保留它们的相对顺序
(算法函数对象)[编辑]