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