Skip to content

Latest commit

 

History

History
311 lines (237 loc) · 9.76 KB

ranges_fold_right.md

File metadata and controls

311 lines (237 loc) · 9.76 KB
Raw

fold_right

  • algorithm[meta header]
  • function template[meta id-type]
  • std::ranges[meta namespace]
  • cpp23[meta cpp]
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)

  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)
}
  • bidirectional_iterator[link /reference/iterator/bidirectional_iterator.md]
  • sentinel_for[link /reference/iterator/sentinel_for.md]
  • bidirectional_range[link /reference/ranges/bidirectional_range.md]
  • iterator_t[link /reference/ranges/iterator_t.md]

概要

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

この関数は、初期値を入力範囲の末尾に付加した範囲に対してその末尾の隣り合う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>;
  • indirectly-binary-left-foldable[link ranges_fold_left.md]

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;
  • decay_t[link /reference/type_traits/decay.md]
  • invoke_result_t[link /reference/type_traits/invoke_result.md]
  • iter_reference_t[link /reference/iterator/iter_reference_t.md]
  • next[link /reference/iterator/ranges_next.md]
  • invoke[link /reference/functional/invoke.md]

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

計算量

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

備考

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

using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
  • decay_t[link /reference/type_traits/decay.md]
  • invoke_result_t[link /reference/type_traits/invoke_result.md]
  • iter_reference_t[link /reference/iterator/iter_reference_t.md]

すなわち、指定した二項演算をイテレータと初期値によってf(*first, std::move(init))のように呼び出した時の戻り値型がこの関数の戻り値型となる。

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

例

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

#include <ranges>
#include <algorithm>
#include <functional>
#include <format>
#include <vector>
#include <iostream>
#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);
}
  • fold_right[color ff0000]
  • same_as[link /reference/concepts/same_as.md]
  • iota[link /reference/ranges/iota_view.md]
  • plus[link /reference/functional/plus.md]
  • println[link /reference/print/println.md]

出力

55
1.125

処理順序を表示する例

#include <ranges>
#include <algorithm>
#include <functional>
#include <format>
#include <vector>
#include <iostream>
#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);
}
  • fold_right[color ff0000]
  • println[link /reference/print/println.md]
  • fold_left[link /reference/algorithm/ranges_fold_left.md]

出力

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 <iostream>
#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);
}
  • fold_right[color ff0000]
  • iota[link /reference/ranges/iota_view.md]
  • println[link /reference/print/println.md]

出力

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

実装例

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

処理系

関連項目

参照