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

NAME
     std::ranges::equal_range - std::ranges::equal_range

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::forward_iterator I, std::sentinel_for<I> S,

		  class T, class Proj = std::identity,
		  std::indirect_strict_weak_order
     (since
		      <const	 T*,	std::projected<I,    Proj>>    Comp    =
     C++20)
	ranges::less							       >
     (until
	constexpr    ranges::subrange<I>   equal_range(   I   first,   S   last,
     C++26)
	const T& value,

						   Comp comp = {},
	Proj proj = {} );
	template< std::forward_iterator I, std::sentinel_for<I> S,

		  class Proj = std::identity,
		  class T = std::projected_value_t<I, Proj>,
		  std::indirect_strict_weak_order
		      <const	T*,    std::projected<I,    Proj>>    Comp     =
     (since
	ranges::less							       >
     C++26)
	constexpr ranges::subrange<I> equal_range( I first, S last,
	const T& value,

						   Comp comp = {},
	Proj proj = {} );
	template< ranges::forward_range R,
								     (1)
		  class T, class Proj = std::identity,
		  std::indirect_strict_weak_order
		      <const						     T*,
     (since
	std::projected<ranges::iterator_t<R>,
     C++20)
						Proj>>		 Comp	       =
     (until
	ranges::less							       >
     C++26)
	constexpr ranges::borrowed_subrange_t<R>

	    equal_range( R&& r, const T& value, Comp comp = {}, Proj
	proj = {} );
	template< ranges::forward_range R,				 (2)

		  class Proj = std::identity,
		  class T =
	std::projected_value_t<ranges::iterator_t<R>, Proj>,
		  std::indirect_strict_weak_order
		      <const						     T*,
     (since
	std::projected<ranges::iterator_t<R>,
     C++26)
						Proj>> Comp =
	ranges::less >
	constexpr ranges::borrowed_subrange_t<R>

	    equal_range( R&& r, const T& value, Comp comp = {}, Proj
	proj = {} );

	1) Returns a view containing all elements equivalent  to  value  in  the
     range
	[first, last).

	The  range [first, last) must be at least partially ordered with respect
     to value,
	i.e. it must satisfy all of the following requirements:

	  * partitioned with respect to element < value or comp(element,  value)
     (that is,
	    all  elements for which the expression is true precedes all elements
     for which
	    the expression is false).
	  * partitioned with respect to !(value < element) or !comp(value,  ele-
     ment).
	  * for all elements, if element < value or comp(element, value) is true
     then
	    !(value < element) or !comp(value, element) is also true.

	A fully-sorted range meets these criteria.

	The returned view is constructed from two iterators, one pointing to the
     first
	element  that  is  not less than value and another pointing to the first
     element
	greater than value. The first iterator	may  be  alternatively	obtained
     with
	std::ranges::lower_bound(),   the   second   -	 with	std::ranges::up-
     per_bound().

	2) Same as (1), but uses r as the source range, as if using the range
	ranges::begin(r) as first and ranges::end(r) as last.

	The function-like entities described on this page  are	niebloids,  that
     is:

	  *  Explicit  template  argument lists cannot be specified when calling
     any of them.
	  * None of them are visible to argument-dependent lookup.
	  * When any of them are found by normal unqualified lookup as the  name
     to the left
	    of	the  function-call operator, argument-dependent lookup is inhib-
     ited.

	In practice, they may be implemented as function objects, or  with  spe-
     cial compiler
	extensions.

Parameters
	first, last - the range of elements to examine
	r	    - the range of the elements to examine
	value	    - value to compare the elements to
	comp	     -	if  the first argument is less than (i.e. is ordered be-
     fore) the second
	proj	    - projection to apply to the elements

Return value
	std::ranges::subrange containing a pair of iterators defining the wanted
     range, the
	first pointing to the first element that is not less than value and  the
     second
	pointing to the first element greater than value.

	If  there are no elements not less than value, the last iterator (itera-
     tor that is
	equal to last or ranges::end(r)) is returned as the first element. Simi-
     larly if
	there are no elements greater than value, the last iterator is	returned
     as the
	second element.

