equal_range

Artykuł
06/09/2015

Mając uporządkowany zakres, odnajduje podzakres, w którym wszystkie elementy są równoważne danej wartości.

template<class ForwardIterator, class Type>
   pair<ForwardIterator, ForwardIterator> equal_range(
      ForwardIterator first,
      ForwardIterator last, 
      const Type& val
   );
template<class ForwardIterator, class Type, class Predicate>
   pair<ForwardIterator, ForwardIterator> equal_range(
      ForwardIterator first,
      ForwardIterator last, 
      const Type& val, 
      Predicate comp
   );

Parametry

first
Iterator postępujący odnosi się do pozycji pierwszego elementu w zakresie wyszukiwania.
last
Iterator postępujący odnosi się do pozycji pierwszej po elemencie końcowym w zakresie wyszukiwania.
val
Wartość wyszukiwana w zakresie uporządkowanym.
comp
Zdefiniowany przez użytkownika obiekt funkcji predykatu, który definiuje sens, w którym jeden element jest mniejszy niż inny.

Wartość zwracana

Para iteratorów postępujących, która określa podzakres, zawarty w zakresie wyszukiwania, w którym wszystkie elementy są równoważne z val w znaczeniu zdefiniowanym przez używany predykat dwuelementowy (albo comp, albo domyślnie mniej niż).

Jeśli żadne elementy w zakresie nie są równe parametrowi val, zwrócona para iteratorów do przodu jest równa i określa punkt, gdzie parametr val może być wstawiony bez naruszania porządku zakresu.

Uwagi

Pierwszym iteratorem pary zwróconej przez algorytm jest lower_bound, a drugim jest upper_bound.

Zakres musi być sortowany zgodnie z predykatem dla equal_range.Na przykład jeśli zamierzasz użyć predykatu większe niż, zakres musi być sortowany w kolejności malejącej.

Elementy w możliwym pustym podzakresie zdefiniowane przez parę iteratorów zwróconych przez equal_range będą równoważne z val w znaczeniu zdefiniowanym przez używany predykat.

Złożoność algorytmu jest logarytmiczna dla iteratorów dostępu liniowego i liniowa w przeciwnym razie z liczbą kroków proporcjonalną do (last – first).

Przykład

// alg_equal_range.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      // greater<int>()
#include <iostream>
#include <string>
using namespace std;

template<class T> void dump_vector( const vector<T>& v, pair< typename vector<T>::iterator, typename vector<T>::iterator > range )
{
    // prints vector v with range delimited by [ and ]

    for( typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
    {
        if( i == range.first )
        {
            cout << "[ ";
        }
        if( i == range.second )
        {
            cout << "] ";
        }

        cout << *i << " ";
    }
    cout << endl;
}

template<class T> void equal_range_demo( const vector<T>& original_vector, T val )
{
    vector<T> v(original_vector);

    sort( v.begin(), v.end() );
    cout << "Vector sorted by the default binary predicate <:" << endl << '\t';
    for( vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
    {
        cout << *i << " ";
    }
    cout << endl << endl;

    pair< vector<T>::iterator, vector<T>::iterator > result
        = equal_range( v.begin(), v.end(), val );

    cout << "Result of equal_range with val = " << val << ":" << endl << '\t';
    dump_vector( v, result );
    cout << endl;
}

template<class T, class F> void equal_range_demo( const vector<T>& original_vector, T val, F pred, string predname )
{
    vector<T> v(original_vector);

    sort( v.begin(), v.end(), pred );
    cout << "Vector sorted by the binary predicate " << predname << ":" << endl << '\t';
    for( typename vector<T>::const_iterator i = v.begin(); i != v.end(); ++i )
    {
        cout << *i << " ";
    }
    cout << endl << endl;

    pair< typename vector<T>::iterator, typename vector<T>::iterator > result
        = equal_range( v.begin(), v.end(), val, pred );

    cout << "Result of equal_range with val = " << val << ":" << endl << '\t';
    dump_vector( v, result );
    cout << endl;
}

// Return whether absolute value of elem1 is less than absolute value of elem2
bool abs_lesser( int elem1, int elem2 )
{
    return abs(elem1) < abs(elem2);
}

// Return whether string l is shorter than string r
bool shorter_than(const string& l, const string& r)
{
    return l.size() < r.size();
}

int main()
{
    vector<int> v1;

    // Constructing vector v1 with default less than ordering
    for( int i = -1; i <= 4; ++i )
    {
        v1.push_back(i);
    }

    for( int i =-3; i <= 0; ++i )
    {
        v1.push_back( i );
    }

    equal_range_demo( v1, 3 );
    equal_range_demo( v1, 3, greater<int>(), "greater" );
    equal_range_demo( v1, 3, abs_lesser, "abs_lesser" );

    vector<string> v2;

    v2.push_back("cute");
    v2.push_back("fluffy");
    v2.push_back("kittens");
    v2.push_back("fun");
    v2.push_back("meowmeowmeow");
    v2.push_back("blah");

    equal_range_demo<string>( v2, "fred" );
    equal_range_demo<string>( v2, "fred", shorter_than, "shorter_than" );
}

Dane wyjściowe

Vector sorted by the default binary predicate <:
        -3 -2 -1 -1 0 0 1 2 3 4

Result of equal_range with val = 3:
        -3 -2 -1 -1 0 0 1 2 [ 3 ] 4

Vector sorted by the binary predicate greater:
        4 3 2 1 0 0 -1 -1 -2 -3

Result of equal_range with val = 3:
        4 [ 3 ] 2 1 0 0 -1 -1 -2 -3

Vector sorted by the binary predicate abs_lesser:
        0 0 -1 1 -1 2 -2 3 -3 4

Result of equal_range with val = 3:
        0 0 -1 1 -1 2 -2 [ 3 -3 ] 4

Vector sorted by the default binary predicate <:
        blah cute fluffy fun kittens meowmeowmeow

Result of equal_range with val = fred:
        blah cute fluffy [ ] fun kittens meowmeowmeow

Vector sorted by the binary predicate shorter_than:
        fun cute blah fluffy kittens meowmeowmeow

Result of equal_range with val = fred:
        fun [ cute blah ] fluffy kittens meowmeowmeow