阿荣的个人网站

探索 C++ 迭代器

迭代器是 C++ 的一个重要组成部分, 它在数据结构和算法之间架起了桥梁. 迭代器作为通用指针, 可以遍历和操作容器中的元素, 同时隐藏底层的复杂性. 让我们一起探索现代 C++ 中迭代器的概念, 类别和使用场景.

什么是迭代器?

迭代器是一种抽象工具, 它允许顺序访问集合中的元素, 而无需暴露集合的底层实现. 迭代器是指针的泛化, 使得可以遍历数组, 向量, 列表等容器.

示例:

std::vector<int> vec{10, 20, 30, 40};
for (auto it = vec.begin(); it != vec.end(); ++it) {
  std::cout << *it << " ";
}
// 输出: 10 20 30 40

相比较而言, 传统的访问方式为:

for (size_t i = 0; i < vec.size(); i++) {
  std::cout << vec[i] << " ";
}
std::cout << std::endl;

auto p = vec.data();
for (size_t i = 0; i < vec.size(); i++) {
  std::cout << p[i] << " ";
}
std::cout << std::endl;

迭代器类别

C++ 定义了多个迭代器类别, 每种类别具备不同的能力.

  1. 随机访问迭代器(Random Access Iterators): 支持完全的随机访问, 比较和算术操作.

    • 容器: std::vector, std::array, 原生数组.
    • 操作: ++, --, +=, -=, *, [], <, <=, >, >=
    #include <iostream>
#include <vector>

int main() {
  std::vector<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8};
  auto it = vec.begin();
  it++;
  it += 3;
  std::cout << *it << std::endl;    // 4
  std::cout << it[0] << std::endl;  // 4

  auto it2 = vec.begin() + 6;
  std::cout << std::boolalpha << (it < it2) << std::endl;  // true
}

  2. 双向迭代器(Bidirectional Iterators): 支持向前和向后遍历.

    • 容器: 链表(std::list), 关联容器如 std::set, std::map.
    • 操作: ++, --, *, ==, !=
    #include <iostream>
#include <list>

int main() {
  std::list<int> vec{0, 1, 2, 3, 4, 5, 6, 7, 8};
  auto it = vec.begin();
  it++;
  std::cout << *it << std::endl;  // 1
  it--;
  std::cout << *it << std::endl;  // 0
}

  3. 前向迭代器(Forward Iterators): 仅支持单向遍历.

    • 容器: std::forward_list, 无序关联容器 std::unordered_map, std::unordered_set
    • 操作: ++, *, ==, !=
    #include <iostream>
#include <unordered_map>

int main() {
  std::unordered_map<int, int> map{{1, 2}, {3, 4}, {5, 6}};
  auto it = map.begin();
  it++;

  //   it--; // Error
  std::cout << it->first << ": " << it->second << std::endl;  // 3: 4
}

  4. 输入迭代器(Input Iterators): 设计用于一次性读取.

    • 示例: std::istream_iterator

  5. 输出迭代器(Output Iterators): 用于一次性写入到范围.

    • 示例: std::ostream_iterator

半开区间和安全性

迭代器遵循半开区间约定, 范围从 begin() 开始, 到 end() 前结束. 这种设计防止了越界访问.

示例:

std::vector<int> nums{1, 2, 3, 4};
for (auto it = nums.begin(); it != nums.end(); ++it) {
    std::cout << *it << " ";
}

STL 算法中的迭代器

标准模板库(STL)的算法利用迭代器实现与容器无关的操作. 例如:

  1. 查找元素:

    auto it = std::find(vec.begin(), vec.end(), value);
if (it != vec.end()) {
    std::cout << "找到: " << *it;
}

  2. 转换元素:

    std::transform(src.begin(), src.end(), dest.begin(), [](int x) { return x * x; });

需要避免的陷阱

未定义行为示例:

  1. 在获取迭代器之后修改容器元素.

    std::vector<int> vec{1, 2, 3};
auto it = vec.begin();
vec.push_back(4);
std::cout << *it; // 未定义行为: 迭代器失效

  2. 在遍历容器的时候删除迭代器

    void remove(std::vector<int>& vec, int target) {
  for (auto it = vec.begin(); it != vec.end(); it++) {
    if (*it == target) {
      vec.erase(it);
    }
  }
}

现代增强

  1. 基于范围的循环(C++11), 使用 for 循环简化迭代:

    for (const auto& elem : vec) {
    std::cout << elem << " ";
}

  2. 视图与过滤器(C++20), 引入对范围的惰性评估.

    auto filtered = vec | std::views::filter([](int x) { return x > 10; });
for (int val : filtered) {
    std::cout << val << " ";
}

总结

C++ 迭代器在数据结构和算法之间起着关键作用, 提供了灵活性和强大功能. 理解它们的类别, 正确用法和可能的陷阱, 可以确保高效且无错误的编程. 拥抱现代增强特性, 简化并优化您的代码!

Tags:

Iterator