Namespaces
Variants

std::ranges::fold_right

De fr.cppreference.net
 
 
Bibliothèque d'algorithmes
Algorithmes contraints et algorithmes sur les ranges (C++20)
Algorithmes contraints, p. ex. ranges::copy, ranges::sort, ...
Opérations de séquence non modificatrices    
Opérations par lots
(C++17)
Opérations de recherche
Opérations de séquence modificatrices
Opérations de copie
(C++11)
(C++11)
Opérations d'échange
Opérations de transformation
Opérations de génération
Opérations de suppression
Opérations de changement d'ordre
(jusqu'à C++17)(C++11)
(C++20)(C++20)
Opérations d'échantillonnage
(C++17)

Tri et opérations connexes
Opérations de partitionnement
(C++11)    

Opérations de tri
Opérations de recherche binaire
(sur des ranges partitionnés)
Opérations d'ensemble (sur des ranges triés)
Opérations de fusion (sur des ranges triés)
Opérations de tas
Opérations minimum/maximum
(C++11)
(C++17)
Opérations de comparaison lexicographique
Opérations de permutation


 
Algorithmes contraints
Tous les noms de ce menu appartiennent à l'espace de noms std::ranges
Opérations de séquence non modificatrices
Opérations de séquence modificatrices
Opérations de partitionnement
Opérations de tri
Opérations de recherche binaire (sur des ranges triés)
       
       
Opérations d'ensemble (sur des ranges triés)
Opérations de tas
Opérations minimum/maximum
       
       
Opérations de permutation
Opérations de pliage
Opérations sur le stockage non initialisé
Types de retour
 
Défini dans l'en-tête <algorithm>
Signature
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) (depuis C++23)
(jusqu'à 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 );
(depuis 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) (depuis C++23)
(jusqu'à 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 );
(depuis C++26)
Concepts auxiliaires
template< class F, class T, class I >
concept /* indirectly-binary-left-foldable */ = /* see description */;
(3) (exposition seulement*)
template< class F, class T, class I >
concept /* indirectly-binary-right-foldable */ = /* see description */;
(4) (exposition seulement*)

Pile à droite (right-fold) les éléments du range donné, c'est-à-dire retourne le résultat de l'évaluation de l'expression en chaîne :
f(x1, f(x2, ...f(xn, init))), où x1, x2, ..., xn sont les éléments du range.

Informellement, ranges::fold_right se comporte comme ranges::fold_left(views::reverse(r), init, /*flipped*/(f)).

Le comportement est indéfini si [firstlast) n'est pas un range valide.

1) Le range est [firstlast).
2) Identique à (1), sauf qu'il utilise r comme range, comme si en utilisant ranges::begin(r) comme first et ranges::end(r) comme last.
3) Équivaut à :
Concepts auxiliaires
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) (exposition seulement*)
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) (exposition seulement*)
4) Équivaut à :
Concepts auxiliaires
template< class F, class T, class I >
concept /*indirectly-binary-right-foldable*/ =
    /*indirectly-binary-left-foldable*/</*flipped*/<F>, T, I>;
(4A) (exposition seulement*)
Gabarits de classes auxiliaires
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) (exposition seulement*)

Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids), c'est-à-dire :

Paramètres

first, last - la paire itérateur-sentinelle définissant le range d'éléments à plier
r - le range d'éléments à plier
init - la valeur initiale du pliage
f - l'objet fonction binaire

Valeur de retour

Un objet de type U qui contient le résultat du pliage à droite (right-fold) du range donné sur f, où U est équivalent à std::decay_t<std::invoke_result_t<F&, std::iter_reference_t<I>, T>>;.

Si le range est vide, U(std::move(init)) est retourné.

Implémentations possibles

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;

Complexité

Exactement ranges::distance(first, last) applications de l'objet fonction f.

Notes

Le tableau suivant compare tous les algorithmes de pliage contraints :

Gabarit de fonction de pliage Commence par Valeur initiale Type de retour
ranges::fold_left gauche init U
ranges::fold_left_first gauche premier élément std::optional<U>
ranges::fold_right droite init U
ranges::fold_right_last droite dernier élément std::optional<U>
ranges::fold_left_with_iter gauche init

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

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

BR est ranges::borrowed_iterator_t<R>

ranges::fold_left_first_with_iter gauche premier élément

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

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

BR est ranges::borrowed_iterator_t<R>

Macro de test de fonctionnalité Valeur Norme Fonctionnalité
__cpp_lib_ranges_fold 202207L (C++23) std::ranges algorithmes de pliage
__cpp_lib_algorithm_default_value_type 202403L (C++26) Initialisation par liste pour les algorithmes (1,2)

Exemple

#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';
}

Sortie :

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

Références

  • Norme C++23 (ISO/IEC 14882:2024) :
  • 27.6.18 Pliage [alg.fold]

Voir aussi

plie à droite un range d'éléments en utilisant le dernier élément comme valeur initiale
(objet fonction d'algorithme)
plie à gauche un range d'éléments
(objet fonction d'algorithme)
plie à gauche un range d'éléments en utilisant le premier élément comme valeur initiale
(objet fonction d'algorithme)
plie à gauche un range d'éléments et retourne une paire (itérateur, valeur)
(objet fonction d'algorithme)
plie à gauche un range d'éléments en utilisant le premier élément comme valeur initiale et retourne une paire (itérateur, optional)
(objet fonction d'algorithme)
additionne ou plie un range d'éléments
(gabarit de fonction)
(C++17)
similaire à std::accumulate, sauf dans le désordre
(gabarit de fonction)