home | help 
std::equal_range(3)	       C++ Standard Libary	     std::equal_range(3)

NAME
     std::equal_range - std::equal_range

Synopsis
	Defined in header <algorithm>
	template< class ForwardIt, class T >
							   (constexpr since
	std::pair<ForwardIt, ForwardIt> 		   C++20)
							   (until C++26)
	    equal_range( ForwardIt first,
	ForwardIt last, const T& value );
	template< class ForwardIt, class T =
	typename std::iterator_traits

	 <ForwardIt>::value_type >			   (since C++26)
	constexpr std::pair<ForwardIt, ForwardIt>

	    equal_range( ForwardIt first,
	ForwardIt last, const T& value );
	template< class ForwardIt, class T, class
	Compare >
						   (1)
	std::pair<ForwardIt,					      ForwardIt>
     (constexpr since
	    equal_range(		    ForwardIt			  first,
     C++20)
	ForwardIt last, 						    (un-
     til C++26)

			 const T& value, Compare
	comp );
	template< class ForwardIt, class T =
	typename std::iterator_traits		       (2)

	 <ForwardIt>::value_type,
		  class 			Compare 		       >
     (since C++26)
	constexpr std::pair<ForwardIt, ForwardIt>
	    equal_range( ForwardIt first,
	ForwardIt last,

			 const T& value, Compare
	comp );

	Returns a range containing all elements equivalent to value in the  par-
     titioned range
	[first, last).

	1) The equivalence is checked using operator<:

	Returns the results of std::lower_bound(first, last, value) and
	std::upper_bound(first, last, value).

	If any of the following conditions is satisfied, the behavior is
	undefined:
     (until C++20)

	  * For any element elem of [first, last), bool(elem < value) does not
	    imply !bool(value < elem).
	  * The elements elem of [first, last) are not partitioned with
	    respect to expressions bool(elem < value) and !bool(value < elem).
	Equivalent   to   std::equal_range(first,   last,  value,  std::less{}).
     (since C++20)

	2) The equivalence is checked using comp:
	Returns the results of std::lower_bound(first, last, value, comp) and
	std::upper_bound(first, last, value, comp).
	If any of the following conditions is satisfied, the behavior  is  unde-
     fined:
	  *  For any element elem of [first, last), bool(comp(elem, value)) does
     not imply
	    !bool(comp(value, elem)).
	  * The elements elem of [first, last) are not partitioned with  respect
     to
	    expressions bool(comp(elem, value)) and !bool(comp(value, elem)).

Parameters
	first, last - the partitioned range of elements to examine
	value	    - value to compare the elements to
		      binary  predicate which returns true if the first argument
     is ordered
		      before the second.

		      The signature of the predicate function should be  equiva-
     lent to the
		      following:

		       bool pred(const Type1 &a, const Type2 &b);

	comp	     -	While  the  signature does not need to have const &, the
     function must
		      not modify the objects passed to it and must  be	able  to
     accept all
		      values of type (possibly const) Type1 and Type2 regardless
     of value
		      category (thus, Type1 & is not allowed
		      ,  nor is Type1 unless for Type1 a move is equivalent to a
     copy
		      (since C++11)).
		      The types Type1 and Type2 must be such that an  object  of
     type T can be
		      implicitly  converted  to both Type1 and Type2, and an ob-
     ject of type
		      ForwardIt can be dereferenced  and  then	implicitly  con-
     verted to both
		      Type1 and Type2.

Type requirements
	-
	ForwardIt must meet the requirements of LegacyForwardIterator.
	-
	Compare  must  meet  the  requirements of BinaryPredicate. It is not re-
     quired to satisfy
	Compare.

Return value
	A std::pair containing a pair of iterators, where

	  * first is an iterator to the first element of the range [first, last)
     not ordered
	    before value (or last if no such element is found), and
	  * second is an iterator to the first	element  of  the  range  [first,
     last) ordered
	    after value (or last if no such element is found).

