equal_range
Dato un intervallo ordinato, trova il sottosistema in cui tutti gli elementi sono equivalenti a un valore specificato.
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
);
Parametri
first
Un iteratore avanti destinato alla posizione del primo elemento nell'intervallo da rilevare.last
Un iteratore avanti destinato alla posizione una dopo l'elemento finale nell'intervallo da rilevare.val
Il valore trovato nell'intervallo ordinato.comp
Oggetto definito dall'utente di funzione predicativa in cui viene definito il concetto cui è minore di un'altra.
Valore restituito
Una coppia degli iteratori avanti che specificano un sottosistema, contenuto nell'intervallo trovato, in cui tutti gli elementi sono equivalenti a val nel senso definito dal predicato utilizzato binario ( comp o l'impostazione predefinita, minore di.).
Se non esistono elementi dell'intervallo equivalenti a val, la coppia restituita gli iteratori avanti è uguale e specifica il punto in cui val è possibile inserire senza pregiudicare l'ordine dell'intervallo.
Note
Il primo iteratore della coppia restituita dall'algoritmo è lower_bounde il secondo iteratore è upper_bound.
L'intervallo deve essere ordinati in base al predicato assegnato a equal_range.Ad esempio, se si utilizza il predicato maggiore di, l'intervallo deve essere ordinato in ordine decrescente.
Gli elementi del sottosistema possibilmente vuota definiti da una coppia degli iteratori restituiti da equal_range sono equivalenti a val nel senso definito dal predicato utilizzato.
La complessità dell'algoritmo è in caso contrario logaritmica per gli iteratori di accesso casuale e lineare, con il numero di passaggi proporzionali alast (– first).
Esempio
// 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" );
}
Requisiti
intestazione: <algorithm>
Spazio dei nomi: deviazione standard