14 范围

14.1 引言

标准库为其中的算法提供了，基于范围概念的有约束版本，和纯粹为了向下兼容的无约束版本。有约束版本位于<ranges>头文件的std::ranges命名空间中。范围是一个序列的通用形态，它有如下几种定义形式：

• 一对迭代器begin和end，begin指向范围中的第一个元素，end指向范围中最后一个元素的下一个位置

• 一个迭代器begin和一个整数n，begin指向范围中的第一个元素，n表示范围中的元素个数

• 一个迭代器begin和一个谓词pred，begin指向范围中的第一个元素，如果迭代器p令“pred(p)”的值为true，则到达了范围的末端。借助这种方法，可以表示无限范围和动态范围

只要v满足范围概念的约束，即v是一个范围，就可以用更简洁的“sort(v)”，代替自1994年STL诞生伊始，沿用至今的“sort(v.begin(), v.end())”形式。类似的写法也可以用在自定义算法中。例如：

xxxxxxxxxx
5
1
template<forward_range R>
2
    requires sortable<iterator_t<R>>
3
void sort20(R& r) { // 受范围概念约束的现代版本
4
    return sort94(r.begin(), r.end()); // 不受任何约束的传统版本
5
}

范围概念覆盖了算法中99%的常用用法。除了符号上的优势，范围还创造了一些优化的机会，并消除了一些愚蠢的错误。例如：

xxxxxxxxxx
1
1
sort(v1.begin(), v2.end());

或者

xxxxxxxxxx
1
1
sort(v.end(), v.begin());

类似这样的错误，在编程实践中屡见不鲜。

自然，不同类型的迭代器适用于不同类型的范围。常用的表示范围的概念包括但不限于input_range、forward_range、bidirectional_range、random_access_range和contiguous_range等等。

C++20：范围、视图和管道

14.2 视图

视图是查看范围的一种方式。例如：

xxxxxxxxxx
5
1
vector<int> v{ -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };
2
...
3
filter_view fv{ v, [](int x) { return x % 2; } };
4
for (int x : fv)
5
    cout << x << ' '; // -5 -3 -1 1 3 5

从filter_view类型的对象fv读取数据时，自与其绑定的范围v的首元素开始，依次获取其中的元素，作为参数传递给构造fv时指定的谓词，若满足该谓词，即谓词函数返回true，则返回该元素，否则获取范围v内的下一个元素，重复以上过程。

借助视图，还可以从给定范围中，获取最多n个元素。例如：

xxxxxxxxxx
4
1
...
2
take_view tv{ fv, 3 };
3
for (int x : tv)
4
    cout << x << ' '; // -5 -3 -1

注意，视图本身也是范围。

上述代码可以匿名视图的形式得以简化：

xxxxxxxxxx
3
1
...
2
for (int x : take_view{ fv, 3 })
3
    cout << x << ' '; // -5 -3 -1

甚至连fv也以匿名方式替换掉：

xxxxxxxxxx
2
1
for (int x : take_view{ filter_view{ v, [](int x) { return x % 2; } }, 3 })
2
    cout << x << ' '; // -5 -3 -1

这种视图嵌套的写法很快会变得象魔咒一样晦涩难懂，为此出现了一种替换形式——管道。

除了filter_view和take_view以外，标准库还提供了很多种视图。视图又被称为范围适配器（range adaptor）。如下表所示：

视图提供的接口与范围提供的接口非常相似，因此但凡可以使用范围的地方，一般也可以使用视图。视图与范围的本质性差异在于，视图并不拥有元素本身，因此视图也不负责与元素存储有关的资源管理，那是范围的责任。从另一方面说，视图的生命周期不能大于所绑定范围的生命周期。例如：

xxxxxxxxxx
5
1
auto bad() {
2
    vector<int> v{ -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 };
3
    filter_view fv{ v, [](int x) { return x % 2; } };
4
    return fv; // 范围v会在函数返回时被销毁，所返回的fv即失去绑定目标
5
}

视图被有意设计为复制开销很低，因此通常采用值方式传递参数。

视图不但可以用于基本类型的范围，同样也可以用于类类型的范围。例如：

xxxxxxxxxx
9
1
void printNames(const auto& students) {
2
    for (const string& name : elements<0>(students))
3
        cout << name << endl;
4
}
5

6
void printAges(const auto& students) {
7
    for (int age : elements<1>(students))
8
        cout << age << endl;
9
}

xxxxxxxxxx
8
1
vector<tuple<string, int>> students;
2
students.push_back(make_tuple("zhangfei", 20));
3
students.push_back(make_tuple("guanyu", 21));
4
students.push_back(make_tuple("zhaoyun", 22));
5
students.push_back(make_tuple("huangzhong", 23));
6
students.push_back(make_tuple("machao", 24));
7
printNames(students);
8
printAges(students);

14.3 生成器

视图不但可以绑定于已有的范围，还可以绑定于动态生成的范围。这样视图称为生成器，亦称范围工厂。下表列出了一些常用的范围工厂：

其中，利用iota_view生成简单序列，会非常方便。例如：

