C++20 Range类型的具体使用

一、引言

在 C++ 编程中，经常需要处理序列化的数据，例如数组、列表或其他容器中的元素。为了高效且简洁地操作这些序列，C++20 引入了 Ranges 库，它提供了一种更强大、更灵活的方式来表达和处理数据序列。本篇将深入探讨 Range 的各种概念，例如 input_range, forward_range, bidirectional_range, random_access_range 等，以及它们之间的区别和应用场景，更好地理解和运用 Ranges 库。

Range 的定义和核心思想：Range 是一种对序列的抽象，它代表一个可以迭代访问其元素的集合。不同于传统的迭代器对（begin() 和 end()），Range 将序列视为一个单一的实体，简化了序列处理。一个 Range 通常由一个起始迭代器和一个结束迭代器（或哨兵）定义，用于标记序列的边界。

Ranges 库的引入极大地提高了代码的可读性和表达能力。它允许以更声明式的方式编写代码，专注于操作的逻辑而不是底层的迭代细节。

• Ranges 支持惰性求值，只有在真正需要时才会计算结果。这种特性可以显著提高代码的效率，尤其是在处理大型数据集时。
• Ranges 还可以轻松地组合各种视图，例如过滤、转换和排序，而不会产生额外的性能开销。这使得可以以一种非常简洁和灵活的方式构建复杂的数据处理管道。

为什么需要深入理解 Range 的类型？

• 不同的 Range 类型提供了不同的能力，例如单次遍历、多次遍历、随机访问等。理解这些类型的区别可以帮助选择最合适的算法，并最大程度地提高代码的性能。使用错误的 Range 类型会导致编译错误或运行时错误。
• 许多 C++ 标准库算法和第三方库已经开始支持 Ranges。深入理解 Range 的类型可以帮助更好地利用这些库，并编写更简洁、更高效的代码。

二、Range 概念基础

在深入探讨各种 Range 类型之前，需要先了解 Range 的一些基本概念和特征。虽然前面文章都介绍了很多次，但这里还是要简单回顾一下，有助于更好地理解不同 Range 类型之间的区别和联系。

迭代器与 Range 的关系：Range 的核心在于迭代器。每个 Range 都可以通过一对迭代器（或一个迭代器和一个哨兵）来表示。起始迭代器指向 Range 的第一个元素，结束迭代器（或哨兵）指向 Range 结尾的下一个位置。

Range 的能力由其迭代器的能力决定。例如，如果一个 Range 的迭代器支持双向移动，那么这个 Range 就支持双向遍历。

Range 的视图 (View) 提供了一种对 Range 进行非破坏性操作的方式。视图并不会复制底层的 Range 数据，而是提供了一个新的视角来观察和操作数据。

视图通常基于另一个 Range 创建，并提供不同的观察方式，例如转换、过滤或排序。视图是惰性求值的，只有在需要时才会计算结果。这可以提高代码的效率，尤其是在处理大型数据集。多个视图可以组合在一起，形成一个数据处理管道，而不会产生额外的性能开销。

三、深入理解 Range 的各种类型

这里详细介绍几种 Range 类型，包括 input_range，forward_range，bidirectional_range 和 random_access_range，并解释它们之间的区别、特性以及应用场景。

3.1、input_range (输入范围)

input_range 是最基本的 Range 类型。它的迭代器只能单次向前移动，即只能遍历 input_range 一次；每次递增迭代器后，之前迭代器所指向的元素可能会失效。

无法保证不同迭代器指向相同的元素时，它们的值是否相等。

input_range 适用于处理只能读取一次的数据流，例如从网络套接字或传感器读取数据。

典型操作：

• 读取元素：可以使用 *it 获取当前迭代器指向的元素值。
• 前移迭代器：可以使用 ++it 将迭代器移动到下一个元素。
• 不支持多次遍历：一旦遍历完成，就不能再次遍历同一个 input_range。
• input_range 的迭代器不支持写入操作。

应用场景：

