Namespaces
Variants

std::ranges::fold_right

De es.cppreference.net
 
 
Biblioteca de algoritmos
Algoritmos restringidos y algoritmos sobre rangos (C++20)
Algoritmos restringidos, p.ej. ranges::copy, ranges::sort, ...
Operaciones de secuencia no modificadoras    
Operaciones por lotes
(C++17)
Operaciones de búsqueda
Operaciones de secuencia modificadoras
Operaciones de copia
(C++11)
(C++11)
Operaciones de intercambio
Operaciones de transformación
Operaciones de generación
Operaciones de eliminación
Operaciones de cambio de orden
(hasta C++17)(C++11)
(C++20)(C++20)
Operaciones de muestreo
(C++17)

Ordenación y operaciones relacionadas
Operaciones de particionado
(C++11)    

Operaciones de ordenación
Operaciones de búsqueda binaria
(en rangos particionados)
Operaciones de conjunto (en rangos ordenados)
Operaciones de mezcla (en rangos ordenados)
Operaciones de montículo
Operaciones de mínimo/máximo
(C++11)
(C++17)
Operaciones de comparación lexicográfica
Operaciones de permutación


 
Algoritmos restringidos
Todos los nombres en este menú pertenecen al espacio de nombres std::ranges
Operaciones de secuencia no modificadoras
Operaciones de secuencia modificadoras
Operaciones de particionado
Operaciones de ordenación
Operaciones de búsqueda binaria (en rangos ordenados)
       
       
Operaciones de conjunto (en rangos ordenados)
Operaciones de montículo
Operaciones de mínimo/máximo
       
       
Operaciones de permutación
Operaciones de plegado
Operaciones sobre almacenamiento no inicializado
Tipos de retorno
 
Definido en el encabezado <algorithm>
Firma de la llamada
template< std::bidirectional_iterator I, std::sentinel_for<I> S, class T,
          /* indirectly-binary-right-foldable */<T, I> F >
constexpr auto fold_right( I first, S last, T init, F f );
(1) (desde C++23)
(hasta C++26)
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 fold_right( I first, S last, T init, F f );
(desde C++26)
template< ranges::bidirectional_range R, class T,
          /* indirectly-binary-right-foldable */
              <T, ranges::iterator_t<R>> F >
constexpr auto fold_right( R&& r, T init, F f );
(2) (desde C++23)
(hasta C++26)
template< ranges::bidirectional_range R, class T = ranges::range_value_t<R>,
          /* indirectly-binary-right-foldable */
              <T, ranges::iterator_t<R>> F >
constexpr auto fold_right( R&& r, T init, F f );
(desde C++26)
Conceptos auxiliares
template< class F, class T, class I >
concept /* indirectly-binary-left-foldable */ = /* see description */;
(3) (solo exposición*)
template< class F, class T, class I >
concept /* indirectly-binary-right-foldable */ = /* see description */;
(4) (solo exposición*)

Plegado a la derecha de los elementos del rango dado, es decir, devuelve el resultado de la evaluación de la expresión en cadena:
f(x1, f(x2, ...f(xn, init))), donde x1, x2, ..., xn son elementos del rango.

Informalmente, ranges::fold_right se comporta como ranges::fold_left(views::reverse(r), init, /*flipped*/(f)).

El comportamiento no está definido si [first, last) no es un rango válido.

1) El rango es [first, last).
2) Igual que (1), excepto que usa r como rango, como si se usara ranges::begin(r) como first y ranges::end(r) como last.
3) Equivalente a:
Conceptos auxiliares
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> &&
    std::invocable<F&, U, std::iter_reference_t<I>> &&
    std::assignable_from<U&,
        std::invoke_result_t<F&, U, std::iter_reference_t<I>>>;
(3A) (solo exposición*)
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, 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>>>>;
(3B) (solo exposición*)
4) Equivalente a:
Conceptos auxiliares
template< class F, class T, class I >
concept /*indirectly-binary-right-foldable*/ =
    /*indirectly-binary-left-foldable*/</*flipped*/<F>, T, I>;
(4A) (solo exposición*)
Plantillas de clase auxiliares
template< class F >
class /*flipped*/
{
    F f;    // exposition only
public:
    template< class T, class U >
        requires std::invocable<F&, U, T>
    std::invoke_result_t<F&, U, T> operator()( T&&, U&& );
};
(4B) (solo exposición*)

Las entidades similares a funciones descritas en esta página son objetos función de algoritmo (conocidos informalmente como niebloides), es decir:

Parámetros

first, last - el par iterador-centinela que define el rango de elementos a plegar
r - el rango de elementos a plegar
init - el valor inicial del pliegue
f - el objeto función binaria

Valor de retorno

Un objeto de tipo U que contiene el resultado del plegado a la derecha del rango dado sobre f, donde U es equivalente a std::decay_t<std::invoke_result_t<F&, std::iter_reference_t<I>, T>>;.

Si el rango está vacío, se devuelve U(std::move(init)).

Posibles implementaciones

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 = std::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::iterator_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;

Complejidad

Exactamente ranges::distance(first, last) aplicaciones del objeto función f.

Notas

La siguiente tabla compara todos los algoritmos de plegado restringidos:

Plantilla de función de plegado Comienza desde Valor inicial Tipo de retorno
ranges::fold_left izquierda init U
ranges::fold_left_first izquierda primer elemento std::optional<U>
ranges::fold_right derecha init U
ranges::fold_right_last derecha último elemento std::optional<U>
ranges::fold_left_with_iter izquierda init

(1) ranges::in_value_result<I, U>

(2) ranges::in_value_result<BR, U>,

donde BR es ranges::borrowed_iterator_t<R>

ranges::fold_left_first_with_iter izquierda primer elemento

(1) ranges::in_value_result<I, std::optional<U>>

(2) ranges::in_value_result<BR, std::optional<U>>

donde BR es ranges::borrowed_iterator_t<R>

Macro de prueba de característica Valor Std Característica
__cpp_lib_ranges_fold 202207L (C++23) std::ranges algoritmos de plegado
__cpp_lib_algorithm_default_value_type 202403L (C++26) Inicialización de lista para algoritmos (1,2)

Ejemplo

#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::multiplies{});
    #endif
    std::cout << "r5: " << r5 << '\n';
}

Salida:

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

Referencias

  • Estándar C++23 (ISO/IEC 14882:2024):
  • 27.6.18 Plegado [alg.fold]

Véase también

pliega a la derecha un rango de elementos usando el último elemento como valor inicial
(objeto función de algoritmo)
pliega a la izquierda un rango de elementos
(objeto función de algoritmo)
pliega a la izquierda un rango de elementos usando el primer elemento como valor inicial
(objeto función de algoritmo)
pliega a la izquierda un rango de elementos, y devuelve un par (iterador, valor)
(objeto función de algoritmo)
pliega a la izquierda un rango de elementos usando el primer elemento como valor inicial, y devuelve un par (iterador, opcional)
(objeto función de algoritmo)
suma o pliega un rango de elementos
(plantilla de función)
(C++17)
similar a std::accumulate, excepto fuera de orden
(plantilla de función)