Ranges 算法

C++20 引入的 Ranges 库彻底革新了 STL 算法的使用方式。本章深入讲解 Ranges 算法的核心优势、常用算法分类、投影机制以及与经典 STL 算法的对比。

为什么需要 Ranges

经典 STL 算法要求传入迭代器对,这带来了几个长期存在的问题:

#include <algorithm>
#include <vector>

std::vector<int> v{5, 3, 8, 1, 9, 2};
std::vector<int> w{10, 20, 30};

// 经典方式:必须手写 begin/end
std::sort(v.begin(), v.end());

// 容易犯错:迭代器不匹配(编译通过,运行时未定义行为!)
// std::sort(v.begin(), w.end());  // BUG: 来自不同容器的迭代器

经典 STL 的痛点:迭代器不匹配是一类难以排查的 bug。编译器不会报错,运行时直接崩溃或产生未定义行为。此外,经典算法的错误信息晦涩难懂——模板展开错误往往长达数百行。

C++20 Ranges 算法解决了这些问题:

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

std::vector<int> v{5, 3, 8, 1, 9, 2};

// Ranges 方式:直接传容器,不可能传错迭代器
std::ranges::sort(v);

// 如果传入不满足约束的类型,编译器会给出清晰的概念错误
// std::ranges::sort(42);  // 错误:"42 不满足 ranges::random_access_range"

核心优势总结:(1)直接传容器,消除迭代器不匹配 bug;(2)基于 Concepts 约束,编译错误信息清晰明了;(3)支持投影(projection)机制,减少样板代码。

常用 Ranges 算法

排序算法

#include <algorithm>
#include <ranges>
#include <vector>
#include <iostream>

std::vector<int> data{5, 2, 8, 1, 9, 3, 7, 4, 6};

// 完全排序
std::ranges::sort(data);
// data: {1, 2, 3, 4, 5, 6, 7, 8, 9}

// 稳定排序(保持相等元素的相对顺序)
std::vector<std::pair<int,char>> items{{1,'a'}, {2,'b'}, {1,'c'}};
std::ranges::stable_sort(items, {}, &std::pair<int,char>::first);
// items: {{1,'a'}, {1,'c'}, {2,'b'}} — 两个 1 保持原始顺序

// 部分排序:只排前 3 个最小元素
std::vector<int> nums{9, 5, 2, 8, 1, 7, 3};
std::ranges::partial_sort(nums, nums.begin() + 3);
// nums 前 3 个元素是 {1, 2, 3},其余元素顺序不确定

// 第 N 个元素(找中位数等场景)
std::vector<int> vals{9, 5, 2, 8, 1, 7, 3};
std::ranges::nth_element(vals, vals.begin() + 3);
// vals[3] 是排序后第 4 小的元素,左边都比它小,右边都比它大

查找算法

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

std::vector<int> data{10, 20, 30, 40, 50};

// 查找精确值
auto it = std::ranges::find(data, 30);
if (it != data.end()) {
    std::cout << "找到: " << *it << "\n";  // 找到: 30
}

// 条件查找
auto it2 = std::ranges::find_if(data, [](int x) { return x > 25; });
// *it2 == 30(第一个大于 25 的元素)

// C++23: contains — 直接返回 bool,更直观
if (std::ranges::contains(data, 30)) {
    std::cout << "容器中包含 30\n";
}

// 二分查找(要求已排序)
std::ranges::sort(data);
bool found = std::ranges::binary_search(data, 30);  // true

// lower_bound / upper_bound
auto lb = std::ranges::lower_bound(data, 25);
// *lb == 30(第一个 >= 25 的元素)

变换算法

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

std::vector<int> src{1, 2, 3, 4, 5};
std::vector<int> dst(5);

// transform:对每个元素应用函数,输出到目标
std::ranges::transform(src, dst.begin(), [](int x) { return x * x; });
// dst: {1, 4, 9, 16, 25}

// 就地变换
std::ranges::transform(src, src.begin(), [](int x) { return x + 10; });
// src: {11, 12, 13, 14, 15}

// for_each:对每个元素执行操作(不产生输出)
std::ranges::for_each(src, [](int x) {
    std::cout << x << " ";
});
// 输出: 11 12 13 14 15

// 双输入 transform
std::vector<int> a{1, 2, 3};
std::vector<int> b{10, 20, 30};
std::vector<int> result(3);
std::ranges::transform(a, b, result.begin(), std::plus{});
// result: {11, 22, 33}

过滤与移除

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

