База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C++

Разделен диапазон за търсене

`std::lower_bound` не изисква целият диапазон да е сортиран: за дадения ключ всички елементи, които изпълняват условието, трябва да предхождат останалите.

Версия: ISO C++23; implementation support may vary

Синтаксис

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

Диапазонът [first, last) е разделен спрямо ключа, ако bool(comp(element, key)) дава първо само true, а след това само false. Всяка от двете части може да е празна и не е нужно да е сортирана вътрешно. Класическият std::lower_bound от <algorithm> връща първия итератор, за който условието е невярно, или last, ако няма такъв. Намереният елемент може да не е равен на ключа. Нарушаването на предусловието за разделяне води до неопределено поведение.

Класическата претоварена версия с компаратор сравнява само в посока от елемента към ключа. Затова може да използва ламбда израз [](const Sale& row, int key), който проверява row.sales > key; [] не прихваща нищо. std::ranges::lower_bound (от C++20) приема двойка итератор–сентинел или диапазон. Компараторът трябва да удовлетворява indirect_strict_weak_order за проектираните елементи и ключа; &Sale::sales позволява да се сравняват цели числа. И двете версии изискват поне итератори с движение напред и правят логаритмичен брой сравнения, но без произволен достъп броят на преместванията на итератора може да е линеен. Претоварването, което приема диапазон, връща std::ranges::dangling за временен диапазон, който не е borrowed_range. Не дереферирай краен или невалиден итератор.

std::nth_element и std::partial_sort изискват итератори с произволен достъп и строга слаба наредба: comp(x, x) трябва да е невярно, а сравнението и еквивалентността, определена от две неверни сравнения, трябва да са транзитивни. За целочислени стойности на продажбите a.sales > b.sales изпълнява тези условия, а >= не. nth_element поставя елемента с избрания ранг там, където би бил след сортиране, и разделя двете части, без да гарантира, че са сортирани. partial_sort сортира началната част с поисканата дължина и оставя останалите елементи в неуточнен ред. Нито един не гарантира разделяне на целия диапазон за произволен ключ. При многократни търсения с различни ключове сортирай целия диапазон по същата наредба.

Примери

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

Резултат

70
70

За `90` и двете извиквания извеждат `70`, първата стойност, която не надвишава прага, въпреки че диапазонът не е сортиран в низходящ ред. За `100` стойността `95` дава `false` преди `120` да даде `true`, затова нито едно от двете извиквания с `100` не е валидно за този диапазон.

Свързани уроци

  • C++ · Урок 23 · Напреднало · Версия: 3

Източници