equal_range

아티클
06/09/2015

정렬된 범위를 감안하여 모든 요소가 지정된 값에 해당하는 하위 범위를 찾습니다.

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

매개 변수

first
검색할 범위에 있는 첫 번째 요소의 위치를 가리키는 정방향 반복기입니다.
last
검색할 범위에 있는 마지막 요소의 하나 뒤 위치를 가리키는 정방향 반복기입니다.
val
순서가 지정된 범위에서 검색한 값입니다.
comp
한 요소가 다른 요소보다 작은 개념을 정의하는 사용자 정의 조건자 함수 개체입니다.

반환 값

검색된 범위 내에 포함된 하위 범위를 지정하는 정방향 반복기의 쌍으로, 모든 요소가 사용된 이진 조건자(comp 또는 기본값, 보다 작음)에 정의된 대로 val와 같습니다.

범위의 요소가 val와 같은 경우 정방향 반복기의 반환된 쌍은 동일하며 범위의 순서를 방해하지 않고 val를 삽입할 수 있는 지점을 지정합니다.

설명

알고리즘에서 반환한 쌍의 첫 번째 반복기는 lower_bound이며 두 번째 반복기는 upper_bound입니다.

범위는 equal_range를 제공된 조건자에 따라 정렬되어야 합니다. 예를 들어, 보다 큼 조건자를 사용하려는 경우 범위는 내림차순으로 정렬되어야 합니다.

equal_range에서 반환된 반복기 쌍에 정의된 빈 하위 범위의 요소는 사용된 조건자에서 정의되었다는 점에서 val와 동일합니다.

알고리즘의 복잡성은 임의 액세스 반복기 및 선형에 대한 로그이며 반대의 경우는 비례하는 단계의 수(last – first)입니다.

예제

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

Output

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