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

CKTIS / C++

std::upper_bound — границата след еквивалентните елементи

`std::upper_bound` намира границата на разделяне на диапазона за търсената стойност: връща итератор към първия елемент, от който `value` е по-малка според използваното сравнение, или `last`, ако такъв елемент няма. При сравнение по подразбиране и числа, сортирани във възходящ ред, това е първото число, по-голямо от `value`.

Версия: C++23; repository compiler flag, production runtime not attested

Синтаксис

#include <algorithm>
std::upper_bound(first, last, value)
std::upper_bound(first, last, value, comp)

std::upper_bound, декларирана в <algorithm>, търси в полуотворения диапазон [first, last). При сравнение по подразбиране и възходящ ред връща първия елемент, по-голям от value, като пропуска всички дубликати на тази стойност. Резултатът е итератор, а не индекс или указание дали стойността присъства. Ако няма подходящ елемент, включително в празен диапазон, резултатът е last. Преди дерефериране проверете дали резултатът е last.

Версията с comp търси първия елемент e, за който comp(value, e) е вярно. Предварителното условие изисква диапазонът да е разделен така, че първо да са всички елементи, за които е вярно !comp(value, e), а след тях — останалите. Пълното сортиране по съвместим ред е достатъчно, но не е необходимо за едно търсене. Не търсете в произволно неподредени данни: нарушаването на предварителното условие води до неопределено поведение. Значението на „по-голям“ зависи от компаратора, а не непременно от числовия оператор >.

Във възходящ диапазон std::lower_bound намира първия елемент, който не е по-малък от value, а std::upper_bound намира първия по-голям елемент. В сортиран диапазон тези граници ограничават елементите, еквивалентни според сравнението. Обърнете внимание на реда на аргументите: std::upper_bound използва comp(value, element), а не comp(element, value).

Необходими са поне forward итератори. Броят на сравненията е O(log N), но без произволен достъп броят на стъпките на итератора може да е O(N); при итератори на std::vector броят на стъпките е логаритмичен. Примерът използва синтаксис, съвместим с C++23. Свързаният работен проект се развива и може да съдържа по-нови декларации.

Примери

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    const std::vector<int> values{1, 2, 2, 2, 4, 7};
    const auto it = std::upper_bound(values.begin(), values.end(), 2);
    std::cout << "index=" << (it - values.begin()) << '\n';
    if (it != values.end()) {
        std::cout << "value=" << *it << '\n';
    }
    const auto end = std::upper_bound(values.begin(), values.end(), 7);
    std::cout << "at_end=" << std::boolalpha << (end == values.end()) << '\n';
}

Резултат

index=4
value=4
at_end=true

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници