equal_range

Artikel
03/26/2013

Erstellen eines geordneten Gültigkeitsbereich, Suchen den Teilbereich, in dem alle Elemente mit 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 Vorwärtsiterator, der die Position des ersten Elements im Bereich behandelt gefunden werden.
last
Ein Vorwärtsiterator, der die Position eine hinter dem letzten Element im Bereich behandelt gefunden werden.
val
Der Wert, der für in geordnete Bereich gefunden wird.
comp
Benutzerdefiniertes Prädikatfunktionsobjekt, dem dem Sinne definiert, in dem ein Element kleiner als andere.

Rückgabewert

Ein Paar Vorwärtsiteratoren, die einen Teilbereich angeben, enthalten innerhalb des Bereichs gefunden, in dem alle Elemente zu val insofern entsprechen, der durch das verwendete binäre Prädikat definiert wird (entweder comp oder der Standardwert, weniger-als).

Wenn keine Elemente im Bereich zu val äquivalent sind, werden die zurückgegebenen Paare von Vorwärtsiteratoren gleich und geben den Punkt an, in dem val eingefügt werden kann, ohne die Reihenfolge des Bereichs zu beeinträchtigen.

Hinweise

Der erste Iterator der Paaren, die vom Algorithmus zurückgegeben werden, ist lower_bound, der zweite Iterator ist upper_bound.

Der Bereich muss entsprechend dem Prädikat sortiert werden, das zu equal_range bereitgestellt wird.Wenn Sie beispielsweise groß-als Prädikat verwenden, muss der Bereich in absteigender Reihenfolge sortiert werden.

Elemente im möglicherweise leeren Teilbereich, das durch die Paare von den Iteratoren zurückgegeben werden durch equal_range definiert ist, sind zu val insofern entsprechend, der durch das verwendete Prädikat definiert ist.

Die Komplexität des Algorithmus ist logarithmisch für Iteratoren mit wahlfreier Zugriff und andernfalls, mit der Anzahl der Schritte linear, die proportional zu sind (last - first).

Beispiel

// alg_equal_range.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>      //For 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" );
}

Anforderungen

Header: <algorithm>

Namespace: std

Siehe auch

Referenz

Standardvorlagenbibliothek

Freigeben über