本文编译环境：clang-21，C++23标准。

迭代器#

迭代器（iterator）是 STL 的核心抽象之一：它将“如何遍历一个容器”与“容器本身的结构”解耦，让算法可以不关心底层数据结构。

用过 STL 的话，你一定见过类似这样的代码：

1
std::vector vec = {1, 2, 3, 4, 5};
2
for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
3
    std::print("{} ", *it);
4
}
5
std::println();
6

7
std::map<std::string, int> mp = {{"a", 1}, {"b", 2}};
8
for (std::map<std::string, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
9
    std::print("{}:{} ", it->first, it->second);
10
}
11
std::println();

vec.begin() 和 mp.begin() 返回的都是迭代器，但两者的底层结构截然不同——vector 是连续内存，map 是红黑树。迭代器将这种差异隐藏起来，对外统一提供 *、->、++ 这套接口。

我们平时写的范围 for 循环，本质上也是迭代器的语法糖：

1
for (auto& x : Container)  // 等价于用 begin()/end() 迭代

不同容器的迭代器，能力各不相同，本章将具体解释迭代器的分类与内部实现。

五种迭代器类型#

C++ 标准库将迭代器按能力分为五个等级，构成一个继承层次：

1
input_iterator_tag / output_iterator_tag
2
forward_iterator_tag        （继承自 input）
3
bidirectional_iterator_tag  （继承自 forward）
4
random_access_iterator_tag  （继承自 bidirectional）

这个层次反映的是”能做什么”：

类型	代表容器	支持操作
`input` / `output`	流迭代器（比如输入输出流）	单次单向遍历
`forward`	`std::forward_list`	多次单向遍历
`bidirectional`	`std::list`	双向遍历 (`++` / `--`)
`random_access`	`std::vector`、原生指针	随机访问（`+n`、`-n`、`[]`）

正如继承关系所示，每一级迭代器的约束都在逐渐增强：

input_iterator / output_iterator_tag：常见于输入/输出流。因为底层是流，数据读过即消失，无法回头也无法重复读取，不保证迭代器副本独立有效，因此只支持单次的单向遍历。std::istream_iterator 是典型代表。
forward_iterator_tag：在输入迭代器基础上增加了多遍保证——迭代器可以被复制，两个副本独立前进互不影响，同一位置可以反复解引用，但是只支持向前遍历（++ 操作）。比如单向链表 std::forward_list。
bidirectional_iterator_tag：在前向迭代器基础上增加了 -- 操作，支持向后移动。std::list、std::map、std::set 等的迭代器属于这级，双向链表和红黑树都能在节点间双向跳转，但一次跳n步只能一步步来。
random_access_iterator_tag：在双向迭代器基础上增加了 $O(1)$ 的任意跳跃（即随机访问能力），支持 it + n、it - n、it1 - it2 和 it[n]，以及迭代器之间的大小比较 <、>。std::vector、std::deque 的迭代器属于这级。std::sort 等算法要求这级，因为内部需要 $O(1)$ 的分治跳跃。
contiguous_iterator_tag（C++17 概念引入，C++20 正式有标签）：在随机访问基础上额外保证内存物理连续，std::vector、std::array 和裸数组满足这级，std::deque 虽然支持随机访问但内存不完全连续，因此不满足。这个tag主要在拷贝时有效，如果物理内存完全连续，那么就是直接将 std::copy 优化为一次 memcpy，但是某些支持随机访问但不完全连续的容器就不行。

这些 tag 不仅是“标记”，在后面我们会看到，它们也是编译期分发的关键。

`std::iterator` 的五个关联类型#

一个合规的迭代器需要向外暴露五个类型信息，STL 算法依赖这些信息工作：

类型名	含义
`value_type`	迭代器指向的元素类型
`pointer`	元素的指针类型
`reference`	元素的引用类型
`difference_type`	两个迭代器之间距离的类型（通常是 `ptrdiff_t`）
`iterator_category`	迭代器类别 tag

看不懂没关系，继续往下看实例。

实现一个自定义迭代器#

这一节的目标是实现一个带哨兵节点的双向链表 my_list<T>，并为它配套实现一个符合规范的自定义迭代器。显然，对于一个自己手动实现的双向链表，不能直接通过 std::iterator 进行遍历，因此我们需要实现一个配套的自定义迭代器。

双向链表实现如下：