• 一次性处理数据流：例如，从输入流（例如文件或网络流）读取数据。
• 传感器数据读取：从传感器读取数据流，这些数据通常只能读取一次。

示例：

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <list>
#include <sstream>
#include <iterator>

void demonstrate_input_range() 
{
    std::istringstream input_stream("1 2 3 4 5 6");
    std::ranges::input_range auto int_range = std::ranges::istream_view<int>(input_stream);

    std::cout << "从 input stream 读取数据: " << std::endl;
    for (int value : int_range) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    // 尝试再次遍历 input_range (这将输出未定义的内容，因为 input_range 只能遍历一次)
    std::cout << "再次遍历 input stream: "<< std::endl;
    for (int value : int_range) {
        std::cout << value << " ";
    }
    std::cout << std::endl;

    std::cout << "使用 std::ranges::for_each 消费 input_range" << std::endl;
    std::istringstream input_stream2("6 7 8 9 10");
    std::ranges::input_range auto int_range2 = std::ranges::istream_view<int>(input_stream2);

    std::ranges::for_each(int_range2, [](int value) { std::cout << value * 2 << " "; });
    std::cout << std::endl;
}

int main() 
{
    demonstrate_input_range();
    return 0;
}

输出内容：

从 input stream 读取数据: 

1 2 3 4 5 6 

再次遍历 input stream: 

使用 std::ranges::for_each 消费 input_range

12 14 16 18 20 

3.2、forward_range (前向范围)

forward_range 扩展了 input_range 的功能，它支持多次向前遍历 Range 中的元素。即可以多次遍历同一个 forward_range，并且每次遍历的结果都是一致的。

forward_range 的迭代器是多遍的，可以保存迭代器的副本，并在稍后使用它重新访问相同的元素。递增迭代器不会使其他迭代器失效。

与 input_range 的区别：

• forward_range 具备 input_range 的所有能力，即单次向前遍历和读取元素。
• forward_range 的主要区别在于它支持多次遍历，而 input_range 只支持单次遍历。 这是因为 forward_range 的迭代器是多遍的，而 input_range 的迭代器是单遍的。

典型操作：

• 可以多次循环遍历 forward_range 中的元素。
• 可以使用 std::ranges::find 等算法在 forward_range 中查找特定元素。
• 可以使用 std::ranges::count 等算法统计 forward_range 中满足特定条件的元素个数。

需要多次遍历同一序列的应用场景：

• 对数据进行多次分析或处理。
• 在数据中查找多个元素。
• 缓存数据以便后续使用。

许多标准库算法都需要 forward_range，例如 std::ranges::sort (虽然它需要更强的 random_access_range)， std::ranges::find，std::ranges::count 等。

示例：

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <list>
#include <sstream>
#include <iterator>

// 演示 forward_range
void demonstrate_forward_range() 
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 多次遍历 forward_range
    std::cout << "第一次遍历 forward_range: ";
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    std::cout << "第二次遍历 forward_range: ";
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    // 使用 std::ranges::find 查找元素
    auto it = std::ranges::find(numbers, 3);
    if (it != numbers.end()) {
        std::cout << "找到元素 3" << std::endl;
    }
}

int main() 
{
    demonstrate_forward_range();
    return 0;
}

结果输出：

第一次遍历 forward_range: 1 2 3 4 5 

第二次遍历 forward_range: 1 2 3 4 5 

找到元素 3

3.3、bidirectional_range

定义和特性：

• bidirectional_range 扩展了 forward_range 的功能，支持向前和向后遍历元素。
• bidirectional_range 的迭代器可以递增 (++it) 和递减 (--it)。
• 与 forward_range 一样，bidirectional_range 的迭代器也是多遍的。

与 forward_range 的区别：

• bidirectional_range 具备 forward_range 的所有能力，包括多次向前遍历和读取元素。
• bidirectional_range 的主要区别在于它支持反向遍历，而 forward_range 只支持向前遍历。

典型操作：

