Namespaces
Variants

    std::stable_partition

    From cppreference.com
     
    C++
     
    Algorithm library
    Constrained algorithms and algorithms on ranges (C++20)
    Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
    Non-modifying sequence operations    
    Batch operations
    (C++17)
    Search operations
    Modifying sequence operations
    Copy operations
    (C++11)
    (C++11)
    (C++11)
    Swap operations
    Transformation operations
    Generation operations
    Removing operations
    Order-changing operations
    (until C++17)(C++11)
    (C++20)(C++20)
    Sampling operations
    (C++17)

    Sorting and related operations
    Partitioning operations
    (C++11)    
    (C++11)

    Sorting operations
    Binary search operations
    (on partitioned ranges)
    Set operations (on sorted ranges)
    Merge operations (on sorted ranges)
    Heap operations
    Minimum/maximum operations
    (C++11)
    (C++17)
    Lexicographical comparison operations
    (C++20)
    Permutation operations


     
    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) Partitions the elements e in the target range [first, last) with respect to the expression bool(p(e)): all elements satisfy p appear before all elements that do not. The relative order of the elements in both groups is preserved.
    2) Same as (1), but executed according to policy.
    This overload participates in overload resolution only if the value of the following expression is true:

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

    		(until C++20)

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

    		(since C++20)

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

    (until C++11)
    (since C++11)

    Parameters

    first, last - the pair of iterators defining the target range
    p - unary predicate which returns ​true for the elements before the partition point.

    The expression p(v) must be convertible to bool for every argument v of type (possibly const) VT, where VT is the value type of BidirIt, regardless of value category, and must not modify v. Thus, a parameter type of VT&is not allowed, nor is VT unless for VT a move is equivalent to a copy(since C++11). ​

    policy - the execution policy to use
    Type requirements
    -
    BidirIt must meet the requirements of LegacyBidirectionalIterator.
    -
    UnaryPred must meet the requirements of Predicate.

    Return value

    The iterator iter indicating the partition point: all elements before iter satisfy p, while all elements starting from iter do not.

    Complexity

    Given N as std::distance(first, last):

    1) At most N⋅log2(N) swaps (or only 𝓞(N) swaps if there is enough extra memory), and exactly N applications of p.
    2) 𝓞(N·log(N)) swaps, and 𝓞(N) applications of p.

    Exceptions

    2) During the execution process:
    • If the temporary memory resources required for parallelization are not available, std::bad_alloc is thrown.
    • If an uncaught exception is thrown while accessing objects via an algorithm argument, the behavior is determined by the execution policy (for standard policies, std::terminate is invoked).

    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 LegacyForwardIterators as an extension.

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

    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

    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 satisfying p before one element not satisfying p     		corrected the
    requirement

    See also

    (C++20)
    		 divides elements into two groups while preserving their relative order within each group
    (algorithm function object)[edit]
    		divides a range of elements into two groups
    (function template & algorithm function object)[edit]
    (C++20)
    Morty Proxy This is a proxified and sanitized view of the page, visit original site.