std::stable_partition() algorithm
- since C++26
- od C++17
- do C++17
// (1)
template< class BidirIt, class UnaryPredicate >
constexpr BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );
// (2)
template< class ExecutionPolicy, class BidirIt, class UnaryPredicate >
BidirIt stable_partition( ExecutionPolicy&& policy,
BidirIt first, BidirIt last, UnaryPredicate p );
// (1)
template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );
// (2)
template< class ExecutionPolicy, class BidirIt, class UnaryPredicate >
BidirIt stable_partition( ExecutionPolicy&& policy,
BidirIt first, BidirIt last, UnaryPredicate p );
// (1)
template< class BidirIt, class UnaryPredicate >
BidirIt stable_partition( BidirIt first, BidirIt last, UnaryPredicate p );
-
(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 to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(do C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(od C++20) istrue
.
Parameters
first last | The range of elements to reorder. |
policy | The execution policy to use. See execution policy for details. |
p | Unary predicate which returns The expression |
Type requirements
BidirIt | LegacyBidirectionalIterator ValueSwappable |
Dereferenced BidirIt | MoveAssignable MoveConstructible |
UnaryPredicate | Predicate |
Return value
Iterator to the first element of the second group.
Complexity
Given N
as std::distance(first, last)
:
(1) Exactly N
applications of p
and O(N) swaps if there is enough extra memory. If memory is insufficient, at most N * log(N) swaps.
(2) O(N * log(N)) swaps and O(N) applications of p
.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard 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.
Possible implementation
stable_partition (1)
template<class ForwardIt, class UnaryPredicate>
ForwardIt stable_partition(ForwardIt first, ForwardIt last, UnaryPredicate 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;
}
Notes
This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.
Implementations in libc++
and libstdc++
also accept ranges denoted by LegacyForwardIterator
s as an extension.
Examples
#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
Hover to see the original license.