Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

Particionirani raspon za pretraživanje

`std::lower_bound` ne zahtijeva potpuno sortiran raspon: za zadani ključ svi elementi koji zadovoljavaju uvjet moraju prethoditi onima koji ga ne zadovoljavaju.

Verzija: ISO C++23; implementation support may vary

Sintaksa

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

Raspon [first, last) particioniran je s obzirom na ključ ako bool(comp(element, key)) prvo daje samo true, a zatim samo false. Oba dijela mogu biti prazna i nijedan ne mora biti sortiran iznutra. Klasični std::lower_bound iz <algorithm> vraća prvi iterator za koji je uvjet neistinit ili last ako takvog nema. Pronađeni element ne mora biti jednak ključu. Ako preduvjet particioniranja nije ispunjen, ponašanje je nedefinirano.

Klasično preopterećenje s komparatorom uspoređuje samo u smjeru od elementa prema ključu. Zato može prihvatiti lambda izraz [](const Sale& row, int key) koji provjerava row.sales > key; [] ništa ne hvata. std::ranges::lower_bound (od C++20) prima par iterator–sentinel ili raspon. Komparator mora zadovoljiti indirect_strict_weak_order za elemente nakon projekcije i za ključ; &Sale::sales omogućuje usporedbu cijelih brojeva. Obje verzije zahtijevaju barem iteratore za kretanje unaprijed i obavljaju logaritamski broj usporedbi, ali bez slučajnog pristupa broj pomaka iteratora može biti linearan. Preopterećenje koje prima raspon vraća std::ranges::dangling ako privremeni raspon nije borrowed_range. Nemoj dereferencirati krajnji ili poništeni iterator.

std::nth_element i std::partial_sort zahtijevaju iteratore sa slučajnim pristupom i strogi slabi poredak: comp(x, x) mora biti neistinit, a i usporedba i ekvivalencija određena dvjema neistinitim usporedbama moraju biti tranzitivne. Za cjelobrojne vrijednosti prodaje a.sales > b.sales ispunjava te uvjete, a >= ne. nth_element smješta element odabranog ranga na mjesto na kojem bi bio nakon sortiranja i razdvaja dva dijela bez jamstva da su sortirani. partial_sort sortira traženi početni dio, a redoslijed ostatka nije specificiran. Nijedan ne jamči particioniranje cijelog raspona za proizvoljan ključ. Za ponovljena pretraživanja s različitim ključevima sortiraj cijeli raspon prema istom poretku.

Primjeri

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Rezultat

70
70

Za `90` oba poziva ispisuju `70`, prvu vrijednost koja ne prelazi prag, iako raspon nije sortiran silazno. Za `100` vrijednost `95` daje `false` prije nego što `120` daje `true`, pa nijedan poziv s `100` na tom rasponu nije valjan.

Povezane lekcije

  • C++ · Lekcija 23 · Napredno · Verzija: 3

Izvori