自定义迭代器：迭代器分类、迭代器标签与实现

迭代器这东西，说白了就是STL的灵魂。我做了这么多年C++，每次跟人聊STL，最后都会绕回到迭代器上。你想想看，没有迭代器，算法和容器就是两座孤岛，谁也挨不着谁。

今天咱们聊聊自定义迭代器。为什么要自己写迭代器？因为现实世界的数据结构，STL不可能全给你准备好。我曾在项目中封装过一个自定义的环形缓冲区，标准库里没有现成的迭代器，那就只能自己动手。

迭代器的五大分类

在动手写代码之前，得先搞清楚迭代器有哪些类型。STL把迭代器分成了五类，每一类的能力都不一样。

分类	能力	典型代表
输入迭代器	只读，单向，一次遍历	istream_iterator
输出迭代器	只写，单向，一次遍历	ostream_iterator
前向迭代器	读写，单向，可多次遍历	forward_list 的迭代器
双向迭代器	读写，可前可后	list、set、map 的迭代器
随机访问迭代器	读写，支持跳跃、下标、算术运算	vector、deque、array 的迭代器

这五类是有层级关系的。随机访问迭代器肯定也是双向迭代器，双向迭代器肯定也是前向迭代器。嗯，这里要注意：输入和输出迭代器是独立的，它们跟后面的三类不是继承关系，而是概念上的包含关系。

迭代器标签：STL的“身份证”

STL怎么知道一个迭代器属于哪一类？靠的就是迭代器标签。每个迭代器内部都定义了一个 iterator_category 类型，说白了就是一张身份证。

// 标准库定义的五个标签
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

为什么标签要用继承？我举个例子你就明白了。假设有个算法只要求前向迭代器，你传一个随机访问迭代器进去，它也能正常工作。因为随机访问迭代器的标签继承了前向迭代器的标签，编译器在重载决议时能匹配上。

我在项目中遇到过一个问题：写了一个算法，传了 std::list 的迭代器进去，结果编译报错。查了半天，发现算法内部用了 it + n 这种操作，而 list 的迭代器是双向的，不支持随机访问。从那以后，我写算法时都会用 iterator_category 做标签分发，提前规避这类问题。

自定义迭代器的完整实现

咱们来实现一个简单的自定义迭代器。假设我有一个固定大小的数组容器，叫 FixedArray，我想让它支持范围 for 循环和 STL 算法。

#include <iostream>
#include <iterator>
#include <algorithm>

template <typename T, std::size_t N>
class FixedArray {
public:
    // 迭代器类
    class Iterator {
    public:
        // 迭代器标签：随机访问
        using iterator_category = std::random_access_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;

        Iterator(pointer ptr) : m_ptr(ptr) {}

        // 解引用
        reference operator*() const { return *m_ptr; }
        pointer operator->() const { return m_ptr; }

        // 前向/后向
        Iterator& operator++() { ++m_ptr; return *this; }
        Iterator operator++(int) { Iterator tmp = *this; ++(*this); return tmp; }
        Iterator& operator--() { --m_ptr; return *this; }
        Iterator operator--(int) { Iterator tmp = *this; --(*this); return tmp; }

        // 随机访问
        Iterator& operator+=(difference_type n) { m_ptr += n; return *this; }
        Iterator& operator-=(difference_type n) { m_ptr -= n; return *this; }
        Iterator operator+(difference_type n) const { return Iterator(m_ptr + n); }
        Iterator operator-(difference_type n) const { return Iterator(m_ptr - n); }
        difference_type operator-(const Iterator& other) const { return m_ptr - other.m_ptr; }
        reference operator[](difference_type n) const { return *(m_ptr + n); }

        // 比较
        bool operator==(const Iterator& other) const { return m_ptr == other.m_ptr; }
        bool operator!=(const Iterator& other) const { return m_ptr != other.m_ptr; }
        bool operator<(const Iterator& other) const { return m_ptr < other.m_ptr; }
        bool operator>(const Iterator& other) const { return m_ptr > other.m_ptr; }
        bool operator<=(const Iterator& other) const { return m_ptr <= other.m_ptr; }
        bool operator>=(const Iterator& other) const { return m_ptr >= other.m_ptr; }

    private:
        pointer m_ptr;
    };

    // 容器接口
    Iterator begin() { return Iterator(data_); }
    Iterator end()   { return Iterator(data_ + N); }

    T& operator[](std::size_t index) { return data_[index]; }

private:
    T data_[N] = {};
};

这段代码里，我定义了 iterator_category 为 std::random_access_iterator_tag，意味着这个迭代器支持所有随机访问操作。你想想看，有了这个标签，std::sort、std::binary_search 这些算法就能直接用了。

标签分发：让算法更聪明

有了迭代器标签，我们就可以做标签分发。说白了，就是根据迭代器的类型，选择不同的算法实现。

// 标签分发辅助函数
template <typename RandomAccessIter>
void advance_impl(RandomAccessIter& it, typename std::iterator_traits<RandomAccessIter>::difference_type n,
                  std::random_access_iterator_tag) {
    it += n;  // 随机访问：直接跳
}

template <typename BidirectionalIter>
void advance_impl(BidirectionalIter& it, typename std::iterator_traits<BidirectionalIter>::difference_type n,
                  std::bidirectional_iterator_tag) {
    if (n > 0) while (n--) ++it;  // 双向：一步步走
    else while (n++) --it;
}

template <typename InputIter>
void advance_impl(InputIter& it, typename std::iterator_traits<InputIter>::difference_type n,
                  std::input_iterator_tag) {
    while (n--) ++it;  // 输入：只能往前走
}

// 对外接口
template <typename Iter>
void my_advance(Iter& it, typename std::iterator_traits<Iter>::difference_type n) {
    advance_impl(it, n, typename std::iterator_traits<Iter>::iterator_category());
}

这段代码展示了标签分发的核心思想。编译器会根据迭代器的标签类型，自动选择最合适的实现。随机访问迭代器直接跳，双向迭代器一步步走，输入迭代器只能往前走。效率拉满。

避坑指南

知识体系总览

下面这张图把自定义迭代器的核心脉络梳理了一遍，从分类到标签再到实现，一条线串下来。

自定义迭代器这件事，说难不难，说简单也不简单。核心就三点：搞清楚你的容器支持什么操作，选对迭代器标签，把五个内嵌类型和操作符实现完整。做到这三点，你的容器就能跟STL算法无缝衔接了。

我个人建议，刚开始写自定义迭代器时，先照着标准库的迭代器抄一遍，理解每个操作符的作用。等你写了两三个之后，就会发现其实套路很固定。嗯，说白了就是模板元编程里的那点事，多练几次就熟了。