iterator — 迭代器

迭代器是 STL 的粘合剂，连接容器与算法。理解迭代器类别和自定义迭代器，是深度使用 STL 的关键。

迭代器类别

#include <iterator>

// 迭代器层次（能力从弱到强）
// InputIterator      — 单次遍历，只读（istream_iterator）
// OutputIterator     — 单次遍历，只写（ostream_iterator）
// ForwardIterator    — 多次遍历，读写（forward_list）
// BidirectionalIterator — 双向（list, map, set）
// RandomAccessIterator  — 随机访问（vector, deque, array）
// ContiguousIterator    — 连续内存（C++20，vector, array, string）

// 检查迭代器类别
static_assert(std::random_access_iterator<std::vector<int>::iterator>);
static_assert(std::bidirectional_iterator<std::list<int>::iterator>);
static_assert(std::forward_iterator<std::forward_list<int>::iterator>);

迭代器操作

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin();

// 所有迭代器
++it;           // 前进一步
*it;            // 解引用

// 双向迭代器
--it;           // 后退一步

// 随机访问迭代器
it += 2;        // 前进多步
it -= 1;        // 后退多步
it[2];          // 下标访问
it2 - it;       // 距离
it < it2;       // 比较

// 通用操作（适用于所有迭代器）
std::advance(it, 3);                    // 前进 n 步（双向可负数）
auto dist = std::distance(v.begin(), v.end());  // 计算距离
auto next_it = std::next(it, 2);        // 返回前进 n 步的迭代器
auto prev_it = std::prev(it, 1);        // 返回后退 n 步的迭代器

特殊迭代器

#include <iterator>

// 插入迭代器
std::vector<int> src = {1, 2, 3};
std::vector<int> dst;

std::copy(src.begin(), src.end(), std::back_inserter(dst));   // 尾部插入
std::copy(src.begin(), src.end(), std::front_inserter(dst));  // 头部插入（list）
std::copy(src.begin(), src.end(), std::inserter(dst, dst.begin() + 1));  // 指定位置

// 流迭代器
#include <sstream>
std::istringstream iss("1 2 3 4 5");
std::vector<int> nums(std::istream_iterator<int>(iss), {});

std::copy(nums.begin(), nums.end(),
          std::ostream_iterator<int>(std::cout, " "));  // 输出到流

// 反向迭代器
for (auto it = v.rbegin(); it != v.rend(); ++it) {
    std::cout << *it << " ";  // 5 4 3 2 1
}

// move 迭代器（移动而非拷贝）
std::vector<std::string> src_str = {"hello", "world"};
std::vector<std::string> dst_str;
std::copy(std::make_move_iterator(src_str.begin()),
          std::make_move_iterator(src_str.end()),
          std::back_inserter(dst_str));

自定义迭代器

// 实现一个范围迭代器
class Range {
    int start_, end_, step_;

public:
    Range(int start, int end, int step = 1)
        : start_(start), end_(end), step_(step) {}

    struct Iterator {
        int current, step;
        using iterator_category = std::forward_iterator_tag;
        using value_type = int;
        using difference_type = std::ptrdiff_t;
        using pointer = const int*;
        using reference = int;

        Iterator(int c, int s) : current(c), step(s) {}
        int operator*() const { return current; }
        Iterator& operator++() { current += step; return *this; }
        Iterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
        bool operator==(const Iterator& o) const { return current >= o.current; }
        bool operator!=(const Iterator& o) const { return !(*this == o); }
    };

    Iterator begin() const { return {start_, step_}; }
    Iterator end()   const { return {end_, step_}; }
};

// 使用
for (int i : Range(0, 10, 2)) {
    std::cout << i << " ";  // 0 2 4 6 8
}

// 与 STL 算法配合
Range r(1, 100);
int sum = std::accumulate(r.begin(), r.end(), 0);

关键认知

迭代器类别决定了哪些算法可以使用。std::advance/std::distance/std::next/std::prev 是通用迭代器操作，比直接 += 更安全（适用于所有迭代器类别）。自定义迭代器需要定义五个类型别名（iterator_category 等）才能与 STL 算法配合。