namespace std::ranges {
template<bidirectional_iterator I, sentinel_for<I> S,
indirectly-binary-right-foldable<iter_value_t<I>, I> F>
requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
constexpr auto fold_right_last(I first, S last, F f); // (1)
template<bidirectional_range R,
indirectly-binary-right-foldable<range_value_t<R>, iterator_t<R>> F>
requires constructible_from<range_value_t<R>, range_reference_t<R>>
constexpr auto fold_right_last(R&& r, F f); // (2)
}
概要
初期値の指定を省略するfold_right
。入力範囲の末尾要素が初期値として使用される。
- (1) : 入力としてイテレータ範囲をとるオーバーロード
- (2) : 入力として範囲を直接とるオーバーロード
引数
first
-- 入力範囲の先頭イテレータlast
-- 入力範囲の番兵(終端イテレータ)r
-- 入力範囲のオブジェクトf
-- 適用する二項演算f(*first, *first)
のような呼び出しが可能であり(実際にこの様に呼ばれるわけではない)、その戻り値型のオブジェクトをacc
とするとacc = f(*first, std::move(acc))
のような呼び出しも可能である必要がある
テンプレートパラメータ制約
indirectly-binary-right-foldable
はF
の引数順が逆になることを除いてindirectly-binary-left-foldable
と同様の制約となる。
indirectly-binary-left-foldable
では、初期値の型T
が戻り値型(積算値の型)U
に変換可能であることが要求(convertible_to<T, U>
)されており、この関数では初期値の型を指定できない(range_value_t<R>
が使用される)ため戻り値型を大きく制御することが困難になる(例えば、fold_right
の例にある入力範囲を反転させる例の様なことは素直にはできない)。
戻り値
(1)(2)ともに、以下と等価
using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
if (first == last)
return optional<U>();
I tail = ranges::prev(ranges::next(first, std::move(last)));
return optional<U>(in_place, ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), std::move(f)));
空の入力範囲に対しては無効値を保持するoptional
を返す。
計算量
入力範囲r
([first, last)
)の要素数をN
とすると、正確にN - 1
回のf
の適用が行われる。
備考
この関数の戻り値型はoptional<U>
であり、U
は次のように求められる型と一致する
auto tail = --last;
decltype(ranges::fold_right(std::move(first), tail, iter_value_t<I>(*tail), f));
すなわち、他の引数はそのままに初期値として入力範囲r
の要素を手動で指定してfold_right
を呼び出した際の戻り値型を包むoptional
となる。
fold_right
と同様に、この型U
はfold_right_last
の処理内部で積算値の型として使用されるものでもあり、f
は*first
の代わりにU
の右辺値も受け取れる必要がある。詳細は下の実装例を参照。
例
基本的な数値集計処理の例
#include <ranges>
#include <algorithm>
#include <functional>
#include <print>
#include <vector>
using namespace std::ranges;
int main() {
// 入力
range auto rng = views::iota(1, 11);
// 二項演算
auto op = std::plus<>{};
auto resl = fold_right_last(rng, op);
std::println("{:d}", resl.value());
// 入力範囲はfloatのvector
std::vector<float> rngf = { 0.125f, 0.25f, 0.75f };
// 計算結果はoptional<float>
auto reslf = fold_right_last(rngf, op);
std::println("{:g}", reslf.value());
}
出力
55
1.125
空の入力範囲に対する動作の例
#include <ranges>
#include <algorithm>
#include <functional>
#include <print>
#include <vector>
using namespace std::ranges;
int main() {
range auto rng = views::empty<int>;
auto op = std::plus<>{};
auto res1 = fold_left(rng, -1, op);
auto res2 = fold_right_last(rng, op);
std::println("{:d}", res1);
std::println("{:d}", res2.value_or(-1));
}
出力
-1
-1
実装例
template<bidirectional_iterator I, sentinel_for<I> S,
indirectly-binary-right-foldable<iter_value_t<I>, I> F>
requires constructible_from<iter_value_t<I>, iter_reference_t<I>>
constexpr auto fold_right_last(I first, S last, F f) {
using U = decay_t<invoke_result_t<F&, iter_reference_t<I>, T>>;
if (first == last) {
return optional<U>();
}
I tail = ranges::prev(ranges::next(first, std::move(last)));
if (first == tail) {
return optional<U>(in_place, *tail);
}
const auto copy_tail = tail;
U accum = invoke(f, *--tail, *copy_tail);
while (first != tail) {
accum = invoke(f, *--tail, std::move(accum));
}
return optional<U>(in_place, std::move(accum));
}
バージョン
言語
- C++23
処理系
- Clang: ??
- GCC: 13.1 ✅
- Visual C++: 2022 Update 5 ✅
関連項目
ranges::fold_left
- 範囲の左からの
fold
- 範囲の左からの
ranges::fold_right
- 範囲の右からの
fold
- 範囲の右からの
ranges::fold_left_first
- 範囲の最初の要素を初期値として
fold_left
- 範囲の最初の要素を初期値として
ranges::fold_left_with_iter
fold_left
の結果と共に、計算した終端イテレータも返す
ranges::fold_left_first_with_iter
fold_left_first
の結果と共に、計算した終端イテレータも返す