std::ranges::fold_right
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| 调用签名 |
||
| (1) | ||
| (C++23 起) (C++26 前) |
||
| |
(C++26 起) | |
| (2) | ||
| |
(C++23 起) (C++26 前) |
|
| |
(C++26 起) | |
| 辅助概念 |
||
| |
(3) | (仅用于阐述*) |
| |
(4) | (仅用于阐述*) |
右折叠给定范围的元素，当 x1, x2, ..., xn 为范围内元素时返回链式表达式 f(x1, f(x2, ...f(xn, init))) 的求值结果。
非正式地说，ranges::fold_right 的行为类似 ranges::fold_left(views::reverse(r), init, /* flipped */(f))。
如果 [first, last) 不是有效范围则行为未定义。
1) 范围为
[first, last)。2) 同 (1)，但使用
r 作为其范围，如同使用 ranges::begin(r) 作为 first 且使用 ranges::end(r) 作为 last。3) 等价于：
| 辅助概念 |
||
| |
(3A) | (仅用于阐述*) |
| |
(3B) | (仅用于阐述*) |
4) 等价于:
| 辅助概念 |
||
| |
(4A) | (仅用于阐述*) |
| 辅助类模板 |
||
| |
(4B) | (仅用于阐述*) |
此页面上描述的函数式实体是算法函数对象（非正式地称为 niebloid），即：
参数
| first, last | - | 要折叠的元素范围的迭代器-哨位对 |
| r | - | 应用折叠的范围 |
| init | - | 折叠的初值 |
| f | - | 二元函数对象 |
返回值
容纳了给定范围上执行 f 右折叠结果的 U 类型对象，其中 U 等价于 std::decay_t<std::invoke_result_t<F&, std::iter_reference_t<I>, T>>;。
如果范围为空，则返回 U(std::move(init))。
可能的实现
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;
|
复杂度
准确应用 ranges::distance(first, last) 次函数对象 f。
注解
下表比较了所有受约束的折叠算法:
| 折叠函数模板 | 始于 | 初值 | 返回类型 |
|---|---|---|---|
ranges::fold_left |
左侧 | init |
U
|
ranges::fold_left_first |
左侧 | 首元素 | std::optional<U>
|
ranges::fold_right |
右侧 | init |
U
|
ranges::fold_right_last |
右侧 | 末元素 | std::optional<U>
|
ranges::fold_left_with_iter |
左侧 | init |
(1) (2) 其中 |
ranges::fold_left_first_with_iter |
左侧 | 首元素 |
(1) (2) 其中 |
| 功能特性测试宏 | 值 | 标准 | 功能特性 |
|---|---|---|---|
__cpp_lib_ranges_fold |
202207L |
(C++23) | std::ranges 折叠算法
|
__cpp_lib_algorithm_default_value_type |
202403L |
(C++26) | 算法中的列表初始化 (1,2) |
示例
运行此代码
#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';
// 使用程序定义的函数对象（lambda-表达式）：
std::string r3 = ranges::fold_right
(
v, "A", [](int x, std::string s) { return s + ':' + std::to_string(x); }
);
std::cout << "r3: " << r3 << '\n';
// 获得 vector 中的所有 pair 的 pair::second 的乘积：
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';
}
输出：
r1: 42
r2: ABCD!
r3: A:8:7:6:5:4:3:2:1
r4: 42
r5: (42,42)
引用
- C++23 标准（ISO/IEC 14882:2024）：
- 27.6.18 Fold [alg.fold]
参阅
(C++23) |
以末元素为初值右折叠范围中元素 (算法函数对象) |
(C++23) |
左折叠范围中元素 (算法函数对象) |
(C++23) |
以首元素为初值左折叠范围中元素 (算法函数对象) |
(C++23) |
左折叠范围中元素，并返回 pair（迭代器，值） (算法函数对象) |
| 以首元素为初值左折叠范围中元素，并返回 pair（迭代器，optional） (算法函数对象) | |
| 求和或折叠范围中元素 (函数模板) | |
(C++17) |
类似 std::accumulate，但不依序执行 (函数模板) |
