前言

在STL的设计中，迭代器扮演着"万能胶水"的角色，它优雅地连接了容器和算法。正如Bjarne Stroustrup所说："C++的STL之所以强大，很大程度上得益于迭代器抽象。"本文将深入探讨迭代器的分类、实现原理以及如何自定义迭代器，让你彻底理解这一核心组件。

一、迭代器分类及其特性

迭代器不是单一类型，而是根据功能分为五大类别，每一类都有特定的能力和限制。

迭代器类别层次结构

#include <iterator>

// 迭代器五大类别
struct input_iterator_tag {};        // 输入迭代器
struct output_iterator_tag {};       // 输出迭代器
struct forward_iterator_tag {};      // 前向迭代器
struct bidirectional_iterator_tag {};// 双向迭代器
struct random_access_iterator_tag {};// 随机访问迭代器

各类迭代器的特性

1. 输入迭代器(Input Iterator)

• 能力：只能读取，只能前向移动，只能单遍扫描
• 典型应用：istream_iterator
• 支持操作：++, *, ->, ==, !=

#include <iostream>
#include <iterator>

void demo_input_iterator() {
    std::istream_iterator<int> input(std::cin);
    std::istream_iterator<int> end;
    
    while (input != end) {
        std::cout << "Read: " << *input << std::endl;
        ++input;
    }
}

2. 输出迭代器(Output Iterator)

• 能力：只能写入，只能前向移动，只能单遍扫描
• 典型应用：ostream_iterator
• 支持操作：++, * (仅用于赋值)

#include <iostream>
#include <iterator>
#include <vector>

void demo_output_iterator() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::ostream_iterator<int> output(std::cout, " ");
    
    for (int val : vec) {
        *output = val;  // 写入输出流
        ++output;
    }
}

3. 前向迭代器(Forward Iterator)

• 能力：可读写，可前向移动，可多遍扫描
• 典型应用：forward_list的迭代器
• 支持操作：包含输入输出迭代器的所有操作

4. 双向迭代器(Bidirectional Iterator)

• 能力：在前向迭代器基础上增加反向移动能力
• 典型应用：list, set, map的迭代器
• 支持操作：增加 -- 操作

#include <list>

void demo_bidirectional_iterator() {
    std::list<int> lst = {1, 2, 3, 4, 5};
    auto it = lst.end();
    
    // 反向遍历
    while (it != lst.begin()) {
        --it;
        std::cout << *it << " ";
    }
}

5. 随机访问迭代器(Random Access Iterator)

• 能力：在双向迭代器基础上支持随机访问
• 典型应用：vector, deque, 原始指针
• 支持操作：增加 +, -, [], <, > 等操作

#include <vector>

void demo_random_access_iterator() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = vec.begin();
    
    // 随机访问
    std::cout << "Third element: " << it[2] << std::endl;
    std::cout << "Distance: " << (vec.end() - vec.begin()) << std::endl;
}

迭代器类别关系图

随机访问迭代器 → 双向迭代器 → 前向迭代器 → 输入迭代器
                             → 输出迭代器

二、迭代器萃取器(Traits)技术

迭代器萃取是STL中最重要的元编程技术之一，它允许算法在编译时获取迭代器的特性信息。

为什么需要迭代器萃取？

考虑这样一个问题：如何实现一个distance函数计算两个迭代器之间的距离？

template<typename Iterator>
typename std::iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last) {
    // 我们需要知道迭代器类别来选择最优算法
}

迭代器萃取器的实现

// 基本的迭代器特质模板
template<typename Iterator>
struct iterator_traits {
    using iterator_category = typename Iterator::iterator_category;
    using value_type        = typename Iterator::value_type;
    using difference_type   = typename Iterator::difference_type;
    using pointer           = typename Iterator::pointer;
    using reference         = typename Iterator::reference;
};

// 针对原始指针的特化版本
template<typename T>
struct iterator_traits<T*> {
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;
};

// 针对const指针的特化版本
template<typename T>
struct iterator_traits<const T*> {
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = const T*;
    using reference         = const T&;
};

使用萃取器实现通用算法

// 根据迭代器类别选择不同的实现
template<typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_impl(InputIterator first, InputIterator last, 
              std::input_iterator_tag) {
    // 线性复杂度实现，用于输入迭代器
    typename iterator_traits<InputIterator>::difference_type n = 0;
    while (first != last) {
        ++first;
        ++n;
    }
    return n;
}

template<typename RandomAccessIterator>
typename iterator_traits<RandomAccessIterator>::difference_type
distance_impl(RandomAccessIterator first, RandomAccessIterator last,
              std::random_access_iterator_tag) {
    // 常数复杂度实现，用于随机访问迭代器
    return last - first;
}

