equal_range

Artikel
06/09/2015

Bei einem sortierten Bereich wird der Unterbereich gesucht, in dem alle Elemente einem angegebenen Wert entsprechen.

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

Parameter

first
Ein Forward-Iterator, der die Position des ersten Elements im zu durchsuchenden Bereich adressiert.
last
Ein Forward-Iterator, der die Position hinter dem letzten Element im zu durchsuchenden Bereich adressiert.
val
Der Wert, nach dem im sortierten Bereich gesucht wird.
comp
Benutzerdefiniertes Prädikatfunktionsobjekt, das den Sinn definiert, in dem ein Element kleiner als ein anderes ist.

Rückgabewert

Ein Paar Forward-Iteratoren, die einem Unterbereich angeben, der im durchsuchten Bereich enthalten ist, in dem alle Elemente val in dem Sinne entsprechen, wie vom verwendeten binären Prädikat definiert wird (entweder comp oder Standard bzw. geringer als).

Wenn in dem Bereich keine Elemente val entsprechen, ist das zurückgegebene Paare von Forward-Iteratoren gleich, und es gibt den Punkt an, an dem val eingefügt werden kann, ohne die Reihenfolge des Bereichs zu beeinträchtigen.

Hinweise

Der erste Iterator des vom Algorithmus zurückgegebenen Paars ist lower_bound, der zweite Iterator ist upper_bound.

Der Bereich muss dem für equal_range bereitgestellten Prädikat entsprechend sortiert werden. Wenn Sie z. B: das Prädikat "größer als" verwenden, muss der Bereich in absteigender Reihenfolge sortiert werden.

Elemente im möglicherweise leeren Unterbereich, der vom Iteratorpaar definiert wird, das von equal_range zurückgegeben wird, entspricht val in dem vom verwendeten Prädikat definierten Sinn.

Die Komplexität dieses Algorithmus ist bei Zufallszugriffsiteratoren logarithmisch und andernfalls linear. Dabei ist eine Anzahl von Schritten proportional zu (last – first)

Beispiel

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

Ausgabe

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