1
template <typename T>
2
class my_list {
3
private:
4
    struct node {
5
        T data = 0;
6
        node *prev = nullptr;
7
        node *next = nullptr;
8
    };
9
    node* _head;
10
    node* _tail;
11

12
public:
13
    my_list() : _head(new node()), _tail(new node()) {
14
        _head->next = _tail;
15
        _tail->prev = _head;
16
    }
17

18
    void push_back(const T &elem) {
19
        node *new_node = new node{elem, nullptr, _tail};
20
        new_node->prev = _tail->prev;
21
        _tail->prev->next = new_node;
22
        _tail->prev = new_node;
23
    }
24

25
    void push_front(const T &elem) {
26
        node *new_node = new node{elem, _head, nullptr};
27
        new_node->next = _head->next;
28
        _head->next->prev = new_node;
29
        _head->next = new_node;
30
    }
31

32
    void print() {
33
        auto current = _head->next;
34
        while (current != _tail) {
35
            std::print("{} ", current->data);
36
            current = current->next;
37
        }
38
        std::println();
39
    }
40

41
    ~my_list() {
42
        auto current = _head->next;
43
        delete _head;
44
        while (current != _tail) {
45
            _head = current;
46
            current = current->next;
47
            delete _head;
48
        }
49
        delete _tail;
50
    }
51
};

使用哨兵节点（dummy head / tail）的好处是：begin() 返回 _head->next，end() 返回 _tail，边界条件统一，无需特判。

迭代器的实现如下：

1
struct iterator {
2
    using value_type        = T;
3
    using pointer           = T*;
4
    using reference         = T&;
5
    using difference_type   = std::ptrdiff_t;
6
    using iterator_category = std::bidirectional_iterator_tag;  // 双向，不是随机访问
7

8
    node* ptr;
9

10
    reference operator*()  const { return ptr->data; }
11
    pointer   operator->() const { return &ptr->data; }
12

13
    bool operator==(const iterator& o) const { return ptr == o.ptr; }
14
    bool operator!=(const iterator& o) const { return ptr != o.ptr; }
15

16
    // ++ 的语义是跳到 next 节点，而不是地址 +1
17
    iterator& operator++() { ptr = ptr->next; return *this; }
18
    iterator  operator++(int) { auto tmp = *this; ptr = ptr->next; return tmp; }
19

20
    // 双向迭代器特有：往回走
21
    iterator& operator--() { ptr = ptr->prev; return *this; }
22
    iterator  operator--(int) { auto tmp = *this; ptr = ptr->prev; return tmp; }
23

24
    // 没有 +n、-n、[] - 链表做不到随机访问
25
};
26

27
iterator begin() { return {_head->next}; }
28
iterator end()   { return {_tail}; }

关联类型#

对于一个迭代器而言，我们需要首先指定它的五个关联类型，对于这个双向链表的迭代器，它的五个关联信息分别是：

value_type = T：迭代器所指向的元素类型，即链表存储的数据类型。解引用 *it 返回的就是这个类型的值。
pointer = T*：元素的指针类型，即 value_type*。operator->() 的返回类型就是它，用于支持 it->member 这样的访问语法。
reference = T&：元素的引用类型，即 value_type&。operator*() 的返回类型就是它，表示解引用后得到的是元素本身的引用，而不是拷贝，所以 *it = 42 可以直接修改链表中的元素。
difference_type = std::ptrdiff_t：表示两个迭代器之间距离的类型。对链表来说虽然没有 it1 - it2 运算符，但 std::distance 等算法内部需要用这个类型来计数，所以仍然需要声明。std::ptrdiff_t 是标准的有符号整数类型，基本上固定用它即可。
iterator_category = std::bidirectional_iterator_tag：声明这个迭代器属于哪个级别。这是五个类型里最关键的一个，STL 算法在编译期通过它做分发——标记为双向迭代器后，std::sort 等要求随机访问的算法会在编译期直接报错，std::reverse 等只需要双向迭代器的算法则可以正常使用。

必要运算符#

以下是实现一个双向迭代器所必须的部件：

引用与解引用：reference 和 pointer。
比较运算符：== 和 !=。
前进（前向迭代）：++iter 和 iter++。
后退（反向迭代）：--iter 和 iter--。
可以补充的是 const_iterator 相关的代码，本文暂时不需要所以省略。

测试#

我们可以对于这个双向链表类进行一些简单的测试：


85 collapsed lines
1
#include <algorithm>
2
#include <ranges>
3
#include <string>
4
#include <print>
5

