Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

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.

Izvori