std::vector<int> data{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// copy_if:复制满足条件的元素到新容器
std::vector<int> evens;
std::ranges::copy_if(data, std::back_inserter(evens),
                     [](int x) { return x % 2 == 0; });
// evens: {2, 4, 6, 8, 10}

// remove_if + erase:就地移除(经典的 erase-remove 惯用法)
auto [rm_begin, rm_end] = std::ranges::remove_if(data,
    [](int x) { return x % 2 != 0; });
data.erase(rm_begin, rm_end);
// data: {2, 4, 6, 8, 10}

// C++20 更简洁的方式:std::erase_if(容器成员)
std::vector<int> nums{1, 2, 3, 4, 5, 6};
std::erase_if(nums, [](int x) { return x < 4; });
// nums: {4, 5, 6}

聚合算法

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

std::vector<int> data{1, 2, 2, 3, 3, 3, 4, 5};

// count:统计特定值出现次数
auto c = std::ranges::count(data, 3);
// c == 3

// count_if:统计满足条件的元素个数
auto even_count = std::ranges::count_if(data,
    [](int x) { return x % 2 == 0; });
// even_count == 3(2, 2, 4)

// accumulate 不在 ranges 中,但可以用 ranges::fold_left (C++23)
// 或经典方式:
int sum = std::accumulate(data.begin(), data.end(), 0);
// sum == 23

// C++23: fold_left
// int sum23 = std::ranges::fold_left(data, 0, std::plus{});

最值算法

#include <algorithm>
#include <ranges>
#include <vector>
#include <iostream>

std::vector<int> data{3, 1, 4, 1, 5, 9, 2, 6};

// 直接取最值(对容器整体操作)
int smallest = std::ranges::min(data);    // 1
int largest  = std::ranges::max(data);    // 9

// 同时获取最小和最大值
auto [lo, hi] = std::ranges::minmax(data);
std::cout << "最小: " << lo << ", 最大: " << hi << "\n";
// 最小: 1, 最大: 9

// min_element / max_element:返回迭代器
auto min_it = std::ranges::min_element(data);
std::cout << "最小值在索引: " << std::distance(data.begin(), min_it) << "\n";

// 也支持初始化列表
int m = std::ranges::min({7, 2, 9, 4});  // 2

投影 (Projections)

投影是 Ranges 算法最强大的特性之一。它允许你在算法比较/操作元素之前,先对元素应用一个变换函数,而无需修改比较器或原始数据。

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

struct Person {
    std::string name;
    int age;
    double salary;
};

std::vector<Person> people{
    {"Alice", 30, 85000.0},
    {"Bob",   25, 72000.0},
    {"Carol", 35, 95000.0},
    {"Dave",  28, 68000.0}
};

// 按年龄排序:投影到 age 成员
std::ranges::sort(people, {}, &Person::age);
// 排序后: Bob(25), Dave(28), Alice(30), Carol(35)

// {} 表示默认比较器 (std::less{}),第三个参数是投影

// 按姓名查找
auto it = std::ranges::find(people, "Carol", &Person::name);
if (it != people.end()) {
    std::cout << it->name << " 的年龄是 " << it->age << "\n";
}

// 按薪资降序排序
std::ranges::sort(people, std::greater{}, &Person::salary);
// Carol(95000), Alice(85000), Bob(72000), Dave(68000)

// 找最年轻的人
auto youngest = std::ranges::min_element(people, {}, &Person::age);
std::cout << "最年轻: " << youngest->name << "\n";  // Bob

投影也可以是 Lambda 表达式,处理更复杂的场景:

// Lambda 作为投影:按姓名长度排序
std::ranges::sort(people, {}, [](const Person& p) {
    return p.name.size();
});

// 按年龄和薪资的组合排序(年轻且高薪优先)
std::ranges::sort(people, {}, [](const Person& p) {
    return std::pair{p.age, -p.salary};  // 年龄升序,薪资降序
});

// 统计 30 岁以上的人数
auto count = std::ranges::count_if(people, [](int age) {
    return age > 30;
}, &Person::age);  // 注意:投影先于谓词执行

投影的执行顺序:投影在谓词/比较器之前执行。对于 count_if(range, pred, proj),实际执行的是 pred(proj(element))。所以上面 Lambda 接收的是 int(投影后的年龄),而不是 Person。

返回值类型

Ranges 算法的返回值比经典 STL 更丰富,携带了更多有用信息:

#include <algorithm>
#include <ranges>
#include <vector>
#include <iostream>

std::vector<int> src{1, 2, 3, 4, 5, 6, 7, 8};
std::vector<int> dst(8);

// find:返回迭代器(与经典相同)
auto it = std::ranges::find(src, 5);

// minmax:返回 ranges::minmax_result{min, max}
auto [lo, hi] = std::ranges::minmax(src);
std::cout << "min=" << lo << ", max=" << hi << "\n";

// copy_if:返回 ranges::copy_if_result{in, out}
std::vector<int> evens;
auto copy_result = std::ranges::copy_if(src,
    std::back_inserter(evens),
    [](int x) { return x % 2 == 0; });
// copy_result.in  — 输入范围的尾后迭代器
// copy_result.out — 输出范围的尾后迭代器

// for_each:返回 {迭代器, 函数对象}
int total = 0;
auto fe_result = std::ranges::for_each(src, [&](int x) { total += x; });
// fe_result.in  — 尾后迭代器
// fe_result.fun — 被移动后的函数对象

// remove_if:返回子范围 [新尾, 旧尾)
std::vector<int> nums{1, 2, 3, 4, 5};
auto [new_end, old_end] = std::ranges::remove_if(nums,
    [](int x) { return x < 3; });
nums.erase(new_end, old_end);
// nums: {3, 4, 5}

利用结构化绑定:配合 C++17 的结构化绑定,Ranges 算法返回的复合类型可以优雅地解构。这比经典 STL 中只返回单个迭代器要实用得多。

与经典 STL 算法对比

操作 经典 STL Ranges (C++20)
排序 std::sort(v.begin(), v.end()) std::ranges::sort(v)
按成员排序 std::sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.x < b.x; }) std::ranges::sort(v, {}, &T::x)
查找 std::find(v.begin(), v.end(), val) std::ranges::find(v, val)
判断包含 std::find(v.begin(), v.end(), val) != v.end() std::ranges::contains(v, val) (C++23)
条件统计 std::count_if(v.begin(), v.end(), pred) std::ranges::count_if(v, pred)
复制过滤 std::copy_if(v.begin(), v.end(), out, pred) std::ranges::copy_if(v, out, pred)
最值 *std::min_element(v.begin(), v.end()) std::ranges::min(v)
错误信息 模板错误(数百行展开) Concepts 约束(精准定位)

