CKTIS / C++
std::stable_partition — stabilní rozdělení rozsahu
std::stable_partition přeuspořádá rozsah tak, aby prvky splňující predikát předcházely ostatním. Zachovává relativní pořadí v obou skupinách a vrací iterátor na hranici rozdělení.
Verze: C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
BidirectionalIterator first,
BidirectionalIterator last,
Predicate pred);
// Usage:
auto boundary = std::stable_partition(first, last, pred);std::stable_partition deklarované v <algorithm> upravuje [first, last): prvky, pro které pred vrátí true, se přesunou před ostatní. Relativní pořadí se zachovává zvlášť v obou skupinách. Nejde o řazení; std::partition tuto stabilitu nezaručuje.
Vrácený iterátor boundary ukazuje na první prvek druhé skupiny. Je roven last, pokud všechny prvky splňují predikát, a first, pokud jej nesplňuje žádný. U prázdného rozsahu funkce vrací first; v tomto případě platí first == last. Jsou vyžadovány obousměrné iterátory a prvky, které lze prohodit, vytvořit přesunem a přiřadit přesunem. Predikát nesmí měnit prvky, které kontroluje.
U zobrazeného přetížení bez zásady provádění se pro rozsah N prvků predikát použije přesně Nkrát. Provede se nejvýše N log₂ N prohození, případně O(N) při dostatku dodatečné paměti. Přeuspořádání existujícího rozsahu tedy nezaručuje konstantní pomocnou paměť.
Příklad zachovává pořadí sudých čísel 2, 4, 6 a lichých čísel 5, 7, 1; druhý řádek výstupu udává velikost první skupiny. Zobrazená deklarace cílí na C++23. Zdroj je průběžně vyvíjený pracovní návrh, který obsahuje i pozdější změny; jeho označení constexpr se nesmí automaticky vztahovat na C++23.
Příklady
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
std::vector<int> values{5, 2, 7, 4, 1, 6};
const auto boundary = std::stable_partition(
values.begin(), values.end(),
[](int value) { return value % 2 == 0; });
for (auto it = values.begin(); it != values.end(); ++it) {
if (it != values.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n' << std::distance(values.begin(), boundary) << '\n';
}
Výsledek
2 4 6 5 7 1 3
Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.