6
template <typename T>
7
class my_list {
8
private:
9
    struct node {
10
        T data = 0;
11
        node *prev = nullptr;
12
        node *next = nullptr;
13
    };
14
    node* _head;
15
    node* _tail;
16

17
public:
18
    my_list() : _head(new node()), _tail(new node()) {
19
        _head->next = _tail;
20
        _tail->prev = _head;
21
    }
22
    void push_back(const T &elem) {
23
        node *new_node = new node{elem, nullptr, _tail};
24
        new_node->prev = _tail->prev;
25
        _tail->prev->next = new_node;
26
        _tail->prev = new_node;
27
    }
28

29
    void push_front(const T &elem) {
30
        node *new_node = new node{elem, _head, nullptr};
31
        new_node->next = _head->next;
32
        _head->next->prev = new_node;
33
        _head->next = new_node;
34
    }
35

36
    void print() {
37
        auto current = _head->next;
38
        while (current != _tail) {
39
            std::print("{} ", current->data);
40
            current = current->next;
41
        }
42
        std::println();
43
    }
44

45
    ~my_list() {
46
        auto current = _head->next;
47
        delete _head;
48
        while (current != _tail) {
49
            _head = current;
50
            current = current->next;
51
            delete _head;
52
        }
53
        delete _tail;
54
    }
55

56
    struct iterator {
57
        using value_type        = T;
58
        using pointer           = T*;
59
        using reference         = T&;
60
        using difference_type   = std::ptrdiff_t;
61
        using iterator_category = std::bidirectional_iterator_tag;  // 注意：双向，不是随机访问
62

63
        node* ptr;
64

65
        reference operator*()  const { return ptr->data; }
66
        pointer   operator->() const { return &ptr->data; }
67

68
        bool operator==(const iterator& o) const { return ptr == o.ptr; }
69
        bool operator!=(const iterator& o) const { return ptr != o.ptr; }
70

71
        // ++ 的语义是跳到 next 节点，而不是地址 +1
72
        iterator& operator++() { ptr = ptr->next; return *this; }
73
        iterator  operator++(int) { auto tmp = *this; ptr = ptr->next; return tmp; }
74

75
        // 双向迭代器特有：往回走
76
        iterator& operator--() { ptr = ptr->prev; return *this; }
77
        iterator  operator--(int) { auto tmp = *this; ptr = ptr->prev; return tmp; }
78

79
        // 没有 +n、-n、[]，链表做不到 O(1) 跳跃
80
    };
81

82
    iterator begin() { return {_head->next}; }
83
    iterator end()   { return {_tail}; }
84
};
85

86
int main() {
87
    my_list<int> lst;
88
    lst.push_back(1);
89
    lst.push_back(2);
90
    lst.push_back(3);
91
    lst.push_front(0);
92
    lst.push_front(-1);
93
    lst.print();  // 输出: -1 0 1 2 3
94

95
    for (auto iter = std::begin(lst); iter != std::end(lst); ++iter) {  // 输出: -1 0 1 2 3
96
        std::print("{} ", *iter);
97
    }
98
    std::println();
99
    for (auto& iter : lst) {  // 输出: -1 0 1 2 3
100
        std::print("{} ", iter);
101
    }
102
    std::println();
103
    for (auto& iter : std::ranges::reverse_view(lst)) {  // 输出: 3 2 1 0 -1
104
        std::print("{} ", iter);
105
    }
106
    std::println();
107
}

如何泛化地对接 STL —— 以 `std::advance` 为例#

std::advance(iter, n) 的作用是让迭代器前进 $n$ 步。对不同类型的迭代器，最优实现截然不同，我们这里以双向迭代器和随机访问迭代器为例说明：

random_access：直接 iter += n， $O(1)$
bidirectional：由于不连续，只能循环 ++iter / --iter， $O(n)$

如果我们想根据上述标准库的实现方法，自己实现一个可泛化的 my_advance，可以用于和 std::advance 对接，最朴素的想法是运行期 if-else：

1
// 反面教材：运行期判断
2
template<typename Iter>
3
void my_advance_bad(Iter& iter, int n) {
4
    if (/* iter 是 random access？*/) {
5
        iter += n;
6
    } else {
7
        while (n--) ++iter;
8
    }
9
}

这有两个问题：

