std::equal_range

Материал из 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 > 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

-

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

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.

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

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

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

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

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

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

First version

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));
}

Second version

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

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

{{dcl list tfun | cpp/algorithm/binary_search |определяет, находится ли элемент в некотором диапазоне


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]

upper_bound	возвращает итератор на первый элемент' больше, чем определенное значение Original: returns an iterator to the first element greater than a certain 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

Поиск

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

Варианты

Просмотры

Действия