第8.4章: 迭代器算法

English

概述

算法作用于迭代器。算法既不知道也不关心底层容器，只要求迭代器具备某些能力。

本章将介绍：

1. 算法依赖迭代器的能力

每个算法都有最低的迭代器要求。这些要求决定了算法能否：

更强的迭代器类别能支撑更强的算法。

2. 算法能力的阶梯


input_iterator
    ↓
forward_iterator
    ↓
bidirectional_iterator
    ↓
random_access_iterator
    ↓
contiguous_iterator

每上升一级都会带来新的算法可能性。

3. 需要 input_iterator 的算法

这些算法只需要向前移动并读取元素一次：

They work on the weakest readable iterators.

4. 需要 forward_iterator 的算法

这些算法要求对同一批元素进行多次遍历：

forward_iterator 保证可以多遍遍历。

5. 需要 bidirectional_iterator 的算法

这些算法要求能够向后移动：

6. 需要 random_access_iterator 的算法

这些算法要求常数时间跳跃：

随机访问使得下标访问和划分成为可能。

迭代器算法

迭代器算法直接作用于迭代器对： 


::std::sort(vec.begin(), vec.end());

这种形式要求 random_access_iterator。

ranges 算法

ranges 算法也可以接受迭代器对： 


::std::ranges::sort(vec.begin(), vec.end());

也可以直接接受整个 range： 


::std::ranges::sort(vec);

两种形式要求相同的迭代器类别。

带比较对象的算法

算法可以接受来自 <functional> 的比较对象。这些对象在迭代器算法与 ranges 算法中都可用。

迭代器算法形式：


::std::sort(vec.begin(), vec.end(), ::std::greater<>{});

ranges 算法形式（迭代器对）：


::std::ranges::sort(vec.begin(), vec.end(), ::std::ranges::greater{});

ranges 算法形式（整个 range）：


::std::ranges::sort(vec, ::std::ranges::greater{});

比较对象不会改变对迭代器类别的要求。

7. 受益于 contiguous_iterator 的算法

contiguous_iterator 让编译器能够推理内存布局，从而带来这些优化：

指向对象类型的指针和 ::fast_io::vector<T> 的迭代器都是 contiguous_iterator。

8. fast_io 容器与迭代器算法

::fast_io::vector<T> 提供连续迭代器。需要随机访问或能从连续性中获益的算法会走最强的那条路径。

fast_io 的其他容器遵循与 STL 对应容器相同的迭代器规则。

9. 用 if constexpr 探测算法是否适用

你可以写出随迭代器或 range 强弱自动调整的算法。类型由函数参数推导，if constexpr 在编译期选择对应的路径。

迭代器版本


template <typename It>
void analyze(It first, It last)
{
    if constexpr(::std::random_access_iterator<It>)
        print("iterator: random-access fast path\n");
    else
        print("iterator: generic path\n");
}

调用方式很直接：


int arr[]{1,2,3,4};
analyze(arr, arr + 4);                 // arr decays to int*


::fast_io::vector<int> vec{1,2,3,4};
analyze(vec.begin(), vec.end());       // deduces ::fast_io::vector<int>::iterator

range 版本

你也可以写一个接受整个 range 的重载： 


template <typename T>
void analyze(T& r)
{
    if constexpr(::std::ranges::random_access_range<T>)
        print("range: random-access fast path\n");
    else
        print("range: generic path\n");
}

调用 range 版本：


analyze(vec);                          // detects random_access_range

两个重载都会根据迭代器或 range 的类别自动调整。

10. 常见陷阱

要点

← 第8.3章: 迭代器类别 ↑ 主页 第8.5章: 投影 →