怎么在运行期判断迭代器类型？
更根本的问题是：对 bidirectional 迭代器，iter += n 根本不能编译——这必须是编译期决策，而不是运行期分支。比如我们在双向链表迭代器中完全没有实现 operator+=，那么对于该迭代器，iter += n 这行代码在编译阶段一定会报错（尽管我们可以在运行期确保不会走进该分支，但在编译期，编译器完全无法判断 iter 的类型）。

正确的做法是编译期分发（tag dispatch），而这需要知道迭代器的 iterator_category。因此，自定义的 iterator 泛化对接STL的核心问题就是：如何在编译期得到迭代器的类型信息，也就是我们前文中提到过的五个关联类型（对于 std::advance，最关键的类型信息自然是 iterator_category，这决定了具体调用的方法）。

Typename 关键字#

由于我们在迭代器中已经用五个 using 声明了对应的类型信息，现在要在模板中访问迭代器的 category，直觉上写法是：

1
template<typename Iter>
2
void my_advance(Iter& iter, int n) {
3
    Iter::iterator_category tag;  // 编译错误？
4
}

但是这行代码会编译失败，原因涉及 C++ 模板解析的一个核心规则：dependent name 问题。

依赖名称与二义性#

在模板中，Iter::iterator_category 是一个依赖名称（dependent name）——它的含义依赖于模板参数 Iter，在模板实例化之前编译器并不知道 Iter 是什么。

问题在于：Iter::iterator_category 既可以是一个类型，也可以是一个静态成员变量。考虑这两种情况：

1
struct A { using iterator_category = std::bidirectional_iterator_tag; };  // 类型
2
struct B { static int iterator_category; };                               // 变量

编译器在解析模板时，面对 T::something，默认假设它是值，而不是类型。因此：

1
Iter::iterator_category* tag;  // 编译器认为 Iter::iterator_category 是值, 这里的 * 会被解析为乘法运算符而非指针

这自然是错误的。我们需要显式告诉编译器：iterator_category 是一个类型。

`typename` 的作用#

1
typename Iter::iterator_category tag;

加上 typename，编译器才会正确地将 Iter::iterator_category 解析为类型名（也就是通过 typename 关键词告诉编译器，这里的 Iter::iterator_category 不会是变量，一定是类型）。

类型萃取（Type Traits）#

现在我们有了 typename，可以写出 typename Iter::iterator_category 来表示迭代器的类型。但还有一个场景没有解决：原生指针。比如 int* 也是合法的随机访问迭代器（可以 ptr + n、ptr[i]），但它没有任何成员类型，int*::iterator_category 根本不存在。

这就是 std::iterator_traits 要解决的问题。

类型萃取的设计逻辑 - 以 `iterator_traits` 为例#

1
// 通用版本：直接转发迭代器自身定义的五个关联类型
2
template <typename Iter>
3
struct iterator_traits {
4
    using value_type        = typename Iter::value_type;
5
    using pointer           = typename Iter::pointer;
6
    using reference         = typename Iter::reference;
7
    using difference_type   = typename Iter::difference_type;
8
    using iterator_category = typename Iter::iterator_category;
9
};

这里体现了模板编程的核心设计思路：用一个中间层结构体统一对外暴露类型信息，使得外部代码无需关心不同迭代器的内部实现差异，始终通过 iterator_traits<Iter>::xxx 这同一种方式访问所需的类型。也就是设置一个中间层，将类型的差异封装在萃取类内部，对外提供统一的访问接口。

对于 my_list::iterator 这样规范的自定义迭代器，通用版本的 iterator_traits 直接生效。

对原生指针的偏特化#

1
// 对 T* 的偏特化：手动填充这些信息
2
template <typename T>
3
struct iterator_traits<T*> {
4
    using value_type        = T;
5
    using pointer           = T*;
6
    using reference         = T&;
7
    using difference_type   = std::ptrdiff_t;
8
    using iterator_category = std::random_access_iterator_tag;
9
};

这就是类型萃取设计的精华所在：通过模板偏特化，为没有内嵌成员类型的类型（比如原生指针）补充元信息，使其融入统一接口。

调用方永远只需要写 iterator_traits<Iter>::iterator_category，无论 Iter 是自定义迭代器还是 int*，都能正确得到 category。

别名模板：告别冗长的 `typename`#

经过前面的铺垫，我们写出了正确的类型访问方式：

1
typename std::iterator_traits<Iter>::iterator_category

这行代码每次使用都要写这么长，很繁琐。C++11 引入的别名模板（alias template）可以解决这个问题：

