CKTIS / C++
Rozsah rozdělený pro vyhledávání
`std::lower_bound` nevyžaduje úplné seřazení: pro daný klíč musí všechny prvky splňující test předcházet prvkům, které ho nesplňují.
Verze: ISO C++23; implementation support may vary
Syntaxe
#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 rozdělen vzhledem ke klíči, pokud bool(comp(element, key)) dává nejprve samé true a potom samé false. Obě části mohou být prázdné a uvnitř nemusejí být seřazené. Klasické std::lower_bound z <algorithm> vrátí první iterátor, pro který je test nepravdivý, nebo last, pokud takový není. Výsledek nemusí být roven klíči. Porušení podmínky rozdělení vede k nedefinovanému chování.
Klasické přetížení s komparátorem porovnává pouze ve směru od prvku ke klíči. Lze tedy použít lambdu [](const Sale& row, int key), která testuje row.sales > key; [] nic nezachycuje. std::ranges::lower_bound (od C++20) přijímá dvojici iterátor–sentinel nebo celý rozsah. Na komparátor klade požadavek indirect_strict_weak_order pro hodnoty po projekci a klíč; &Sale::sales umožní porovnávat celá čísla. Obě verze vyžadují alespoň dopředné iterátory a provádějí logaritmický počet porovnání, ale bez náhodného přístupu může být počet posunů iterátoru lineární. Přetížení pro rozsah vrátí std::ranges::dangling, pokud typ dočasného rozsahu nesplňuje koncept std::ranges::borrowed_range. Nedereferencuj koncový ani zneplatněný iterátor.
std::nth_element a std::partial_sort vyžadují iterátory s náhodným přístupem a striktní slabé uspořádání: comp(x, x) musí být nepravdivé a porovnání i ekvivalence určená dvěma nepravdivými porovnáními musejí být tranzitivní. Pro celočíselné hodnoty prodeje podmínky splňuje a.sales > b.sales, nikoli >=. nth_element umístí prvek zvolené pořadové pozice tam, kam by patřil po seřazení, a rozdělí obě části bez záruky jejich seřazení. partial_sort seřadí požadovaný začátek a pořadí zbytku není specifikováno. Ani jeden algoritmus nezaručuje rozdělení celého rozsahu pro libovolný klíč. Při opakovaném hledání různých klíčů seřaď celý rozsah podle stejného uspořádání.
Pří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ýsledek
70 70
Pro `90` vypíšou obě volání `70`, první hodnotu nepřevyšující mez, ačkoli rozsah není seřazen sestupně. Pro `100` dává `95` výsledek `false` dříve, než `120` dá `true`; s `100` proto není na tomto rozsahu platné ani jedno volání.
Související lekce
- C++ · Lekce 23 · Pokročilá · Verze: 3