CKTIS / C++
std::stable_partition — stabilna razdelitev obsega
std::stable_partition preuredi obseg tako, da so elementi, ki izpolnjujejo predikat, pred preostalimi. Ohrani relativni vrstni red v obeh skupinah in vrne iterator na mejo razdelitve.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#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, deklariran v <algorithm>, spremeni [first, last): elementi, za katere pred vrne true, so pred preostalimi. Relativni vrstni red se ohrani ločeno v obeh skupinah. To ni razvrščanje; std::partition te stabilnosti ne zagotavlja.
Vrnjeni iterator boundary kaže na prvi element druge skupine. Enak je last, če vsi elementi izpolnjujejo predikat, in first, če ga ne izpolnjuje noben. Pri praznem obsegu funkcija vrne first; v tem primeru velja first == last. Potrebni so dvosmerni iteratorji ter elementi, ki jih je mogoče zamenjati, konstruirati s premikom in prirediti s premikom. Predikat ne sme spreminjati elementov, ki jih preverja.
Pri prikazani preobremenitvi brez pravilnika izvajanja se za N elementov predikat uporabi natanko N-krat. Izvede se največ N log₂ N zamenjav oziroma O(N), če je na voljo dovolj dodatnega pomnilnika. Preurejanje obstoječega obsega zato ne zagotavlja konstantne porabe dodatnega pomnilnika.
Primer ohrani vrstni red sodih števil 2, 4, 6 in lihih števil 5, 7, 1; druga izhodna vrstica je velikost prve skupine. Prikazana deklaracija je namenjena za C++23. Vir je razvijajoči se delovni osnutek, ki vključuje tudi poznejše spremembe; njegovih oznak constexpr ne smemo samodejno prenesti na C++23.
Primeri
#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';
}
Rezultat
2 4 6 5 7 1 3
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.