std::stable_partition
来自 cppreference.cn
定义于头文件 <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, |
(2) | (C++17 起) |
1) 重新排列范围
[
first,
last)
中的元素,使得谓词 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) |
类型要求 | ||
-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 的元素之前 |
已更正 要求 |
[编辑] 参阅
将一个范围的元素分成两组 (函数模板) | |
(C++20) |
将元素分成两组,同时保留它们的相对顺序 (算法函数对象) |