xxxxxxxxxx
2
1
for (auto x : iota_view{ 42, 52 })
2
    cout << x << ' '; // 42 43 44 45 46 47 48 49 50 51

而通过istream_view可以很方便地在一个基于范围的for循环中，持续地从输入流中读取数据。例如：

xxxxxxxxxx
2
1
for (auto x : istream_view<int>{ cin })
2
    cout << x << ' ';

更进一步，istream_view视图还可以和其它视图结合使用。例如：

xxxxxxxxxx
3
1
for (auto x : transform_view{ istream_view<int>{ cin },
2
    [](auto x) { return x * x; } })
3
    cout << x << ' ';

输入“1 2 3”，输出“1 4 9”。

14.4 管道

考虑之前的例子：

xxxxxxxxxx
2
1
for (int x : take_view{ filter_view{ v, [](int x) { return x % 2; } }, 3 })
2
    cout << x << ' '; // -5 -3 -1

当需要将一个视图（如filter_view）的输出（如“-5 -3 -1 1 3 5”）作为另一个视图（如take_view）的输入，以获得进一步的输出（如“-5 -3 -1”）时，可以用管道操作符（|）将这些视图连接起来。这比视图嵌套的写法更容易理解。例如：

xxxxxxxxxx
2
1
for (int x : v | filter([](int x) { return x % 2; }) | take(3))
2
    cout << x << ' '; // -5 -3 -1

std::ranges::views命名空间中的filter和take函数会产生filter_view和take_view视图对象，并在管道操作符（|）和编译器的共同作用下，产生与视图嵌套完全等价的执行过程。

C++的管道操作符（|）显然是受到UNIX操作系统管道命令符（|）的影响，后者的作用是将一个命令的输出作为下一个命令的输入。管道操作的执行顺序是从左至右，即将左侧视图或范围的输出作为右侧视图的输入。位于最左侧的对象必须是范围或生成器。

象filter和take这样的函数称为过滤器函数。标准库提供的过滤器函数都位于std::ranges::views命名空间中。借助using指令或using声明，可以省略函数名前面的命名空间前缀，就象上面代码中的写法，但显式写上“views::”会令代码更加可读。例如：

xxxxxxxxxx
2
1
for (int x : v | views::filter([](int x) { return x % 2; }) | views::take(3))
2
    cout << x << ' '; // -5 -3 -1

视图和管道的实现，涉及到一些令人毛骨悚然的模板元编程。如果对性能心存疑虑，不妨在经实际测量之后，选择性能更好的解决方案，包括回归传统的实现方式。例如：

xxxxxxxxxx
7
1
int n = 0;
2
for (int x : v)
3
    if (x % 2) {
4
        cout << x << ' '; // -5 -3 -1
5
        if (++n >= 3)
6
            break;
7
    }

相比于基于视图和管道的做法，传统方式的代码稍显繁琐且晦涩难懂。

14.5 概念概述

标准库在<concepts>头文件中提供了很多有用的概念，包括但不限于类型概念、迭代器概念和范围概念，等等。

14.5.1 类型概念

类型概念用于约束类型的属性和类型之间的关系。如下表所示：

很多代码都涉及到针对不同类型数据的混合处理，当然这些类型之间应该存在一定的关联性，比如string和const char*，或者int和double，它们要么是一种类型可以转换为另一种类型，要么是都可以转换为第三种类型。common_with用于检测这种类型混合是否可行，如果“common_with<U,V>”约束满足，即U和V共享同一个公共类型，则可以通过“common_type_t<U,V>”取得该公共类型。例如：

xxxxxxxxxx
6
1
template<typename U, typename V>
2
    requires common_with<U, V>
3
auto min(U u, V v) {
4
    common_type_t<U, V> _u = u, _v = v;
5
    return _u < _v ? _u : _v;
6
}

该函数用于求取两个相同或不同类型数据的最小值。类型虽然可以不同，但必须共享同一个公共类型，否则无法比较大小，因此这里使用了“common_with<U,V>”概念约束。在约束满足的前提下，进一步通过“common_type_t<U,V>”获取U和V共享的公共类型，并将参数u和v分别转换为该公共类型的变量_u和_v，借助“<”操作符比较大小，返回其中的较小者。

该函数可以如下方式调用：

xxxxxxxxxx
3
1
string a{ "hello" };
2
const char* b{ "world" };
3
cout << ::min(a, b) << endl; // hello，string和const char*共享的公共类型是string

或者这样调用：

xxxxxxxxxx
3
1
int c{ 1 };
2
double d{ 0.5 };
3
cout << ::min(c, d) << endl; // 0.5，int和double共享的公共类型是double

但不能这样调用：

xxxxxxxxxx
3
1
string a{ "hello" };
2
double d{ 0.5 };
3
cout << ::min(a, d) << endl; // 编译失败，string和double没有共享的公共类型

因为a的d类型string和double不满足common_with约束，即它们没有共享的公共类型，因此编译器不会生成针对string和double类型的模板实例化代码。最后因所调用函数不存在报告编译失败。

如果需要人为地将特定混合类型（如int和double）的共享公共类型，指定为与标准库定义的公共类型（如double）不同的类型（如int），可以通过特化std命名空间中的common_type模板实现。例如：

