Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages

  
 
  

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
       elements	of the
	  range.

	  Informally,	       ranges::fold_right	  behaves	  like
       std::fold_left(ranges::reverse(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)
       (exposition 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)
       (exposition 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
       (exposition
	  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 call-
       ing 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 in-
       hibited.

	  In practice, they may	be implemented as function  objects,  or  with
       special 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_reference_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::iter-
       ator_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
       object 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::bor-
       rowed_iterator_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::bor-
       rowed_iterator_t<R>

		    Feature-test       macro		     Value	   Std
       Feature
	  __cpp_lib_ranges_fold			 202207L  (C++23)  std::ranges
       fold algorithms
	  __cpp_lib_algorithm_default_value_type 202403	 (C++26) List-initial-
       ization 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
       vector:
	    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::multi-
       plies{});
	    #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 us-
       ing 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 us-
       ing the first
	  ranges::fold_left_first_with_iter element as an initial  value,  and
       returns a pair
	  (C++23)			    (iterator, optional)
					    (niebloid)
	  accumulate			     sums  up or folds a range of ele-
       ments
					    (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)

Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::ranges::fold_right&sektion=3&manpath=FreeBSD+Ports+15.1.quarterly>

home | help