Complexity
	Given \(\scriptsize N\)N as std::distance(first, last):

	1) At most \(\scriptsize 2\log_{2}(N)+O(1)\)2log
	2(N)+O(1) comparisons with value using
	operator<
	(until C++20)
	std::less{}
	(since C++20).
	2) At most \(\scriptsize 2\log_{2}(N)+O(1)\)2log
	2(N)+O(1) applications of the comparator comp.

	However, if ForwardIt is not a LegacyRandomAccessIterator, the number of
     iterator
	increments  is	linear	in  \(\scriptsize  N\)N.  Notably,  std::set and
     std::multiset
	iterators  are	not  random  access,  and  so  their  member   functions
     std::set::equal_range
	(resp. std::multiset::equal_range) should be preferred.

Notes
	Although std::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 any value.

	On top of the requirements of std::lower_bound and std::upper_bound,
	std::equal_range also requires operator< or comp to be asymmetric (i.e.,
     a < b and b
	< a always have different results).

	Therefore, the intermediate results of binary search can be shared by
	std::lower_bound and std::upper_bound. For example, the result of the
	std::lower_bound call can be used  as  the  argument  of  first  in  the
     std::upper_bound
	call.

		  Feature-test macro	       Value	Std		 Feature
	__cpp_lib_algorithm_default_value_type	202403	(C++26) List-initializa-
     tion for
							      algorithms (1,2)

Possible implementation
				       equal_range (1)
	template<class ForwardIt,
		 class T = typename std::iterator_traits<ForwardIt>::value_type>
	constexpr std::pair<ForwardIt, ForwardIt>
	    equal_range(ForwardIt first, ForwardIt last, const T& value)
	{
	    return std::equal_range(first, last, value, std::less{});
	}
				       equal_range (2)
	template<class ForwardIt,
		 class T = typename std::iterator_traits<ForwardIt>::value_type,
		 class Compare>
	constexpr std::pair<ForwardIt, ForwardIt>
	    equal_range(ForwardIt first, ForwardIt last, const T& value, Compare
     comp)
	{
	    return std::make_pair(std::lower_bound(first, last, value, comp),
				  std::upper_bound(first, last, value, comp));
	}

Example
     // Run this code

      #include <algorithm>
      #include <complex>
      #include <iostream>
      #include <vector>

      struct S
      {
	  int number;
	  char name;
	  // note: name is ignored by this comparison operator
	  bool 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 below
	  const std::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<(): ";
	  const auto 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: ";
	  const auto 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_type
	      auto p3 =  std::equal_range(nums.cbegin(),  nums.cend(),	{2,  0},
     cmpz);
	  #else
	      auto  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';
      }

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

	Defect reports

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

	  DR	 Applied to	 Behavior as published		     Correct be-
     havior
			   Compare was required to satisfy  only a  partitioning
     is required;
	LWG  270  C++98      Compare and T was required       heterogeneous com-
     parisons
			   to be LessThanComparable (strict permitted
			   weak ordering required)
			   at most \(\scriptsize
			   2\log_{2}(N)+1\)2log 		corrected     to
     \(\scriptsize
	LWG	     384	  C++98 	      2(N)+1	     comparisons
     2\log_{2}(N)+O(1)\)2log
			   were allowed, which is not	    2(N)+O(1)
			   implementable^[1]

	 1. a Applying equal_range to a single-element range requires 2  compar-
     isons, but at
	    most 1 comparison is allowed by the complexity requirement.

See also
			    returns  an  iterator  to the first element not less
     than the given
	lower_bound	    value
			    (function template)
			    returns an iterator to  the  first	element  greater
     than a certain
	upper_bound	    value
			    (function template)
	binary_search	     determines  if an element exists in a partially-or-
     dered range
			    (function template)
	partition	    divides a range of elements into two groups
			    (function template)
	equal		    determines if two sets of elements are the same
			    (function template)
			    returns range of elements matching a specific key
	equal_range	    (public member function of	std::set<Key,Compare,Al-
     locator>)

			    returns range of elements matching a specific key
	equal_range	     (public  member  function of std::multiset<Key,Com-
     pare,Allocator>)

	ranges::equal_range returns range of elements matching a specific key
	(C++20) 	    (niebloid)

http://cppreference.com 	   2024.06.10		     std::equal_range(3)
home | help