最終更新日時(UTC): 2026年01月05日 09時09分29秒
Koichi Murase が更新

履歴 編集

function template
<algorithm>

# std::ranges::fold_right(C++23)

    namespace std::ranges {
      template <bidirectional_iterator I,
                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) C++23
      template <bidirectional_iterator I,
                sentinel_for<I> S,
                class T = iter_value_t<I>,
                indirectly-binary-right-foldable<T, I> F>
      constexpr auto
        fold_right(I first,
                   S last,
                   T init,
                   F f);    // (1) C++26

      template <bidirectional_range R,
                class T,
                indirectly-binary-right-foldable<T, iterator_t<R>> F>
      constexpr auto
        fold_right(R&& r,
                   T init,
                   F f);    // (2) C++23
      template <bidirectional_range R,
                class T = range_value_t<R>,
                indirectly-binary-right-foldable<T, iterator_t<R>> F>
      constexpr auto
        fold_right(R&& r,
                   T init,
                   F f);    // (2) C++26
    }

## 概要

初期値から始めて、入力範囲の各要素に対して指定された二項演算を適用していきその結果を返す。二項演算が適用される各ステップでは、前のステップまでの積算値が一緒に渡される。

この関数は、初期値を入力範囲の末尾に付加した範囲に対してその末尾の隣り合う2要素に対して与えられた二項演算を適用し、その結果によって処理した要素を置換し、処理後の範囲に対して同様の処理を残りの要素が無くなるまで繰り返すような処理を行う。

これは、関数型言語におけるリスト操作の一般形である高階関数`foldr`に対応し、`std::accumulate`を改善したものでもある。

- (1) : 入力としてイテレータ範囲をとるオーバーロード
- (2) : 入力として範囲を直接とるオーバーロード

入力範囲を`{1, 2, 3, 4, 5}`、初期値を`0`、二項演算を`+`（`std::plus<>`）とした時の`fold_right()`の処理の様子

    0 : init
    [1, 2, 3, 4, 5] : rng

    [1, 2, 3, 4, 5]  0
                 5 + 0
              4 + 5
           3 + 9
        2 + 12
     1 + 14 -> fold_right(rng, 0, +)

`fold_left`に対しては、入力範囲の末尾から先頭に向かって処理を進めていく点が異なる。

## 引数

- `first` -- 入力範囲の先頭イテレータ
- `last` -- 入力範囲の番兵（終端イテレータ）
- `r` -- 入力範囲のオブジェクト
- `init` -- 初期値
- `f` -- 適用する二項演算
  - `f(*first, std::move(init))`のような呼び出しが可能であり、その戻り値型のオブジェクトを`acc`とすると
  - `acc = f(*first, std::move(acc))`のような呼び出しも可能である必要がある

## テンプレートパラメータ制約

`indirectly-binary-right-foldable`は次のように定義される説明専用のコンセプトである

    template<class F, class T, class I>
    concept indirectly-binary-right-foldable =
      indirectly-binary-left-foldable<flipped<F>, T, I>;

`flipped<F>`は二項呼び出し可能な`F`の引数順を入れ替える説明専用のクラステンプレートであり、次のように定義される

    template<class F>
    class flipped {
      F f;

    public:
      template<class T, class U>
        requires invocable<F&, U, T>
      invoke_result_t<F&, U, T> operator()(T&&, U&&);
    };

すなわち、二項演算`F`の引数順が逆になることを除いて`fold_left`と同じ制約となる。

ただし、`fold_right`はその処理の都合上、入力範囲に対して`bidirectional_range`であることを要求する（`fold_left`は`input_range`）。

## 戻り値

(1), (2)ともに、以下と等価

    using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
    if (first == last)
      return U(std::move(init));
    I tail = ranges::next(first, last);
    U accum = invoke(f, *--tail, std::move(init));
    while (first != tail)
      accum = invoke(f, *--tail, std::move(accum));
    return accum;

空の入力範囲に対しては初期値`init`を返す。

## 計算量

入力範囲`r`（`[first, last)`）の要素数を`N`とすると、正確に`N`回の`f`の適用が行われる。

## 備考

- この関数の戻り値型は、入力の型`F, T, I`から次のような`U`として取得される

      using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;

  - すなわち、指定した二項演算をイテレータと初期値によって`f(*first, std::move(init))`のように呼び出した時の戻り値型がこの関数の戻り値型となる。
  - また、この型`U`は`fold_right`の処理内部で積算値の型として使用されるものでもあり、`f`は`init`の代わりに`U`の右辺値も受け取れる必要がある。二項演算の呼び出しにおいては、第一引数にイテレータの間接参照結果が直接渡され、第二引数に初期値もしくは積算値が渡される。そして、二項演算の適用結果は積算値を保存する変数に直接代入される（つまり、結果を次のステップに引き継ぎたい場合は積算処理も二項演算内で行う必要がある）。詳細は下の実装例を参照。

