WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::stable_partition — stabile Bereichspartitionierung

std::stable_partition ordnet einen Bereich so um, dass Elemente, für die ein Prädikat gilt, vor den übrigen stehen. Die relative Reihenfolge bleibt in beiden Gruppen erhalten; zurückgegeben wird ein Iterator auf die Grenze zwischen ihnen.

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

Syntax

#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 aus <algorithm> verändert den Bereich [first, last): Elemente, für die pred true ergibt, stehen vor den übrigen. Die relative Reihenfolge bleibt in beiden Gruppen jeweils erhalten. Dies ist keine Sortierung; std::partition garantiert diese Stabilität nicht.

Der zurückgegebene Iterator boundary zeigt auf das erste Element der zweiten Gruppe. Er ist gleich last, wenn alle Elemente das Prädikat erfüllen, und gleich first, wenn keines es erfüllt. Bei einem leeren Bereich gibt die Funktion first zurück; in diesem Fall gilt first == last. Erforderlich sind bidirektionale Iteratoren sowie Elemente, die vertauschbar sind, per Move-Konstruktor erzeugt und per Move-Zuweisung zugewiesen werden können. Das Prädikat darf die geprüften Elemente nicht verändern.

Für die gezeigte Überladung ohne Ausführungsrichtlinie wird das Prädikat bei N Elementen genau N-mal angewendet. Es gibt höchstens N log₂ N Vertauschungen; mit ausreichend zusätzlichem Speicher sinkt die Anzahl auf O(N). Das Umordnen des vorhandenen Bereichs bedeutet daher keine Garantie für konstanten zusätzlichen Speicherbedarf.

Das Beispiel erhält die Reihenfolge der geraden Zahlen 2, 4, 6 und der ungeraden Zahlen 5, 7, 1; die zweite Ausgabezeile gibt die Größe der ersten Gruppe an. Die gezeigte Deklaration ist für C++23 vorgesehen. Die Quelle ist ein fortlaufend weiterentwickelter Arbeitsentwurf, der auch spätere Änderungen enthält; seine constexpr-Markierungen dürfen nicht automatisch auf C++23 übertragen werden.

Beispiele

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

Ergebnis

2 4 6 5 7 1
3

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen