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.