// 统一的distance接口
template<typename Iterator>
typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last) {
    return distance_impl(first, last,
        typename iterator_traits<Iterator>::iterator_category());
}

三、自定义迭代器实现

让我们实现一个简单的自定义迭代器，用于遍历一个固定数组。

基本迭代器实现

template<typename T>
class ArrayIterator {
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&;
    
    // 构造函数
    explicit ArrayIterator(T* ptr = nullptr) : ptr_(ptr) {}
    
    // 解引用操作
    reference operator*() const { return *ptr_; }
    pointer operator->() const { return ptr_; }
    
    // 前缀递增
    ArrayIterator& operator++() {
        ++ptr_;
        return *this;
    }
    
    // 后缀递增
    ArrayIterator operator++(int) {
        ArrayIterator temp = *this;
        ++ptr_;
        return temp;
    }
    
    // 前缀递减
    ArrayIterator& operator--() {
        --ptr_;
        return *this;
    }
    
    // 后缀递减
    ArrayIterator operator--(int) {
        ArrayIterator temp = *this;
        --ptr_;
        return temp;
    }
    
    // 随机访问操作
    ArrayIterator operator+(difference_type n) const {
        return ArrayIterator(ptr_ + n);
    }
    
    ArrayIterator operator-(difference_type n) const {
        return ArrayIterator(ptr_ - n);
    }
    
    difference_type operator-(const ArrayIterator& other) const {
        return ptr_ - other.ptr_;
    }
    
    reference operator[](difference_type n) const {
        return ptr_[n];
    }
    
    // 比较操作
    bool operator==(const ArrayIterator& other) const {
        return ptr_ == other.ptr_;
    }
    
    bool operator!=(const ArrayIterator& other) const {
        return ptr_ != other.ptr_;
    }
    
    bool operator<(const ArrayIterator& other) const {
        return ptr_ < other.ptr_;
    }
    
    bool operator>(const ArrayIterator& other) const {
        return ptr_ > other.ptr_;
    }
    
private:
    T* ptr_;
};

使用自定义迭代器

#include <algorithm>
#include <iostream>

void demo_custom_iterator() {
    int arr[] = {5, 2, 8, 1, 9};
    const int size = sizeof(arr) / sizeof(arr[0]);
    
    ArrayIterator<int> begin(arr);
    ArrayIterator<int> end(arr + size);
    
    // 使用STL算法
    std::sort(begin, end);
    
    // 使用范围for循环（需要提供begin/end函数）
    for (auto it = begin; it != end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

为自定义容器实现迭代器

template<typename T>
class SimpleVector {
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&;
        
        explicit Iterator(T* ptr = nullptr) : ptr_(ptr) {}
        
        // 实现必要的迭代器操作...
        
    private:
        T* ptr_;
    };
    
    // 容器接口
    Iterator begin() { return Iterator(data_); }
    Iterator end() { return Iterator(data_ + size_); }
    
private:
    T* data_;
    size_t size_;
    size_t capacity_;
};

四、迭代器适配器

STL提供了多种迭代器适配器，可以改变迭代器的行为：

1. 反向迭代器(Reverse Iterator)

#include <vector>
#include <iterator>

void demo_reverse_iterator() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";  // 输出: 5 4 3 2 1
    }
}

2. 插入迭代器(Insert Iterator)

#include <vector>
#include <iterator>
#include <algorithm>

void demo_insert_iterator() {
    std::vector<int> source = {1, 2, 3, 4, 5};
    std::vector<int> target;
    
    std::copy(source.begin(), source.end(), 
              std::back_inserter(target));
}

总结

迭代器是STL设计的核心智慧所在，它通过统一的接口抽象了不同容器的访问方式，使得算法和容器能够独立发展。理解迭代器的分类、萃取技术以及实现原理，对于深入掌握STL和编写高效的泛型代码至关重要。

关键要点：

1. 迭代器分为五大类别，每种类别有不同的能力和限制
2. 迭代器萃取技术使得算法能够根据迭代器特性选择最优实现
3. 自定义迭代器需要提供必要的类型定义和操作符重载
4. 迭代器适配器可以改变现有迭代器的行为

思考题

1. 为什么输入迭代器和输出迭代器只能单遍扫描？
2. 迭代器萃取技术如何帮助实现advance函数？
3. 如何为树形结构（如二叉搜索树）实现迭代器？

在下一篇文章中，我们将探讨函数对象与适配器的实现原理，揭开STL中另一种强大的抽象机制。