Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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.

Zdroje