C++23 ranges::fold_right 算法详解 - cpprefjp/site 技术解析

概述

std::ranges::fold_right 是 C++23 引入的一个新算法，它实现了函数式编程中经典的右折叠操作。该算法从范围的末尾开始，将二元操作依次应用到每个元素和累积值上，最终返回处理后的结果。

算法原理

fold_right 的工作方式可以理解为：

1. 从范围的最后一个元素开始处理
2. 将当前元素和初始值（或前一步的累积结果）传递给二元操作函数
3. 将操作结果作为下一步的累积值
4. 重复上述过程直到处理完所有元素

数学表达式表示为：f(e1, f(e2, f(e3, ... f(en, init)...))

函数签名

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);
  
  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);
}

参数说明

• first, last: 输入范围的迭代器对
• r: 可直接传递的范围对象
• init: 初始累积值
• f: 二元操作函数，接受当前元素和累积值，返回新的累积值

使用示例

基本数值计算

#include <ranges>
#include <algorithm>
#include <numeric>
#include <iostream>

int main() {
    auto nums = std::views::iota(1, 6); // [1,2,3,4,5]
    auto sum = std::ranges::fold_right(nums, 0, std::plus{});
    std::cout << sum << '\n'; // 输出15 (1+(2+(3+(4+(5+0)))))
}

字符串连接

#include <vector>
#include <ranges>
#include <algorithm>
#include <string>

int main() {
    std::vector<std::string> words{"Hello", " ", "World", "!"};
    auto concat = std::ranges::fold_right(words, std::string{}, 
        [](const auto& elem, auto acc) {
            return elem + std::move(acc);
        });
    // 结果为"Hello World!"
}

技术细节

约束条件

fold_right 要求输入范围满足 bidirectional_range，因为它需要从末尾开始处理元素。二元操作函数必须满足 indirectly-binary-right-foldable 概念，这实际上是 indirectly-binary-left-foldable 的变体，其中函数参数顺序被反转。

返回值类型

返回值类型由二元操作函数的返回类型决定，具体为：

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

复杂度

算法的时间复杂度是线性的，精确执行 N 次二元操作（N 为范围大小）。

与 fold_left 的对比

特性	fold_right	fold_left
处理方向	从右到左	从左到右
范围要求	双向范围	输入范围
数学表达式	f(e1, f(e2, ...))	f(...f(f(init, e1), e2), ...)
典型应用	列表反转、右结合运算	累加、左结合运算

实际应用场景

1. 反向处理数据：当需要从后向前处理数据时
2. 构建右结合表达式：如数学表达式解析
3. 函数式编程模式：实现函数式编程中的高阶操作
4. 复杂数据结构转换：如树结构的构建

注意事项

1. 二元操作函数的参数顺序很重要，第一个参数是当前元素，第二个是累积值
2. 对于空范围，直接返回初始值
3. C++26 开始支持使用花括号初始化语法传递参数
4. 返回值类型由二元操作决定，可能与输入类型不同

总结

std::ranges::fold_right 为 C++ 带来了函数式编程的强大能力，特别适合需要从右向左处理数据的场景。它与 fold_left 形成互补，为算法库提供了更完整的函数式编程支持。理解并掌握这一算法，可以编写出更简洁、更具表达力的 C++ 代码。