1
template<typename Iter>
2
using iter_category_t = typename std::iterator_traits<Iter>::iterator_category;

此后直接写 iter_category_t<Iter> 即可，typename 被封装进别名定义里，使用侧不再需要重复书写。

`_t` 惯例#

这种把 typename ...::type 包装成 ..._t 的写法，从 C++14 起被标准库大量采用。例如：

1
// C++11 写法
2
typename std::remove_const<T>::type
3
typename std::decay<T>::type
4

5
// C++14 起的 _t 别名
6
std::remove_const_t<T>
7
std::decay_t<T>

对于 iterator_traits，标准库本身没有直接提供 _t 别名，但 C++20 引入了一套更现代的迭代器工具：

1
std::iter_value_t<Iter>       // = iterator_traits<Iter>::value_type
2
std::iter_reference_t<Iter>   // = iterator_traits<Iter>::reference
3
std::iter_difference_t<Iter>  // = iterator_traits<Iter>::difference_type

注意：C++20 的这套别名底层实现比 iterator_traits 更复杂，能处理更多边缘情况（如 range 的迭代器），但核心思想是一致的。

在 C++14/17 环境下，按需自定义 _t 别名是常见做法，也是标准库的编写惯例。

`my_advance` 的完整实现#

有了 iterator_traits，我们可以实现完整的 my_advance：

1
// 针对 bidirectional 的实现：逐步前进
2
template<typename Iter>
3
void my_advance_impl(Iter& iter, int dist, std::bidirectional_iterator_tag) {
4
    std::println("bidirectional_iterator, step forward {}.", dist);
5
    if (dist > 0) {
6
        while (dist--) ++iter;
7
    } else {
8
        while (dist++) --iter;
9
    }
10
}
11

12
// 针对 random_access 的实现：O(1) 跳跃
13
template<typename Iter>
14
void my_advance_impl(Iter& iter, int dist, std::random_access_iterator_tag) {
15
    std::println("random_access_iterator, step forward {}.", dist);
16
    iter += dist;
17
}
18

19
// 别名模板
20
template<typename Iter>
21
using iter_category_t = typename std::iterator_traits<Iter>::iterator_category;
22

23
// 对外接口：通过 iterator_traits 萃取 category，构造 tag 对象传入
24
template<typename Iter>
25
void my_advance(Iter& iter, int dist) {
26
    my_advance_impl(iter, dist, iter_category_t<Iter>());
27
}

这里有几个细节值得注意：

typename 再次出现：typename std::iterator_traits<Iter>::iterator_category —— Iter 是模板参数，所以 iterator_traits<Iter>::iterator_category 是 dependent name，必须加 typename。
Tag 对象：iter_category_t<Iter>() 构造了一个 tag 类型的临时对象，但这个对象本身没有任何数据，它只是作为类型信息的载体传递给重载函数，让编译器选择正确的 my_advance_impl 版本。整个分发过程发生在编译期，零运行时开销。
继承的作用：random_access_iterator_tag 继承自 bidirectional_iterator_tag。如果我们没有为 bidirectional 提供特化，编译器会自动匹配到 bidirectional 的版本（因为 random_access tag 可以隐式转换为 bidirectional tag）。这使得 tag dispatch 天然地支持”能力降级”。

验证一下效果：

1
int main() {
2
    my_list<int> lst;
3
    lst.push_back(1);
4
    lst.push_back(2);
5
    lst.push_back(3);
6
    lst.push_front(0);
7
    lst.push_front(-1);
8
    lst.print();
9
    auto it2 = std::begin(lst);
10
    my_advance(it2, 2);
11
    std::println("{}", *it2);   // 1
12
    my_advance(it2, -1);
13
    std::println("{}", *it2);   // 0
14

15
    int* arr = new int[10];
16
    std::iota(arr, arr + 10, 0);
17
    auto arr_iter = arr;
18
    my_advance(arr_iter, 5);
19
    std::println("{}", *arr_iter);  // 5
20
    my_advance(arr_iter, -2);
21
    std::println("{}", *arr_iter);  // 3
22
}

my_list 的迭代器走了 bidirectional 分支，原生指针走了 random_access 分支，完全符合预期。

用这一套 iterator_traits 的设计方案，用户只需要定义好五个关联类型，自定义的迭代器就能够对接所有可用的STL方法了。

迭代器#

五种迭代器类型#

std::iterator 的五个关联类型#