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

NAME
     std::ranges::fold_right - std::ranges::fold_right

Synopsis
	Defined in header <algorithm>
	Call signature
	template< std::bidirectional_iterator I,
	std::sentinel_for<I> S, class T,
								      (since
		  /* indirectly-binary-right-foldable */<T,	      C++23)
	I> F >							      (until
								      C++26)
	constexpr auto fold_right( I first, S last, T init, F
	f );
	template< std::bidirectional_iterator I,
	std::sentinel_for<I> S,

		  class T = std::iter_value_t<I>,		      (since
		  /* indirectly-binary-right-foldable */<T,	      C++26)
	I> F >

	constexpr auto fold_right( I first, S last, T init, F
	f );
	template< ranges::bidirectional_range R, class T,
							      (1)
		  /*		 indirectly-binary-right-foldable	      */
     (since C++23)
		      <T,	   ranges::iterator_t<R>>	   F	       >
     (until C++26)

	constexpr auto fold_right( R&& r, T init, F f );
	template< ranges::bidirectional_range R, class T =
	ranges::range_value_t<R>,

		  /*	 indirectly-binary-right-foldable     */	     (2)
     (since C++26)
		      <T, ranges::iterator_t<R>> F >

	constexpr auto fold_right( R&& r, T init, F f );
	Helper concepts
	template<      class	  F,	  class      T,      class	I      >
     (exposition
	concept   /*  indirectly-binary-left-foldable  */  =  /*	     (3)
     only*)
	see description */;
	template<      class	  F,	  class      T,      class	I      >
     (exposition
	concept   /*  indirectly-binary-right-foldable	*/  =  /*	     (4)
     only*)
	see description */;

	Right-folds the elements of given range, that is, returns the result  of
     evaluation
	of the chain expression:
	f(x[1], f(x[2], ...f(x[n], init))), where x[1], x[2], ..., x[n] are ele-
     ments of the
	range.

	Informally,  ranges::fold_right  behaves like std::fold_left(ranges::re-
     verse(r), init,
	/* flipped */(f)).

	The behavior is undefined if [first, last) is not a valid range.

	1) The range is [first, last).
	2) Same as (1), except that  uses  r  as  the  range,  as  if  by  using
     ranges::begin(r) as
	first and ranges::end(r) as last.
	3) Equivalent to:

	Helper concepts
	template< class F, class T, class I, class U >

	concept /*indirectly-binary-left-foldable-impl*/ =
	    std::movable<T> &&
	    std::movable<U> &&
	    std::convertible_to<T, U> &&			     (3A) (expo-
     sition only*)
	    std::invocable<F&, U, std::iter_reference_t<I>> &&
	    std::assignable_from<U&,

		std::invoke_result_t<F&, U,
	std::iter_reference_t<I>>>;
	template< class F, class T, class I >

	concept /*indirectly-binary-left-foldable*/ =
	    std::copy_constructible<F> &&
	    std::indirectly_readable<I> &&
	    std::invocable<F&, T, std::iter_reference_t<I>> &&
	    std::convertible_to<std::invoke_result_t<F&, T,	     (3B) (expo-
     sition only*)
	std::iter_reference_t<I>>,
		std::decay_t<std::invoke_result_t<F&, T,
	std::iter_reference_t<I>>>> &&
	    /*indirectly-binary-left-foldable-impl*/<F, T, I,

		std::decay_t<std::invoke_result_t<F&, T,
	std::iter_reference_t<I>>>>;

	4) Equivalent to:

	Helper concepts
	template< class F, class T, class I >
									    (ex-
     position
	concept   /*indirectly-binary-right-foldable*/	 =		    (4A)
     only*)

	    /*indirectly-binary-left-foldable*/</*flipped*/<F>, T, I>;
	Helper class templates
	template< class F >

	class /*flipped*/
	{
	    F f;    // exposition only					    (ex-
     position
	public: 							    (4B)
     only*)
	    template< class T, class U >
		requires std::invocable<F&, U, T>
	    std::invoke_result_t<F&, U, T> operator()( T&&, U&& );

	};

	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 fold
	r	    - the range of elements to fold
	init	    - the initial value of the fold
	f	    - the binary function object

Return value
	An object of type U that contains the result of right-fold of the  given
     range over
	f, where U is equivalent to std::decay_t<std::invoke_result_t<F&,
	std::iter_reference_t<I>, T>>;.

	If the range is empty, U(std::move(init)) is returned.

