Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

Rozsah rozdelený na vyhľadávanie

`std::lower_bound` nevyžaduje úplne zoradený rozsah: pre daný kľúč musia všetky prvky, ktoré spĺňajú test, predchádzať prvkom, ktoré ho nespĺňajú.

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

Syntax

#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))

Rozsah [first, last) je rozdelený vzhľadom na kľúč, ak bool(comp(element, key)) dáva najprv samé true a potom samé false. Obe časti môžu byť prázdne a nemusia byť vnútorne zoradené. Klasické std::lower_bound z <algorithm> vráti prvý iterátor, pre ktorý je test nepravdivý, alebo last, ak taký neexistuje. Výsledok sa nemusí rovnať kľúču. Porušenie podmienky rozdelenia vedie k nedefinovanému správaniu.

Klasické preťaženie s komparátorom porovnáva iba v smere od prvku ku kľúču. Môže teda použiť lambdu [](const Sale& row, int key), ktorá testuje row.sales > key; [] nič nezachytáva. std::ranges::lower_bound (od C++20) prijíma dvojicu iterátor–sentinel alebo rozsah. Komparátor musí spĺňať indirect_strict_weak_order pre projektované prvky a kľúč; &Sale::sales umožňuje porovnávať celé čísla. Obe verzie vyžadujú aspoň dopredné iterátory a vykonajú logaritmický počet porovnaní, ale bez náhodného prístupu môže byť počet posunov iterátora lineárny. Preťaženie pre rozsah vráti std::ranges::dangling pre dočasný rozsah, ktorý nie je borrowed_range. Nedereferencuj koncový ani zneplatnený iterátor.

std::nth_element a std::partial_sort vyžadujú iterátory s náhodným prístupom a striktné slabé usporiadanie: comp(x, x) musí byť nepravdivé a porovnanie aj ekvivalencia určená dvoma nepravdivými porovnaniami musia byť tranzitívne. Pre celočíselné hodnoty predaja to spĺňa a.sales > b.sales, nie však >=. nth_element umiestni prvok zvoleného poradia na pozíciu, ktorú by mal po zoradení, a oddelí dve časti bez záruky ich zoradenia. partial_sort zoradí požadovaný začiatok a poradie zvyšku nechá nešpecifikované. Ani jeden nezaručuje rozdelenie celého rozsahu pre ľubovoľný kľúč. Pri opakovanom vyhľadávaní rôznych kľúčov zoraď celý rozsah podľa rovnakého usporiadania.

Príklady

#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';
    }
}

Výsledok

70
70

Pre `90` obe volania vypíšu `70`, prvú hodnotu neprekračujúcu hranicu, hoci rozsah nie je zoradený zostupne. Pre `100` dáva `95` hodnotu `false` skôr, než `120` dá `true`, takže s `100` nie je na tomto rozsahu platné ani jedno volanie.

Súvisiace lekcie

  • C++ · Lekcia 23 · Pokročilá · Verzia: 3

Zdroje