xxxxxxxxxx
6
1
namespace std {
2
    template<>
3
    struct common_type<int, double> {
4
        using type = int; // 标准库里定义的是double
5
    };
6
}

多数情况下并不需要特化标准库中的common_type模板，除非所操作的混合类型中包含某个自定义类型。

下面这组概念与比较有关：

截止目前，还没有编译器支持针对equality_comparable_with和equality_comparable概念的重载。

标准库中没有表示布尔类型的概念，不妨自己定义一个。例如：

xxxxxxxxxx
9
1
template<typename B>
2
concept Boolean = requires(B x, B y) {
3
    { x = true };
4
    { x = false };
5
    { x = (x == y) };
6
    { x = (x != y) };
7
    { x = !x };
8
    { x = (x = y) };
9
};

一个类型所能支持的基本操作，通常是模板需要关注的重点。以下概念用于根据所支持的基本操作对类型分类：

对一个自定义的类型而言，最理想的情况是满足regular概念的约束。使用这样的类型就象使用int一样简单，无需考虑特别的注意事项，极大地降低了用户的负担。除非提供了“==”操作符，绝大多数类其实只是semiregular，虽然它们可以是也应该是regular。

某些类型的对象可被当做函数调用，这样的类型需要满足可调用概念的约束。如下表所示：

函数的相等性保持指的是，针对相等的输入必然返回相等的输出，即若$x=y$$x=y$，则$f(x)=f(y)$$f(x)=f(y)$​。因此，regular_invocable和invocable的区别并不体现在代码上，而仅仅是语义上的区别。这两个概念的命名只是为了强调设计者的意图。

所谓等价关系，是指同时具备自反性、对称性和传递性的关系。因此equivalence_relation和relation仅仅是语义上的区别。

严格弱排序是标准库对所有比较操作的默认假定，比如“<”操作符。因此strict_weak_order和relation仅仅是语义上的区别。

14.5.2 迭代器概念

传统的标准库算法通过迭代器访问序列中的元素，因此有必要通过概念对迭代器类型进行分类。如下表所示：

信标的基本思想是，通过迭代器（p）从起始位置（begin）开始，遍历一个范围，直到该迭代器的目标元素（*p）使谓词（s）的值为真。通过这种方式，由起始位置和信标所圈定的范围，可被表示为形如“[begin:s(*p))”的左闭右开区间。

信标的另一种更简单形式，是令其参与和迭代器的相等性（==）比较，一旦相等即结束遍历。通过这种方式，由起始位置和信标所圈定的范围，可被表示为形如“[begin:p==s)”的左闭右开区间。

最常见的信标是指向遍历范围中最后一个元素的下一个位置的迭代器，即终止迭代器（end）。这样的范围可被表示为形如“[begin:end)”的左闭右开区间。事实上，信标可以是任何类型的对象，只要其支持与迭代器的相等性（==）比较即可。

无论是“s(*p)”还是“p==s”，都需要信标（s）和迭代器（p）的类型满足sentinel_for概念的约束。例如：

xxxxxxxxxx
14
1
template<input_or_output_iterator Iter>
2
class Sentinel {
3
public:
4
    Sentinel() : m_end{} {} // sentinel_for概念要求必须有默认构造函数
5

6
    Sentinel(iter_value_t<Iter> end) : m_end{ end } {}
7

8
    friend bool operator==(const Iter& p, Sentinel s) {
9
        return *p == s.m_end;
10
    }
11

12
private:
13
    iter_value_t<Iter> m_end;
14
};

在使用Sentinel信标之前，不妨先检查一下信标类型“Sentinel<const char*>”和迭代器类型“const char*”是否满足sentinel_for概念的约束。例如：

xxxxxxxxxx
1
1
static_assert(sentinel_for<Sentinel<const char*>, const char*>);

若满足，则使用该信标，从一个字符串中提取出现在第一个换行符之前的字符。例如：

xxxxxxxxxx
2
1
const char* begin = "Hello\nWorld";
2
ranges::for_each(begin, Sentinel<const char*>{ '\n' }, [](char c) { cout << c; });

从程序的运行结果可以看出，位于“Hello”后面的换行符，连同其后的“World”都没有被输出。

14.5.3 范围概念

范围概念的定义位于<ranges>头文件的ranges命名空间中，用于刻画范围的各种属性。如下表所示：

<ranges>头文件里还有很多其它概念。这些概念的主要用途就是根据范围的类型属性，匹配合适的重载实现。

14.6 建议

• 当对标准库算法的迭代器版本感到厌倦时，不妨使用它们的范围版本

• 调用范围版本的算法函数，需要显式指明std::ranges命名空间

• 当对范围进行管道操作时，可以使用view、generator和filter表示

• 为了用谓词作为一个范围的结束，需要定义一个信标

• 可以使用static_assert检查特定类型是否满足某个概念约束

• 如果需要使用某个基于范围的算法，但标准库并没有提供，不妨自己定义一个

• 理想的类型都应该满足regular概念

• 尽可能选用标准库预定义好的概念

• 使用标准库算法，如果选择了并行策略，则需要规避竞争和死锁的风险