注意命名空间:Ranges 算法位于 std::ranges:: 命名空间,不要与 std:: 中的经典版本混淆。两者可以共存于同一个翻译单元,但推荐统一使用 Ranges 版本。

组合使用示例

以下是一个完整的实际示例——处理学生成绩数据:

#include <algorithm>
#include <ranges>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <format>

struct Student {
    std::string name;
    int math;
    int english;
    int science;

    int total() const { return math + english + science; }
    double average() const { return total() / 3.0; }
};

int main() {
    std::vector<Student> students{
        {"张三", 85, 92, 78},
        {"李四", 90, 88, 95},
        {"王五", 72, 65, 80},
        {"赵六", 95, 90, 92},
        {"钱七", 60, 55, 70},
        {"孙八", 88, 91, 85},
    };

    // 1. 按总分降序排列
    std::ranges::sort(students, std::greater{}, &Student::total);

    std::cout << "=== 成绩排名 ===\n";
    std::ranges::for_each(students, [rank = 1](const Student& s) mutable {
        std::cout << std::format("第{}名: {} (总分: {})\n",
                                   rank++, s.name, s.total());
    });

    // 2. 筛选出平均分 80 以上的优秀学生
    std::vector<Student> excellent;
    std::ranges::copy_if(students, std::back_inserter(excellent),
        [](double avg) { return avg >= 80.0; }, &Student::average);

    std::cout << "\n=== 优秀学生 (均分≥80) ===\n";
    for (const auto& s : excellent) {
        std::cout << std::format("  {} - 均分: {:.1f}\n", s.name, s.average());
    }

    // 3. 找出数学最高分
    auto math_best = std::ranges::max_element(students, {}, &Student::math);
    std::cout << std::format("\n数学最高分: {} ({}分)\n",
                              math_best->name, math_best->math);

    // 4. 统计不及格人数(任意一科低于 60)
    auto fail_count = std::ranges::count_if(students, [](const Student& s) {
        return std::ranges::min({s.math, s.english, s.science}) < 60;
    });
    std::cout << std::format("有不及格科目的学生: {}人\n", fail_count);

    // 5. 提取所有学生姓名
    std::vector<std::string> names(students.size());
    std::ranges::transform(students, names.begin(), &Student::name);
    std::cout << "\n所有学生: ";
    std::ranges::for_each(names, [](const std::string& n) {
        std::cout << n << " ";
    });
    std::cout << "\n";

    return 0;
}

程序输出:

=== 成绩排名 ===
第1名: 赵六 (总分: 277)
第2名: 李四 (总分: 273)
第3名: 孙八 (总分: 264)
第4名: 张三 (总分: 255)
第5名: 王五 (总分: 217)
第6名: 钱七 (总分: 185)

=== 优秀学生 (均分≥80) ===
  赵六 - 均分: 92.3
  李四 - 均分: 91.0
  孙八 - 均分: 88.0
  张三 - 均分: 85.0

数学最高分: 赵六 (95分)
有不及格科目的学生: 1人

所有学生: 赵六 李四 孙八 张三 王五 钱七

实践建议:在新代码中优先使用 std::ranges:: 算法。它们不仅更简洁安全,投影机制还能减少大量 Lambda 样板代码。唯一需要注意的是确保编译器支持 C++20(GCC 10+、Clang 13+、MSVC 16.10+)。

本章小结

  • 更安全:直接传容器,彻底消除迭代器不匹配的 bug
  • 更简洁:省去 .begin() / .end(),代码更紧凑
  • 投影机制:用 &T::member 或 Lambda 替代复杂比较器
  • 更好的错误信息:基于 Concepts 的约束让编译错误清晰可读
  • 更丰富的返回值:返回结构体包含多个有用信息,配合结构化绑定使用
  • 常用分类:排序、查找、变换、过滤、聚合、最值六大类覆盖日常需求