Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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

Źródła