CKTIS / C++
Razdeljeno iskalno območje
`std::lower_bound` ne zahteva povsem urejenega območja: pri danem ključu morajo vsi elementi, ki izpolnijo pogoj, stati pred tistimi, ki ga ne izpolnijo.
Različica: 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))Območje [first, last) je razdeljeno glede na ključ, če bool(comp(element, key)) najprej vrača samo true, nato pa samo false. Oba dela sta lahko prazna in znotraj njiju ni treba urediti elementov. Klasični std::lower_bound iz <algorithm> vrne prvi iterator, pri katerem je pogoj neresničen, ali last, če takega ni. Najdeni element ni nujno enak ključu. Če pogoj razdeljenosti ni izpolnjen, je obnašanje nedefinirano.
Klasična preobremenitev s primerjalnikom primerja le v smeri od elementa do ključa. Zato lahko uporabi lambda izraz [](const Sale& row, int key), ki preveri row.sales > key; [] ne zajame ničesar. std::ranges::lower_bound (od C++20) sprejme par iterator–sentinel ali območje. Primerjalnik mora izpolniti indirect_strict_weak_order za projicirane elemente in ključ; &Sale::sales omogoča primerjanje celih števil. Obe različici zahtevata vsaj iteratorje za pomikanje naprej in opravita logaritemsko število primerjav, toda brez naključnega dostopa je število korakov iteratorja lahko linearno. Preobremenitev, ki sprejme območje, vrne std::ranges::dangling, če začasno območje ni borrowed_range. Končnega ali razveljavljenega iteratorja ne dereferenciraj.
std::nth_element in std::partial_sort zahtevata iteratorje z naključnim dostopom in strogo šibko urejenost: comp(x, x) mora biti neresničen, primerjava in ekvivalenca, določena z dvema neresničnima primerjavama, pa morata biti tranzitivni. Za celoštevilske vrednosti prodaje a.sales > b.sales te pogoje izpolni, >= pa ne. nth_element postavi element izbranega ranga na položaj, ki bi ga imel po urejanju, in loči oba dela, ne da bi zagotavljal njuno urejenost. partial_sort uredi zahtevani začetni del, vrstni red preostanka pa ni določen. Nobeden ne zagotavlja razdeljenosti celotnega območja za poljuben ključ. Pri ponavljajočem se iskanju z različnimi ključi uredi celotno območje po istem pravilu.
Primeri
#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 klica izpišeta `70`, prvo vrednost, ki ne presega praga, čeprav območje ni urejeno padajoče. Za `100` je pri `95` rezultat `false`, preden pri `120` dobimo `true`, zato na tem območju noben klic s `100` ni veljaven.
Povezane lekcije
- C++ · Lekcija 23 · Napredna · Različica: 3