Possible implementations
	struct fold_right_fn
	{
	    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
		     class T = std::iter_value_t<I>,
		     /* indirectly-binary-right-foldable */<T, I> F>
	    constexpr auto operator()(I first, S last, T init, F f) const
	    {
		using U = std::decay_t<std::invoke_result_t<F&, std::iter_refer-
     ence_t<I>, T>>;
		if (first == last)
		    return U(std::move(init));
		I tail = ranges::next(first, last);
		U accum = std::invoke(f, *--tail, std::move(init));
		while (first != tail)
		    accum = invoke(f, *--tail, std::move(accum));
		return accum;
	    }

	    template<ranges::bidirectional_range      R,      class	 T     =
     ranges::range_value_t<R>,
		     /*  indirectly-binary-right-foldable  */<T,  ranges::itera-
     tor_t<R>> F>
	    constexpr auto operator()(R&& r, T init, F f) const
	    {
		return	       (*this)(ranges::begin(r),	 ranges::end(r),
     std::move(init), std::ref(f));
	    }
	};

	inline constexpr fold_right_fn fold_right;

Complexity
	Exactly ranges::distance(first, last) applications of the  function  ob-
     ject f.

Notes
	The following table compares all constrained folding algorithms:

	     Fold function template	  Starts Initial	     Return type
					   from   value
	ranges::fold_left		  left	 init	 U
	ranges::fold_left_first 	  left	 first	 std::optional<U>
						 element
	ranges::fold_right		  right  init	 U
	ranges::fold_right_last 	  right  last	 std::optional<U>
						 element
							 (1)
     ranges::in_value_result<I, U>

	ranges::fold_left_with_iter		 left	       init	     (2)
     ranges::in_value_result<BR, U>,

							 where BR is
							 ranges::borrowed_itera-
     tor_t<R>
							 (1)
     ranges::in_value_result<I,
							 std::optional<U>>

	ranges::fold_left_first_with_iter	left	      first	     (2)
     ranges::in_value_result<BR,
						 element std::optional<U>>

							 where BR is
							 ranges::borrowed_itera-
     tor_t<R>

		  Feature-test	macro		  Value    Std		    Fea-
     ture
	__cpp_lib_ranges_fold		       202207L (C++23) std::ranges  fold
     algorithms
	__cpp_lib_algorithm_default_value_type	202403	(C++26) List-initializa-
     tion for
							       algorithms (1,2)

Example
     // Run this code

      #include <algorithm>
      #include <complex>
      #include <functional>
      #include <iostream>
      #include <ranges>
      #include <string>
      #include <utility>
      #include <vector>

      using namespace std::literals;
      namespace ranges = std::ranges;

      int main()
      {
	  auto v = {1, 2, 3, 4, 5, 6, 7, 8};
	  std::vector<std::string> vs{"A", "B", "C", "D"};

	  auto r1 = ranges::fold_right(v.begin(), v.end(), 6, std::plus<>()); //
     (1)
	  std::cout << "r1: " << r1 << '\n';

	  auto r2 = ranges::fold_right(vs, "!"s, std::plus<>()); // (2)
	  std::cout << "r2: " << r2 << '\n';

	  // Use a program defined function object (lambda-expression):
	  std::string r3 = ranges::fold_right
	  (
	      v,  "A",	[](int	x,  std::string  s)  {	return	 s   +	 ':'   +
     std::to_string(x); }
	  );
	  std::cout << "r3: " << r3 << '\n';

	  //  Get  the product of the std::pair::second of all pairs in the vec-
     tor:
	  std::vector<std::pair<char, float>> data{{'A', 2.f}, {'B', 3.f}, {'C',
     3.5f}};
	  float r4 = ranges::fold_right
	  (
	      data | ranges::views::values, 2.0f, std::multiplies<>()
	  );
	  std::cout << "r4: " << r4 << '\n';

	  using CD = std::complex<double>;
	  std::vector<CD> nums{{1, 1}, {2, 0}, {3, 0}};
	  #ifdef __cpp_lib_algorithm_default_value_type
	      auto r5 = ranges::fold_right(nums, {7, 0}, std::multiplies{});
	  #else
	      auto r5 = ranges::fold_right(nums, CD{7, 0}, std::multiplies{});
	  #endif
	  std::cout << "r5: " << r5 << '\n';
      }

Output:
      r1: 42
      r2: ABCD!
      r3: A:8:7:6:5:4:3:2:1
      r4: 42
      r5: (42,42)

References
	  * C++23 standard (ISO/IEC 14882:2023):

	  * 27.6.18 Fold [alg.fold]

See also
	ranges::fold_right_last 	  right-folds a range of elements  using
     the last
	(C++23) 			  element as an initial value
					  (niebloid)
	ranges::fold_left		  left-folds a range of elements
	(C++23) 			  (niebloid)
	ranges::fold_left_first 	   left-folds  a range of elements using
     the first
	(C++23) 			  element as an initial value
					  (niebloid)
	ranges::fold_left_with_iter	  left-folds a range  of  elements,  and
     returns a pair
	(C++23) 			  (iterator, value)
					  (niebloid)
					  left-folds  a  range of elements using
     the first
	ranges::fold_left_first_with_iter element as an initial value,	and  re-
     turns a pair
	(C++23) 			  (iterator, optional)
					  (niebloid)
	accumulate			  sums up or folds a range of elements
					  (function template)
	reduce				  similar to std::accumulate, except out
     of order
	(C++17) 			  (function template)

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