std::equal_range

Эта страница была переведена автоматически с английской версии вики используя Переводчик Google.

Перевод может содержать ошибки и странные формулировки. Наведите курсор на текст, чтобы увидеть оригинал. Вы можете помочь в исправлении ошибок и улучшении перевода. Для инструкций перейдите по ссылке.

Щёлкните здесь, чтобы увидеть английскую версию этой страницы

Определено в заголовочном файле `<algorithm>`
template< class ForwardIt, class T > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value );	(1)
template< class ForwardIt, class T, class Compare > std::pair<ForwardIt,ForwardIt> equal_range( ForwardIt first, ForwardIt last, const T& value, Compare comp );	(2)

Возвращает диапазон, содержащий все элементы равны value в отсортированном диапазоне [first, last). Диапазон определяется двумя итераторы, один, указывающий на первый элемент, который является' не меньше, чем value и другое указывает на первый элемент' больше, чем value. Первый итератор может быть альтернативно, полученные с lower_bound(), второй - с upper_bound().

Первый вариант используется operator< для сравнения элементов, вторая версия использует данную функцию сравнения comp.

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

first, last	-	диапазон элементов для изучения Оригинал: the range of elements to examine Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
value	-	Значение для сравнения элементов Оригинал: value to compare the elements to Текст был переведён автоматически используя Переводчик Google. Вы можете проверить и исправить перевод. Для инструкций щёлкните сюда.
comp	-	функция сравнения, возвращающая true если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: bool cmp(const Type1 &a, const Type2 &b); Сигнатура на обязана содержать const &, однако, функция не может изменять переданные объекты. Тип Type1 должен быть таков, что объект типа T может быть неявно преобразован в Type1. Тип Type2 должен быть таков, что объект типа ForwardIt может быть разыменован и затем неявно преобразован в Type2.
Требования к типам
- `ForwardIt` должен соответствовать требованиям `ForwardIterator`.

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

std::pair содержащий пару итераторов определении нужного диапазона, первое, указывающий на первый элемент, который является' не меньше, чем value, а второй указывает на первый элемент' больше, чем value.

Если нет элементов' не менее чем value, last возвращается в качестве первого элемента. Аналогично, если нет элементов' больше, чем value, last возвращается в качестве второго элемента

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

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

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

Первый вариант

template<class ForwardIt, class T
std::pair<ForwardIt,ForwardIt>
    equal_range(ForwardIt first, ForwardIt last,
                const T& value)
{
    return std::make_pair(std::lower_bound(first, last, value),
                          std::upper_bound(first, last, value));
}

Второй вариант

template<class ForwardIt, class T, class Compare>
std::pair<ForwardIt,ForwardIt>
    equal_range(ForwardIt first, ForwardIt last,
                const T& value, Compare comp);
{
    return std::make_pair(std::lower_bound(first, last, value, comp),
                          std::upper_bound(first, last, value, comp));
}

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

Запустить этот код

#include <algorithm>
#include <vector>
#include <iostream>
 
struct S
{
    int number;
    char name;
 
    S ( int number, char name  )
        : number ( number ), name ( name )
    {}
 
    // only the number is relevant with this comparison
    bool operator< ( const S& s ) const
    {
        return number < s.number;
    }
};
 
 
int main()
{
    std::vector<S> vec = { {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {3,'F'}, {4,'G'} };
 
    S value ( 2, '?' );
 
    auto p = std::equal_range(vec.begin(),vec.end(),value);
 
    for ( auto i = p.first; i != p.second; ++i )
        std::cout << i->name << ' ';
}

Вывод:

B C D

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


lower_bound	то же самое что и upper_bound (шаблон функции) [править]

upper_bound	то же самое что и lower_bound (шаблон функции) [править]

binary_search	определяет, находится ли элемент в некотором диапазоне (шаблон функции) [править]

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

cppreference.com

Поиск

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

Варианты

Просмотры

Действия