Complexity
	The  number  of comparisons performed is logarithmic in the distance be-
     tween first and
	last (at most 2 * log
	2(last - first) + O(1) comparisons). However, for an iterator that  does
     not model
	random_access_iterator, the number of iterator increments is linear.

Possible implementation
      struct equal_range_fn
      {
	  template<std::forward_iterator I, std::sentinel_for<I> S,
		   class   Proj   =   std::identity,   class   T   =   std::pro-
     jected_value_t<I, Proj>,
		   std::indirect_strict_weak_order
		       <const T*, std::projected<I, Proj>> Comp = ranges::less>
	  constexpr ranges::subrange<I>
	      operator()(I first, S last, const T& value, Comp comp =  {},  Proj
     proj = {}) const
	  {
	      return ranges::subrange
	      (
		  ranges::lower_bound(first,	last,	value,	 std::ref(comp),
     std::ref(proj)),
		  ranges::upper_bound(first,   last,   value,	 std::ref(comp),
     std::ref(proj))
	      );
	  }

	  template<ranges::forward_range R, class Proj = std::identity,
		   class   T   =   std::projected_value_t<ranges::iterator_t<R>,
     Proj>,
		   std::indirect_strict_weak_order
		       <const T*, std::projected<ranges::iterator_t<R>,
						 Proj>> Comp = ranges::less>
	  constexpr ranges::borrowed_subrange_t<R>
	      operator()(R&& r, const T& value, Comp comp = {}, Proj proj =  {})
     const
	  {
	      return (*this)(ranges::begin(r), ranges::end(r), value,
			     std::ref(comp), std::ref(proj));
	  }
      };

      inline constexpr equal_range_fn equal_range;

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

Example
     // Run this code

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

      struct S
      {
	  int number {};
	  char name {};
	  // note: name is ignored by these comparison operators
	  friend bool operator== (const S s1, const S s2) { return s1.number  ==
     s2.number; }
	  friend auto operator<=>(const S s1, const S s2) { return s1.number <=>
     s2.number; }
	  friend std::ostream& operator<<(std::ostream& os, S o)
	  {
	      return os << '{' << o.number << ", '" << o.name << "'}";
	  }
      };

      void println(auto rem, const auto& v)
      {
	  for (std::cout << rem; const auto& e : v)
	      std::cout << e << ' ';
	  std::cout << '\n';
      }

      int main()
      {
	  // note: not ordered, only partitioned w.r.t. S defined below
	  std::vector<S> vec
	  {
	      {1,'A'}, {2,'B'}, {2,'C'}, {2,'D'}, {4, 'D'}, {4,'G'}, {3,'F'}
	  };

	  const S value{2, '?'};

	  namespace ranges = std::ranges;

	  auto a = ranges::equal_range(vec, value);
	  println("1. ", a);

	  auto b = ranges::equal_range(vec.begin(), vec.end(), value);
	  println("2. ", b);

	  auto c = ranges::equal_range(vec, 'D', ranges::less {}, &S::name);
	  println("3. ", c);

	  auto d = ranges::equal_range(vec.begin(), vec.end(), 'D', ranges::less
     {}, &S::name);
	  println("4. ", d);

	  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 = ranges::equal_range(nums, {2, 0}, cmpz);
	  #else
	      auto p3 = ranges::equal_range(nums, CD{2, 0}, cmpz);
	  #endif
	  println("5. ", p3);
      }

Output:
      1. {2, 'B'} {2, 'C'} {2, 'D'}
      2. {2, 'B'} {2, 'C'} {2, 'D'}
      3. {2, 'D'} {4, 'D'}
      4. {2, 'D'} {4, 'D'}
      5. (2,2) (2,1)

See also
	ranges::lower_bound    returns an iterator to the first element not less
     than the
	(C++20) 	      given value
			      (niebloid)
	ranges::upper_bound   returns an iterator to the first	element  greater
     than a
	(C++20) 	      certain value
			      (niebloid)
	ranges::binary_search determines if an element exists in a partially-or-
     dered range
	(C++20) 	      (niebloid)
	ranges::partition     divides a range of elements into two groups
	(C++20) 	      (niebloid)
	ranges::equal	      determines if two sets of elements are the same
	(C++20) 	      (niebloid)
	equal_range	      returns range of elements matching a specific key
			      (function template)

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