• 正向遍历：与 forward_range 相同。
• 反向遍历：可以使用反向迭代器 (rbegin() 和 rend()) 进行反向遍历。
• 双向查找：可以向前和向后搜索元素。

应用场景：

• std::list 是一个典型的双向范围。
• 需要反向处理序列的场景。
• 某些算法需要双向遍历的能力，例如反向排序。

示例：

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <list>
#include <sstream>
#include <iterator>

void demonstrate_bidirectional_range() 
{
    std::list<int> numbers = {1, 2, 3, 4, 5};

    // 正向遍历 bidirectional_range
    std::cout << "正向遍历 bidirectional_range: ";
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;

    // 反向遍历 bidirectional_range
    std::cout << "反向遍历 bidirectional_range: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用 std::ranges::find 查找元素 (正向)
    auto it = std::ranges::find(numbers, 3);
    if (it != numbers.end()) {
        std::cout << "正向找到元素 3" << std::endl;
    }

    // 使用 std::ranges::find 查找元素 (反向) - 需要使用 std::ranges::reverse_view
    auto reversed_numbers = std::ranges::reverse_view{numbers};
    auto it_reverse = std::ranges::find(reversed_numbers, 3);
    if (it_reverse != reversed_numbers.end()) {
        std::cout << "反向找到元素 3" << std::endl;
    }
}

int main() 
{
    demonstrate_bidirectional_range();
    return 0;
}

3.4、random_access_range

定义和特性：

• random_access_range 扩展了 bidirectional_range 的功能，支持随机访问元素，就像数组一样。
• 可以使用索引运算符 [] 直接访问 Range 中的任何元素。
• random_access_range 的迭代器支持指针算术运算，例如 it + n、it - n、it[n]、it1 - it2 等。
• 迭代器也支持比较运算符 <、>、<=、>=。

与 bidirectional_range 的主要区别在于random_access_range支持高效的随机访问，而 bidirectional_range 需要通过多次递增或递减迭代器来访问特定元素。

典型操作：

• 索引访问：可以使用 [] 运算符直接访问元素。
• 排序：可以使用 std::ranges::sort 等算法对 random_access_range 进行排序。
• 二分查找：可以使用 std::ranges::binary_search 等算法在已排序的 random_access_range 中进行高效的二分查找。

应用场景举例：

• std::vector、std::array、std::deque 是典型的随机访问范围。
• 需要快速访问任意元素的场景。
• 许多算法需要随机访问的能力，例如排序、二分查找等。

示例：

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <list>
#include <array>
#include <sstream>
#include <iterator>

void demonstrate_random_access_range() 
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};

    // 随机访问 random_access_range
    std::cout << "随机访问 random_access_range: ";
    std::cout << numbers[0] << " " << numbers[2] << std::endl;

    // 使用 std::ranges::sort 排序
    std::ranges::sort(numbers); // 注意：示例简单，vector已排序

    std::cout << "排序后的 random_access_range: ";
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;


    // 使用 std::ranges::sort 反向排序
    std::ranges::sort(numbers, std::greater<int>());

    std::cout << "反向排序后的 random_access_range: ";
    for (int number : numbers) {
        std::cout << number << " ";
    }
    std::cout << std::endl;
}

int main() 
{
    demonstrate_random_access_range();
    return 0;
}

输出：

随机访问 random_access_range: 1 3

排序后的 random_access_range: 1 2 3 4 5 

反向排序后的 random_access_range: 5 4 3 2 1 

3.5、contiguous_range

contiguous_range 是 random_access_range 的一个特例，其元素在内存中是连续存储的。可以像数组一样，通过指针算术直接访问元素。

contiguous_range 的 data() 成员函数返回一个指向底层连续内存块的指针。高效的内存访问和缓存利用率是其主要优势。

contiguous_range 的主要区别在于它的元素保证在内存中是连续的，而 random_access_range 不一定保证连续性 (例如 std::deque 在存储大量元素时，底层可能不是连续的).

典型操作：

