Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::stable_partition — stabilny podział zakresu

std::stable_partition przestawia elementy zakresu tak, aby spełniające predykat poprzedzały pozostałe. Zachowuje względną kolejność w obu grupach i zwraca iterator granicy podziału.

Wersja: C++23; repository compiler flag, production runtime not attested

Składnia

#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 z nagłówka <algorithm> modyfikuje zakres [first, last): elementy, dla których pred daje true, trafiają przed pozostałe. Względna kolejność zostaje zachowana osobno w obu grupach. To nie jest sortowanie; std::partition nie gwarantuje takiej stabilności.

Zwrócony iterator boundary wskazuje pierwszy element drugiej grupy. Wynosi last, gdy wszystkie elementy spełniają predykat, a first, gdy żaden go nie spełnia. Dla pustego zakresu funkcja zwraca first; w tym przypadku first == last. Wymagane są iteratory dwukierunkowe, możliwość zamiany elementów oraz ich konstruowania i przypisywania przez przeniesienie. Predykat nie może modyfikować sprawdzanych elementów.

Dla pokazanego przeciążenia bez polityki wykonania, przy N elementach predykat jest wywoływany dokładnie N razy. Liczba zamian wynosi najwyżej N log₂ N, a przy dostatecznej pamięci dodatkowej — O(N). Przestawianie istniejącego zakresu nie oznacza więc gwarancji stałej pamięci dodatkowej.

Przykład zachowuje kolejność liczb parzystych 2, 4, 6 i nieparzystych 5, 7, 1; druga linia wyniku to rozmiar pierwszej grupy. Pokazana deklaracja dotyczy C++23. Źródłem jest rozwijany szkic standardu, który zawiera też późniejsze zmiany; jego oznaczenia constexpr nie należy automatycznie przenosić do C++23.

Przykłady

#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';
}

Wynik

2 4 6 5 7 1
3

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła