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

CKTIS / C++

std::lower_bound — първа позиция, която не е по-малка от ключ

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

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

Синтаксис

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

std::lower_bound, декларирана в <algorithm>, търси в [first, last) и връща първия итератор, за който comp(*it, value) е невярно, или last, ако няма такъв елемент. Ако comp не е зададен, се използва сравнението по подразбиране „по-малко от“. Във възходящ числов диапазон резултатът сочи към първия елемент >= value, включително първото повторение.

Предусловието е диапазонът да е разделен спрямо конкретния ключ: всички елементи, за които е изпълнено comp(element, value), трябва да предхождат останалите. Пълното сортиране със същото сравнение е достатъчно, но не е необходимо. Нарушаването на това условие води до неопределено поведение; функцията не сортира данните.

Резултатът не потвърждава, че ключът съществува. Проверете it != last, преди да използвате *it. В примера с цели числа кодът проверява само it != values.end(), преди да отпечата намерената стойност; той не я сравнява с ключа. След като се уверите, че итераторът не е в края на диапазона, можете отделно да проверите равенството чрез *it == key. При потребителски ред еквивалентност означава !comp(a, b) && !comp(b, a), а не непременно a == b.

Необходими са поне итератори за движение напред. За N елемента броят на сравненията е O(log N), но без итератори с произволен достъп броят на стъпките на итератора може да е линеен. Примерът е предназначен за C++23; свързаният документ е развиващ се работен проект, а не окончателно издание на C++23.

Примери

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

int main() {
    const std::vector<int> values{1, 3, 3, 7};
    for (int key : {3, 4, 9}) {
        const auto it = std::lower_bound(values.begin(), values.end(), key);
        std::cout << key << ": index=" << (it - values.begin());
        if (it != values.end()) {
            std::cout << ", value=" << *it;
        } else {
            std::cout << ", end";
        }
        std::cout << '\n';
    }
}

Резултат

3: index=1, value=3
4: index=3, value=7
9: index=4, end

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

Източници