• 直接内存访问：通过 data() 获取指向底层数据的指针，然后使用指针算术进行操作。
• 高效的数据复制：可以利用连续性进行高效的内存块复制。
• 与 C 风格 API 的互操作性：可以直接将 data() 返回的指针传递给 C 风格的函数。

应用场景举例：

• std::vector、std::array、std::string 是典型的连续范围。
• 需要高效内存访问和操作的场景。
• 与需要连续内存块的 C 风格 API 交互的场景。

示例：

#include <iostream>
#include <vector>
#include <ranges>
#include <algorithm>
#include <list>
#include <array>
#include <string>
#include <sstream>
#include <iterator>

void demonstrate_contiguous_range() 
{
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {1, 2, 3, 4, 5};
    std::string str = "hello";

    // 使用 data() 获取指向底层数据的指针
    int* vec_ptr = vec.data();
    int* arr_ptr = arr.data();
    char* str_ptr = str.data();

    // 使用指针算术遍历 contiguous_range
    std::cout << "使用指针遍历 vector: ";
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << *(vec_ptr + i) << " ";
    }
    std::cout << std::endl;

    std::cout << "使用指针遍历 array: ";
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << *(arr_ptr + i) << " ";
    }
    std::cout << std::endl;

    std::cout << "使用指针遍历 string: ";
    for (size_t i = 0; i < str.size(); ++i) {
        std::cout << *(str_ptr + i);
    }
    std::cout << std::endl;
}

int main() 
{
    demonstrate_contiguous_range();
    return 0;
}

输出：

使用指针遍历 vector: 1 2 3 4 5 

使用指针遍历 array: 1 2 3 4 5 

使用指针遍历 string: hello

四、类型之间的层次结构与选择

C++20 中的 Range 概念建立在迭代器类别之上，形成了一个明确的层次结构，旨在精确描述可迭代序列的能力。这种层次结构意味着更高级别的 Range 概念包含了低级别 Range 的所有能力，从而允许算法根据 Range 的能力自动选择最有效的实现。

• std::ranges::input_range: 这是最基本的 Range 类型，适用于一次性消费的序列。
• std::ranges::forward_range: 是一个比 input_range 更强的概念。其迭代器是可复制的，并且 begin() 可以被多次调用，允许对序列进行多遍遍历。
• std::ranges::bidirectional_range: 在 forward_range 的基础上，增加了双向遍历的能力。
• std::ranges::random_access_range: 在 bidirectional_range 的基础上，增加了随机访问的能力。
• std::ranges::contiguous_range: 这是最强的 Range 类型，表示其元素在内存中是连续存储的，并且大小相同，可以通过指针算术进行访问。

这种层次结构的关键在于，如果一个 Range 满足了某个更高级别的概念，那么它也自动满足了所有比它低级别的概念，但 input_range 不包含 output_range 的写入能力。

选择合适的 Range 类型对于编写高效、正确且可读的 C++ 代码至关重要。C++20 Ranges 库通过概念在编译时强制执行这些要求，从而提高了代码的健壮性。

性能考量：

• 算法的效率往往取决于其所操作的 Range 的能力。
• C++20 Ranges 算法会利用 Range 的概念信息，自动选择最适合给定 Range 类型的算法实现，从而在编译时优化性能。
• 虽然理论上使用更高级别的 Range 总是更好，但在某些特定场景下，如果仅仅需要简单的单次遍历，使用 input_range 或 output_range 这样的基本类型更合适，因为它避免了不必要的开销或复杂性。

五、总结

C++20 引入的 Ranges 库提供了一种强大且灵活的机制来处理序列数据。通过定义 input_range、forward_range、bidirectional_range、random_access_range 和 contiguous_range 等不同类型的 Range，Ranges 库能够更精确地表达序列的能力，从而实现更高效的算法选择和执行

C++20 Ranges 库的设计理念是根据 Range 的能力自动选择最优的算法实现。因此，选择合适的 Range 类型不仅可以提高代码的可读性和可维护性，还能在编译时优化性能，避免不必要的开销。