C++迭代器原理与自定义实现指南

1. 迭代器与标准库算法的适配原理

在C++标准库中，算法与数据结构的解耦是通过迭代器实现的。这种设计使得算法可以独立于具体的数据结构工作，只要数据结构提供了符合要求的迭代器接口。标准库算法如sort()、find()等并不直接操作容器，而是通过迭代器来访问和修改元素。

迭代器本质上是指针的泛化，它提供了以下几种核心操作：

• 解引用（*iter）
• 递增/递减（++iter/--iter）
• 比较（iter1 != iter2）
• 随机访问（iter[n]，仅限随机访问迭代器）

标准库定义了五种迭代器类别，形成一个层次结构：

1. 输入迭代器（InputIterator）：只读，单次遍历
2. 输出迭代器（OutputIterator）：只写，单次遍历
3. 前向迭代器（ForwardIterator）：可读写，多次遍历
4. 双向迭代器（BidirectionalIterator）：可双向移动
5. 随机访问迭代器（RandomAccessIterator）：支持随机访问

2. 自定义迭代器的实现要点

当我们需要让自定义数据结构与标准库算法协同工作时，需要为其实现适当的迭代器。一个完整的自定义迭代器通常需要：

2.1 基本迭代器操作

cpp复制class CustomIterator {
public:
    // 解引用
    value_type& operator*() const;
    
    // 前置递增
    CustomIterator& operator++();
    
    // 后置递增
    CustomIterator operator++(int);
    
    // 相等比较
    bool operator==(const CustomIterator& other) const;
    
    // 不等比较
    bool operator!=(const CustomIterator& other) const;
    
    // 对于随机访问迭代器还需要实现
    value_type& operator[](difference_type n) const;
    CustomIterator& operator+=(difference_type n);
    // ...其他随机访问操作
};

2.2 迭代器特征（traits）

为了让算法能识别迭代器的能力，需要通过iterator_traits提供类型信息：

cpp复制namespace std {
template<>
struct iterator_traits<CustomIterator> {
    using difference_type = ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    using iterator_category = random_access_iterator_tag;
};
}

或者更简单的方式是让迭代器本身定义这些类型：

cpp复制class CustomIter