Returns a range containing all elements equivalent tovalue in the partitioned range[first, last).

[edit]Parameters

[edit]Return value

Astd::pair containing a pair of iterators, where

• first is an iterator to the first element of the range[first, last) not ordered beforevalue (orlast if no such element is found), and
• second is an iterator to the first element of the range[first, last) ordered aftervalue (orlast if no such element is found).

[edit]Complexity

Given\(\scriptsize N\)N asstd::distance(first, last):

However, ifForwardIt is not aLegacyRandomAccessIterator, the number of iterator increments is linear in\(\scriptsize N\)N. Notably,std::set andstd::multiset iterators are not random access, and so their member functionsstd::set::equal_range (resp.std::multiset::equal_range) should be preferred.

[edit]Notes

Althoughstd::equal_range only requires[first, last) to be partitioned, this algorithm is usually used in the case where[first, last) is sorted, so that the binary search is valid for anyvalue.

On top of the requirements ofstd::lower_bound andstd::upper_bound,std::equal_range also requiresoperator< orcomp to be asymmetric (i.e.,a< b andb< a always have different results).

Therefore, the intermediate results of binary search can be shared bystd::lower_bound andstd::upper_bound. For example, the result of thestd::lower_bound call can be used as the argument offirst in thestd::upper_bound call.

[edit]Possible implementation

template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::value_type>constexprstd::pair<ForwardIt, ForwardIt>     equal_range(ForwardIt first, ForwardIt last,const T& value){return std::equal_range(first, last, value,std::less{});}

template<class ForwardIt,class T=typenamestd::iterator_traits<ForwardIt>::value_type,class Compare>constexprstd::pair<ForwardIt, ForwardIt>    equal_range(ForwardIt first, ForwardIt last,const T& value, Compare comp){returnstd::make_pair(std::lower_bound(first, last, value, comp),std::upper_bound(first, last, value, comp));}

[edit]Example

#include <algorithm>#include <complex>#include <iostream>#include <vector> struct S{int number;char name;// note: name is ignored by this comparison operatorbool operator<(const S& s)const{return number< s.number;}}; struct Comp{bool operator()(const S& s,int i)const{return s.number< i;}bool operator()(int i,const S& s)const{return i< s.number;}}; int main(){// note: not ordered, only partitioned w.r.t. S defined belowconststd::vector<S> vec{{1,'A'},{2,'B'},{2,'C'},{2,'D'},{4,'G'},{3,'F'}};const S value{2,'?'}; std::cout<<"Compare using S::operator<(): ";constauto p= std::equal_range(vec.begin(), vec.end(), value); for(auto it= p.first; it!= p.second;++it)std::cout<< it->name<<' ';std::cout<<'\n'; std::cout<<"Using heterogeneous comparison: ";constauto p2= std::equal_range(vec.begin(), vec.end(),2, Comp{}); for(auto it= p2.first; it!= p2.second;++it)std::cout<< it->name<<' ';std::cout<<'\n'; using CD=std::complex<double>;std::vector<CD> nums{{1,0},{2,2},{2,1},{3,0},{3,1}};auto cmpz=[](CD x, CD y){return x.real()< y.real();};#ifdef __cpp_lib_algorithm_default_value_typeauto p3= std::equal_range(nums.cbegin(), nums.cend(),{2,0}, cmpz);#elseauto p3= std::equal_range(nums.cbegin(), nums.cend(), CD{2,0}, cmpz);#endif for(auto it= p3.first; it!= p3.second;++it)std::cout<<*it<<' ';std::cout<<'\n';}

Compare using S::operator<(): B C D Using heterogeneous comparison: B C D(2,2) (2, 1)

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

1. ↑Applyingequal_range to a single-element range requires 2 comparisons, but at most 1 comparison is allowed by the complexity requirement.

[edit]See also

• In other languages

• Deutsch
• Español
• Français
• Italiano
• 日本語
• Português
• Русский
• 中文