Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

CKTIS / C++

std::stable_partition — partizione stabile di un intervallo

std::stable_partition riordina un intervallo in modo che gli elementi che soddisfano un predicato precedano gli altri. Mantiene l’ordine relativo in entrambi i gruppi e restituisce un iteratore al confine della partizione.

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

Sintassi

#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, dichiarato in <algorithm>, modifica [first, last): gli elementi per cui pred restituisce true precedono gli altri. L’ordine relativo viene mantenuto separatamente in entrambi i gruppi. Non è un ordinamento; std::partition non garantisce questa stabilità.

L’iteratore restituito boundary indica il primo elemento del secondo gruppo. È uguale a last se tutti gli elementi soddisfano il predicato e a first se nessuno lo soddisfa. Se l’intervallo è vuoto, la funzione restituisce first; in questo caso vale first == last. Sono richiesti iteratori bidirezionali ed elementi scambiabili, costruibili per spostamento e assegnabili per spostamento. Il predicato non deve modificare gli elementi esaminati.

Per l’overload mostrato, senza una policy di esecuzione, un intervallo di N elementi richiede esattamente N applicazioni del predicato. Si effettuano al massimo N log₂ N scambi, ridotti a O(N) con memoria aggiuntiva sufficiente. Riordinare l’intervallo esistente non garantisce quindi un uso costante di memoria ausiliaria.

L’esempio mantiene l’ordine dei numeri pari 2, 4, 6 e dispari 5, 7, 1; la seconda riga dell’output è la dimensione del primo gruppo. La dichiarazione mostrata è destinata a C++23. La fonte è una bozza di lavoro in evoluzione che include anche modifiche successive; le annotazioni constexpr non vanno applicate automaticamente a C++23.

Esempi

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

Risultato

2 4 6 5 7 1
3

Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.

Fonti