CKTIS / C++
Zakres podzielony na potrzeby wyszukiwania
`std::lower_bound` nie wymaga pełnego sortowania: dla danego klucza wszystkie elementy spełniające warunek muszą poprzedzać te, które go nie spełniają.
Wersja: ISO C++23; implementation support may vary
Składnia
#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))Zakres [first, last) jest podzielony względem klucza, gdy bool(comp(element, key)) daje najpierw same true, a potem same false. Każda z tych części może być pusta; żadna nie musi być wewnętrznie posortowana. Klasyczne std::lower_bound z <algorithm> zwraca pierwszy iterator, dla którego warunek jest fałszywy, lub last, gdy takiego elementu nie ma. Wynik nie musi być równy kluczowi. Naruszenie warunku podziału oznacza niezdefiniowane zachowanie.
Klasyczne przeciążenie z komparatorem używa go w kierunku od elementu do klucza. Może więc przyjąć lambdę [](const Sale& row, int key) porównującą row.sales > key; [] niczego nie przechwytuje. std::ranges::lower_bound (od C++20) przyjmuje parę iterator–wartownik lub cały zakres. Nakłada wymaganie indirect_strict_weak_order na komparator względem wartości po projekcji i klucza; &Sale::sales pozwala porównywać liczby. Obie wersje wymagają co najmniej iteratorów jednokierunkowych i wykonują logarytmiczną liczbę porównań, lecz bez dostępu swobodnego liczba przesunięć iteratora może być liniowa. Przeciążenie zakresowe zwraca std::ranges::dangling dla tymczasowego zakresu, którego iteratorów nie można używać po jego zniszczeniu. Nie dereferencjonuj iteratora końcowego ani unieważnionego.
std::nth_element i std::partial_sort wymagają iteratorów o dostępie swobodnym i ścisłego słabego porządku: comp(x, x) musi być fałszywe, a relacja porównania i równoważność wynikająca z dwóch porównań dających false muszą być przechodnie. Dla całkowitych wartości sprzedaży a.sales > b.sales spełnia te warunki, a >= nie. nth_element ustawia element na pozycji, którą zajmowałby po sortowaniu, i rozdziela obie części bez gwarancji ich posortowania; partial_sort sortuje wymagany początek i nie określa kolejności reszty. Żaden z nich nie gwarantuje odpowiedniego podziału dla dowolnego klucza w całym zakresie. Przy wielu różnych kluczach posortuj cały zakres według tego samego porządku.
Przykłady
#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';
}
}Wynik
70 70
Dla `90` oba wywołania wypisują `70`, pierwszą wartość nieprzekraczającą progu, mimo że zakres nie jest posortowany malejąco. Dla `100` wartość `95` daje `false` przed `true` dla `120`, więc na tym zakresie nie wolno wywoływać żadnej z tych wersji dla `100`.
Powiązane lekcje
- C++ · Lekcja 23 · Zaawansowany · Wersja: 3