std::stable_partition(3)

💅 std::stable_partition — the C++ Standard Library's little reordering icon

okay so bestie, welcome to std::stable_partition(3) from the C++ Standard Library ✨ this one's a <algorithm> girlie and she's lowkey one of the most useful little functions in the whole header. let's get into it 🎀

---

🌸 NAME 🌸

std::stable_partition — literally std::stable_partition. yes the name is the name, we love a self-titled queen 👑

---

✨ SYNOPSIS ✨

she lives in the header <algorithm>, as all the good ones do 💖

template< class BidirIt, class UnaryPred >
BidirIt stable_partition( BidirIt first, BidirIt last,   (1)
(constexpr since C++26)
UnaryPred p );

template< class ExecutionPolicy, class BidirIt, class UnaryPred >

BidirIt stable_partition( ExecutionPolicy&& policy,      (2) (since C++17)

                              BidirIt first, BidirIt last,
UnaryPred p );

so here's the tea on the two overloads 🫖

1. Reorders the elements in the range [first, last) in such a way that all elements for which the predicate p returns true precede the elements for which predicate p returns false. And bestie — the relative order of the elements is preserved. that's the stable part, that's her whole brand 💅
2. Same as (1), but executed according to policy.

this overload only participates in overload resolution if:

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

⚠️ and now the scary part — if ANY of these conditions is satisfied, the behavior is undefined 😭 like genuinely undefined, do not test her: - The type of *first is not Swappable. (until C++11) - BidirIt is not ValueSwappable. - The type of *first is not MoveConstructible. (since C++11) - The type of *first is not MoveAssignable.

---

🦋 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 true if the element should be ordered before other elements.

okay the p situation has rules and we're gonna respect them 🙈 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). no cap, that's the whole vibe check on predicates 💀

---

🧚 Type requirements 🧚

• BidirIt must meet the requirements of LegacyBidirectionalIterator.
• UnaryPred must meet the requirements of Predicate.

both of them, no exceptions, she's picky and honestly? respect 💅

---

👑 Return value 👑

Iterator to the first element of the second group. that's it, that's the gift 🎁

---

🔥 Complexity 🔥

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

1. Exactly (\scriptsize N)N applications of p. (\scriptsize O(N))O(N) swaps if there is enough extra memory, otherwise at most (\scriptsize N \cdot log_{2}(N))N⋅log 2(N) swaps.
2. (\scriptsize O(N))O(N) applications of p. (\scriptsize N \cdot log(N))N⋅log(N) swaps.

so like... she's doing math but make it fashion 💖 the logarithms are real and we are NOT pretending otherwise 😭

---

💀 Exceptions 💀

The overload with a template parameter named ExecutionPolicy reports 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 other ExecutionPolicy, the behavior is implementation-defined.
• If the algorithm fails to allocate memory, std::bad_alloc is thrown.

yeah so std::terminate is not a vibe, be careful out there 🫶

---

🌈 Notes 🌈

This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen. she tries her best, and honestly? that's main character energy ✨

Implementations in libc++ and libstdc++ also accept ranges denoted by LegacyForwardIterators as an extension. cute bonus feature, iykyk 🎀

Feature-test macro time, she's got a whole table and everything:

• __cpp_lib_constexpr_algorithms — value 202306L, Std column: blank, feature: constexpr stable sorting ⭐

---

🍓 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

look at her go 😭 positives first, in the exact order they came in, then the rest, untouched. ICONIC. she ate and left no crumbs 👑

---

💜 Defect reports 💜

The following behavior-changing defect reports were applied retroactively to previously published C++ standards. history revisionism but make it standards-compliant 🌸

• LWG 2150 — Applied to: C++98
  • Behavior as published: std::stable_partition was only required to place one element satisfying p before one element not satisfying p.
  • Correct behavior: corrected the requirement.

so yeah, pre-LWG 2150 the requirement was lowkey slacking and they fixed it. glow-up 🦋

---

🌟 See also 🌟

• partition — divides a range of elements into two groups (function template)
• ranges::stable_partition (C++20) — divides elements into two groups while preserving their relative order (niebloid)

both of them are serving, pick whichever matches your vibe ✨

---

aaaand that's the page bestie 💖 source and version credits: this all comes from http://cppreference.com, dated 2024.06.10, for std::stable_partition(3) — go forth and partition stably, you've got this 🫶🌷