std::stable_partition

From cppreference.com

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros(C++20)
Language support library
Concepts library(C++20)
Diagnostics library
Memory management library
Metaprogramming library(C++11)
General utilities library
Containers library
Iterators library
Ranges library(C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library(C++17)
Concurrency support library(C++11)
Execution control library(C++26)
Technical specifications
Symbols index
External libraries

[edit]

Algorithm library

Constrained algorithms and algorithms on ranges(C++20)

Constrained algorithms, e.g.ranges::copy,ranges::sort, ...

Execution policies(C++17)

is_execution_policy

(C++17)

execution::seqexecution::parexecution::par_unseqexecution::unseq

(C++17) (C++17)(C++17)(C++20)

execution::sequenced_policyexecution::parallel_policyexecution::parallel_unsequenced_policyexecution::parallel_unsequenced

(C++17)(C++17)(C++17)(C++20)

Non-modifying sequence operations

(C++17)

all_ofany_ofnone_of (C++11) (C++11)(C++11)
countcount_if
mismatch
equal

findfind_iffind_if_not (C++11)
find_end
find_first_of
adjacent_find
search
search_n

Modifying sequence operations

Copy operations

copycopy_if (C++11)
copy_backward

copy_n (C++11)
move (C++11)
move_backward (C++11)

Swap operations

swap
iter_swap

swap_ranges

Transformation operations

replacereplace_if
transform

replace_copyreplace_copy_if

Generation operations

fill
fill_n

generate
generate_n

Removing operations

removeremove_if
unique

remove_copyremove_copy_if
unique_copy

Order-changing operations

reverse
reverse_copy
rotate
rotate_copy

random_shuffleshuffle (until C++17)(C++11)
shift_leftshift_right (C++20)(C++20)

Sampling operations

sample

(C++17)

Sorting and related operations

Partitioning operations

partition
partition_copy (C++11)
stable_partition

is_partitioned (C++11)
partition_point (C++11)

Sorting operations

sort
stable_sort
partial_sort
partial_sort_copy

is_sorted (C++11)
is_sorted_until (C++11)
nth_element

Binary search operations
(on partitioned ranges)

lower_bound
upper_bound

equal_range
binary_search

Set operations (on sorted ranges)

includes
set_union
set_intersection

set_difference
set_symmetric_difference

Merge operations (on sorted ranges)

merge

inplace_merge

Heap operations

push_heap
pop_heap
make_heap

sort_heap
is_heap (C++11)
is_heap_until (C++11)

Minimum/maximum operations

max
min
minmax (C++11)
clamp (C++17)

max_element
min_element
minmax_element (C++11)

Lexicographical comparison operations

lexicographical_compare

lexicographical_compare_three_way

(C++20)

Permutation operations

next_permutation
prev_permutation

is_permutation (C++11)

iota (C++11)
inner_product
adjacent_difference

accumulate
reduce (C++17)
transform_reduce (C++17)

partial_sum
inclusive_scan (C++17)
exclusive_scan (C++17)

transform_inclusive_scan (C++17)
transform_exclusive_scan (C++17)

Operations on uninitialized memory

uninitialized_copy
uninitialized_move (C++17)
uninitialized_fill

uninitialized_copy_n (C++11)
uninitialized_move_n (C++17)
uninitialized_fill_n

destroy (C++17)
destroy_n (C++17)
destroy_at (C++17)
construct_at (C++20)

uninitialized_default_construct (C++17)
uninitialized_value_construct (C++17)
uninitialized_default_construct_n (C++17)
uninitialized_value_construct_n (C++17)

[edit]

Defined in header`<algorithm>`
template<class BidirIt,class UnaryPred> BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPred p);	(1)	(constexpr since C++26)
template<class ExecutionPolicy,class BidirIt,class UnaryPred> BidirIt stable_partition( ExecutionPolicy&& policy, BidirIt first, BidirIt last, UnaryPred p);	(2)	(since C++17)

1) Reorders the elements in the range[first, last) in such a way that all elements for which the predicatep returnstrue precede the elements for which predicatep returnsfalse. Relative order of the elements is preserved.

2) Same as(1), but executed according topolicy.

This overload participates in overload resolution only if all following conditions are satisfied:

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> istrue.	(until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> istrue.	(since C++20)

If any of the following conditions is satisfied, the behavior is undefined:

The type of*first is notSwappable.	(until C++11)
`BidirIt` is notValueSwappable. The type offirst is notMoveConstructible. The type offirst is notMoveAssignable.	(since C++11)

[edit]Parameters

first, last	-	the pair of iterators defining therange of elements to reorder
policy	-	theexecution policy to use
p	-	unary predicate which returns true if the element should be ordered before other elements. The expressionp(v) must be convertible tobool for every argument`v` of type (possibly const)`VT`, where`VT` is the value type of`BidirIt`, regardless ofvalue category, and must not modify`v`. Thus, a parameter type ofVT&is not allowed, nor isVT unless for`VT` a move is equivalent to a copy(since C++11).
Type requirements
- `BidirIt` must meet the requirements ofLegacyBidirectionalIterator.
- `UnaryPred` must meet the requirements ofPredicate.

[edit]Return value

Iterator to the first element of the second group.

[edit]Complexity

Given\(\scriptsize N\)N asstd::distance(first, last):

1) Exactly\(\scriptsize N\)N applications ofp.

\(\scriptsize O(N)\)O(N) swaps if there is enough extra memory, otherwise at most\(\scriptsize N \cdot log_{2}(N)\)N⋅log2(N) swaps.

2)\(\scriptsize O(N)\)O(N) applications ofp.

\(\scriptsize N \cdot log(N)\)N⋅log(N) swaps.

[edit]Exceptions

The overload with a template parameter namedExecutionPolicy reports errors as follows:

If execution of a function invoked as part of the algorithm throws an exception andExecutionPolicy is one of thestandard policies,std::terminate is called. For any otherExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory,std::bad_alloc is thrown.

[edit]Notes

This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.

Implementations inlibc++ andlibstdc++ also accept ranges denoted byLegacyForwardIterators as an extension.

Feature-test macro	Value	Std	Feature
`__cpp_lib_constexpr_algorithms`	`202306L`	(C++26)	constexpr stable sorting(1)

[edit]Example

Run this code

#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';}

Output:

3 2 4 5 7 0 0 -1 0

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 2150	C++98	`std::stable_partition` was only required to place one element satisfyingp before one element not satisfyingp	corrected the requirement

[edit]See also

partition	divides a range of elements into two groups (function template)[edit]
ranges::stable_partition (C++20)	divides elements into two groups while preserving their relative order (algorithm function object)[edit]