迭代器体系全解

定义与作用

迭代器是 STL 的粘合剂——连接容器与算法。它将容器的内部表示抽象为统一的遍历接口，使算法可以独立于具体容器类型工作。

std::vector<int> v{1, 2, 3};
auto it = v.begin();        // 随机访问迭代器
*it = 10;                   // 解引用
std::advance(it, 2);        // 前进 2 步

核心原理

五类迭代器层次

iterator_traits 机制

完整示例

示例一：通用打印函数——迭代器层次实战

场景说明：白歌为飞翔科技编写一个通用日志打印函数，根据迭代器类型选择最优策略。

#include <iostream>
#include <vector>
#include <list>
#include <iterator>
#include <string>

// 随机访问迭代器：可以用 size 预取
template<typename It>
void printRange(It first, It last, std::random_access_iterator_tag) {
    auto size = std::distance(first, last);
    std::cout << "[随机访问] 共 " << size << " 个元素: ";
    for (; first != last; ++first)
        std::cout << *first << " ";
    std::cout << "\n";
}

// 双向迭代器：只能逐个遍历
template<typename It>
void printRange(It first, It last, std::bidirectional_iterator_tag) {
    std::cout << "[双向] 顺序遍历: ";
    for (; first != last; ++first)
        std::cout << *first << " ";
    std::cout << "\n";

    // 反向打印
    std::cout << "[双向] 逆序遍历: ";
    --last;
    for (; ; --last) {
        std::cout << *last << " ";
        if (last == first) break;
    }
    std::cout << "\n";
}

// 通用分发入口
template<typename It>
void printRange(It first, It last) {
    using category = typename std::iterator_traits<It>::iterator_category;
    printRange(first, last, category{});
}

int main() {
    std::cout << "=== 飞翔科技迭代器示例 ===\n\n";

    // vector → 随机访问迭代器
    std::vector<std::string> team{"大翔", "白歌", "小崔", "黄俪", "李眉"};
    std::cout << "技术团队 (vector):\n";
    printRange(team.begin(), team.end());

    // list → 双向迭代器
    std::list<int> scores{98, 95, 92, 88, 85};
    std::cout << "\n绩效分数 (list):\n";
    printRange(scores.begin(), scores.end());

    // 原生数组 → 指针也是随机访问迭代器
    double revenue[] = {188888.88, 232000.00, 166666.66};
    std::cout << "\n营收数据 (原生数组):\n";
    printRange(std::begin(revenue), std::end(revenue));
}

预期输出：

=== 飞翔科技迭代器示例 ===

技术团队 (vector):
[随机访问] 共 5 个元素: 大翔 白歌 小崔 黄俪 李眉 

绩效分数 (list):
[双向] 顺序遍历: 98 95 92 88 85 
[双向] 逆序遍历: 85 88 92 95 98 

营收数据 (原生数组):
[随机访问] 共 3 个元素: 188889 232000 166667

逐段分析：

  • Tag Dispatch 模式：通过 iterator_category 标签选择合适的重载
  • std::iterator_traits<T*> 对指针有偏特化，原生数组的指针也能获得完整的 traits
  • std::begin() / std::end() 是 C++11 引入的自由函数，统一获取容器和原生数组的迭代器

示例二：迭代器辅助工具函数

场景说明：小崔利用 advance、distance、next、prev 实现高效的元素跳跃访问。

#include <iostream>
#include <list>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
    // advance：通用前进（O(1) 随机访问，O(n) 非随机）
    std::list<int> lst{10, 20, 30, 40, 50, 60, 70};
    auto it = lst.begin();
    std::advance(it, 3);  // 对 list 是 O(n)（实际走了 3 步）
    std::cout << "advance 3: " << *it << "\n";  // 40

    // distance：计算两个迭代器间距离
    auto dist = std::distance(lst.begin(), lst.end());
    std::cout << "distance: " << dist << " 个元素\n";  // 7

    // next：返回前进 n 步后的迭代器（不修改原迭代器）
    auto it2 = lst.begin();
    auto it3 = std::next(it2, 4);
    std::cout << "next(begin, 4): " << *it3 << "\n";  // 50

    // prev：返回后退 n 步后的迭代器
    auto it4 = lst.end();
    auto it5 = std::prev(it4, 2);
    std::cout << "prev(end, 2): " << *it5 << "\n";    // 60

    // vector 的随机访问优势
    std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    auto vit = vec.begin();
    std::advance(vit, 8);   // 对 vector 是 O(1)！
    std::cout << "vector advance 8: " << *vit << "\n";
}

预期输出：

advance 3: 40
distance: 7 个元素
next(begin, 4): 50
prev(end, 2): 60
vector advance 8: 9

逐段分析：

  • advance 对随机访问迭代器用 +=（O(1)），对非随机用循环 ++（O(n)）
  • distance 类似，随机访问直接相减（O(1)），非随机逐次计数（O(n)）
  • next/prev（C++11）是 advance + 创建副本的便利封装

易错场景与面试考点

易错场景

1. 调用 advance 时忽略复杂度差异

std::list<int> lst(100000, 0);
auto it = lst.begin();
std::advance(it, 50000);  // O(n)，在 list 中开销大
// 如果需要频繁随机访问，应使用 vector

2. 迭代器失效后继续使用

std::vector<int> v{1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 可能触发 realloc，it 失效
// *it;  // 未定义行为

3. 混淆 end() 和最后一个元素

auto last = v.end();  // 指向尾后，不是最后一个元素！
// *last;  // 未定义行为
auto realLast = std::prev(v.end());  // 正确获取最后一个元素

面试考点

考点要点
五类迭代器输入 → 前向 → 双向 → 随机访问 → 连续（C++17）
iterator_traits统一获取 value_type/difference_type/category 等
Tag Dispatch通过 iterator_category 标签选择不同实现
advance/distance对随机访问 O(1)，非随机 O(n)
next/prevC++11 引入，返回新迭代器不修改原迭代器
迭代器失效vector 扩容/删除、deque 中间插入等
iterator vs const_iteratorcbegin/cend 返回 const_iterator