std::upper_bound

Материал из cppreference.com

This page has been machine-translated from the English version of the wiki using Google Translate.

The translation may contain errors and awkward wording. Hover over text to see the original version. You can help to fix errors and improve the translation. For instructions click here.

Заголовочный файл `<algorithm>`

template< class ForwardIt, class T > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );	(1)

template< class ForwardIt, class T, class Compare > ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

Возвращает итератор, указывающий на первый элемент в диапазоне [first, last) то есть' больше, чем value. Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp.
Original:
Returns an iterator pointing to the first element in the range [first, last) that is greater than value. The first version uses operator< to compare the elements, the second version uses the given comparison function comp.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Параметры

first, last

-

диапазон элементов для изучения

value

-

Значение для сравнения элементов

comp

-

comparison function which returns true if the first argument is less than the second.

The signature of the comparison function should be equivalent to the following:


bool cmp(const Type1 &a, const Type2 &b);

The signature does not need to have const &, but the function must not modify the objects passed to it.
The type Type1 must be such that an object of type T can be implicitly converted to Type1. The type Type2 must be such that an object of type ForwardIt can be dereferenced and then implicitly converted to Type2.

Type requirements

-

ForwardIt must meet the requirements of ForwardIterator.

[править] Возвращаемое значение

итератор, указывающий на первый элемент, больший', чем value, или last, если такой элемент не найден.
Original:
iterator pointing to the first element that is greater than value, or last if no such element is found.
The text has been machine-translated via Google Translate.
You can help to correct and verify the translation. Click here for instructions.

[править] Возможная реализация

First version

template<class ForwardIt, class T>
ForwardIt upper_bound(ForwardIt first, ForwardIt last,
                            const T& value)
{
    ForwardIt it;
    std::iterator_traits<ForwardIt>::distance_type count, step;
    count = std::distance(first,last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (!(value < *it)) {
            first = ++it;
            count -= step + 1;
        } else count = step;
    }
    return first;
}

Second version

template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last,
                            const T& value, Compare comp)
{
    ForwardIt it;
    std::iterator_traits<ForwardIt>::distance_type count, step;
    count = std::distance(first,last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (!comp(value, *it)),
            first = ++it;
            count -= step + 1
        } else count = step;
    }
    return first;
}

[править] Пример

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
int main()
{
    std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };
 
    auto lower = std::lower_bound(data.begin(), data.end(), 4);
    auto upper = std::upper_bound(data.begin(), data.end(), 4);
 
    std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
}

Вывод:

4 4 4

[править] Сложность

логарифмический расстояние между first и last

[править] См. также


equal_range	возвращает набор элементов для конкретного ключа Original: returns range of elements matching a specific key The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

lower_bound	возвращает итератор на первый элемент' не менее, чем заданное значение Original: returns an iterator to the first element not less than the given value The text has been machine-translated via Google Translate. You can help to correct and verify the translation. Click here for instructions. (шаблон функции) [edit]

Язык
Понятия
Утилиты библиотеки
Струны библиотеки
Контейнеры библиотеки
Алгоритмы библиотеки
Итераторы библиотеки
Numerics библиотеки
Библиотеки ввода / вывода
Локализация библиотеки
Библиотеки регулярных выражений (C++11)
Атомная библиотеке операций (C++11)
Библиотека тему поддержки (C++11)

cppreference.com

Поиск

Пространства имён

Варианты

Просмотры

Действия