- (1), (2) :

  - C++26 : 引数として波カッコ初期化`{}`を受け付ける

        std::vector<T> v;
        T sum = std::ranges::fold_right(v, {a, b}, op);

## 例

### 基本的な数値集計処理の例

    #include <ranges>
    #include <algorithm>
    #include <functional>
    #include <format>
    #include <vector>
    #include <print>
    #include <concepts>

    using namespace std::ranges;

    int main() {
      // 入力
      range auto rng = views::iota(1, 11);
      // 初期値
      const int init = 0;
      // 二項演算
      auto op = std::plus<>{};

      int resl = fold_right(rng, init, op);

      std::println("{:d}", resl);

      // 入力範囲はfloatのvector
      std::vector<float> rngf = { 0.125f, 0.25f, 0.75f };

      // 計算結果はfloat
      std::same_as<float> auto reslf = fold_right(rngf, init, op);

      std::println("{:g}", reslf);
    }

#### 出力

    55
    1.125

### 処理順序を表示する例

    #include <ranges>
    #include <algorithm>
    #include <functional>
    #include <format>
    #include <vector>
    #include <print>
    #include <concepts>

    using namespace std::ranges;

    int main() {
      // [a, b, c, d, e, f]
      range auto rng = views::iota('a', 'g');

      const std::string init = "init";

      // fold_leftの二項演算op
      auto op_left = [](std::string acc, char elem) {
        acc += " -> ";
        acc += elem;
        return acc;
      };
      // fold_rightの二項演算op
      auto op_right = [op_left](char elem, std::string acc) {
        return op_left(std::move(acc), elem);
      };

      auto resl = fold_left(rng, init, op_left);
      auto resr = fold_right(rng, init, op_right);

      std::println("{:s}", resl);
      std::println("{:s}", resr);
    }

#### 出力

    init -> a -> b -> c -> d -> e -> f
    init -> f -> e -> d -> c -> b -> a

### 入力範囲を反転させる例

    #include <ranges>
    #include <algorithm>
    #include <functional>
    #include <format>
    #include <vector>
    #include <print>
    #include <concepts>

    using namespace std::ranges;

    int main() {
      range auto rng = views::iota(1, 11);

      std::vector<int> init{};

      auto op = [](int elem, std::vector<int> acc) {
        acc.push_back(elem);
        return acc;
      };

      std::vector<int> res = fold_right(rng, init, op);

      std::println("{}", res);
    }

#### 出力

    [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

### 波カッコ初期化を入力として使用する (C++26)

    #include <algorithm>
    #include <print>
    #include <vector>

    int main() {
      std::vector<int> v = {1, 2, 3};

      int sum = std::ranges::fold_right(
        v,
        {},
        [](auto&& a, auto&& b) { return a + b; }
      );
      std::println("{}", sum);
    }

#### 出力

    6

## 実装例

    template<bidirectional_iterator I, 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) {
      using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;

      if (first == last) {
        return U(std::move(init));
      }

      I tail = ranges::next(first, last);
      U accum = invoke(f, *--tail, std::move(init));

      while (first != tail) {
        accum = invoke(f, *--tail, std::move(accum));
      }

      return accum; // 暗黙ムーブ or NRVO
    }

## バージョン

### 言語

- C++23

### 処理系

- Clang: ??
- GCC: 13.1 ✅
- Visual C++: 2022 Update 5 ✅

## 関連項目

- `ranges::fold_left`
  - 範囲の左からの`fold`
- `ranges::fold_left_first`
  - 範囲の最初の要素を初期値として`fold_left`
- `ranges::fold_right_last`
  - 範囲の最後の要素を初期値として`fold_right`
- `ranges::fold_left_with_iter`
  - `fold_left`の結果と共に、計算した終端イテレータも返す
- `ranges::fold_left_first_with_iter`
  - `fold_left_first`の結果と共に、計算した終端イテレータも返す

## 参照

- P2322R6 `ranges::fold`
- プログラミングHaskellのfoldr, foldlの説明が秀逸だった件 - あと味
- P2248R8 Enabling list-initialization for algorithms
  - C++26で波カッコ初期化 (リスト初期化) に対応した