CKTIS / C++
std::stable_partition — stabilna podjela raspona
std::stable_partition preslaguje raspon tako da elementi koji zadovoljavaju predikat prethode ostalima. Čuva relativni redoslijed unutar obiju skupina i vraća iterator na granicu podjele.
Verzija: 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 u <algorithm>, mijenja [first, last): elementi za koje pred vraća true dolaze prije ostalih. Relativni redoslijed zasebno se čuva unutar obiju skupina. Ovo nije sortiranje; std::partition ne jamči tu stabilnost.
Vraćeni iterator boundary pokazuje na prvi element druge skupine. Jednak je last ako svi elementi zadovoljavaju predikat, a first ako ga ne zadovoljava nijedan. Za prazan raspon funkcija vraća first; u tom slučaju vrijedi first == last. Potrebni su dvosmjerni iteratori te elementi koji se mogu zamjenjivati, konstruirati premještanjem i dodjeljivati premještanjem. Predikat ne smije mijenjati elemente koje provjerava.
Za prikazano preopterećenje bez pravila izvođenja, za raspon od N elemenata predikat se primjenjuje točno N puta. Broj zamjena najviše je N log₂ N, odnosno O(N) uz dovoljno dodatne memorije. Preslagivanje postojećeg raspona stoga ne jamči konstantnu pomoćnu memoriju.
Primjer čuva redoslijed parnih brojeva 2, 4, 6 i neparnih brojeva 5, 7, 1; drugi redak izlaza veličina je prve skupine. Prikazana deklaracija namijenjena je za C++23. Izvor je radni nacrt koji se stalno razvija i uključuje kasnije izmjene; njegove oznake constexpr ne treba automatski primjenjivati na C++23.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.