38 C++ STL模板库7-迭代器

C++ STL模板库7-迭代器

迭代器是C++中连接容器与算法的通用接口，提供了一种访问容器元素的统一方式，类似于指针但更强大。
使用迭代器需包含 <iterator>

一、迭代器的核心作用

1. 解耦容器与算法

   • 算法（如 std::sort, std::copy）通过迭代器操作容器，无需知道容器具体类型（数组、链表等）。
   • 示例：std::sort(vec.begin(), vec.end()) 可对 vector、deque 等均生效。

2. 统一访问模式

   • 无论容器如何存储数据（连续内存/链表/树），迭代器提供一致的遍历接口（++, *, ->）。

3. 支持范围操作

   • 通过 begin() 和 end() 定义半开区间 [begin, end)，安全遍历且避免越界。

二、迭代器的五大分类与操作

1. 根据功能由弱到强分为：

   分类	支持操作	典型容器
   输入迭代器	只读一次（*it, ++, ==）	istream_iterator
   输出迭代器	只写一次（*it=, ++）	ostream_iterator
   前向迭代器	多次读写（++）	forward_list, 哈希表
   双向迭代器	双向移动（++, --）	list, set, map
   随机访问迭代器	跳跃访问（+n, -n, [], 比较）	vector, deque, 数组

2. 核心声明语法

   容器类型::iterator 变量名;         // 可修改元素的迭代器  
   容器类型::const_iterator 变量名;   // 只读元素的迭代器  
   容器类型::reverse_iterator 变量名; // 反向迭代器  
   

   vector<int>::iterator it = vn.begin ();
   array<int,5>::iterator it = vn.begin ();
   array<string>::iterator it = vn.begin ();
   

   下面的语句令一个整型向量的迭代器指向该向量的第一个元素：
   it = vn.begin ();
   而下面的语句令该迭代器指向向量中最后一个元素的下一个位置：
   it = vn.end ();
   通过begin()和end()构建迭代循环：

   for (vector<int>::iterator it = vn.begin(); it != vn.end (); it++)
       ...
   一般用 auto 类型推导代替 vector<int>::iterator ,来缩短代码和防止出错
   

   遍历容器中元素。
   迭代器的基本操作：*、++/–、+/-/+=/-=整数(部分容器的迭代器)

3. 迭代器工具函数（需包含 <iterator>）

   函数	语法/示例	作用
   std::advance	advance(iter, n)	移动迭代器n步（支持正负方向）
   std::distance	distance(iter1, iter2)	计算两个迭代器之间的元素数量
   std::next/std::prev	next(iter, n=1) 或 prev(iter, n=1)	获取移动后的迭代器副本（不修改原迭代器）

   示例：

   std::deque<int> dq = {10, 20, 30};  
   auto dq_it = dq.begin();  
   std::advance(dq_it, 2);      // 移动到第3个元素（30）  
   auto count = std::distance(dq.begin(), dq.end()); // 计算长度（3）  
   auto next_it = std::next(dq_it, -1); // 获取前一个位置的迭代器（20）  
   

三、关键用法与代码示例

1. 迭代器的原理

迭代器本质是抽象化的指针
迭代器模式的核心价值在于解耦数据结构和算法

int arr[5] = {10, 20, 30, 40, 50};  

// ✅ 指针作为迭代器的用法  
int* begin = arr;      // 首元素迭代器  
int* end = arr + 5;    // 尾后迭代器  
    
// 遍历操作  
for (int* it = begin; it != end; ++it) {  
    std::cout << *it << " ";  // 输出：10 20 30 40 50  
}  
    
// 随机访问  
*(begin + 2) = 99;    // 修改第三个元素 → arr[2]=99  
std::cout << begin[3]; // 输出：40（等价于*(begin+3)）  
    
// 算法应用  
auto min_pos = begin;  
for (int* p = begin + 1; p != end; ++p) {  
    if (*p < *min_pos) min_pos = p;  
}  
std::cout << "最小值：" << *min_pos; // 输出：10    

• 指针迭代的缺点：
  1. 无边界检查：end + 1 会导致未定义行为
  2. 无类型封装：无法区分 int* 是迭代器还是普通指针
  3. 功能缺失：不支持反向迭代器等高级特性

2. 迭代器用法与示例

1. 遍历数组（正/反向）

   #include <iostream>  
   #include <array>  
   
   int main() {  
       std::array<int, 4> arr = {10, 20, 30, 40};  
   
       // 正向迭代器（常量与非常量）  
       for(auto it = arr.begin(); it != arr.end(); ++it) {  
           *it += 1;  // 修改元素值  
           std::cout << *it << " ";  // 输出：11 21 31 41  
       }  
   
       // 反向迭代器（C++11）  
       for(auto rit = arr.rbegin(); rit != arr.rend(); ++rit) {  
           std::cout << *rit << " ";  // 输出：41 31 21 11  
       }  
   }  
   

2. 遍历容器

   std::array<int, 3> arr = {10, 20, 30};  
   
   for (std::array<int, 3>::iterator it = arr.begin();  it != arr.end();  ++it) {  
       std::cout << *it << " "; // 输出：10 20 30  
   }  
   
   auto it = arr.begin() + 2;  
   *it = 99;                //  
       
   // C++11范围for（底层使用迭代器）  
   for (int val : arr) {  
       std::cout << val << " ";  //输出：10 20 99  
   }   
   

3. 与标准算法结合

   #include <iostream>  
   #include <array>  
   #include <algorithm>  
   #include <numeric>  //  accumulate✅ 必须包含此头文件  
   
   int main() {  
       std::array<int, 4> arr = {10, 20, 30, 40};  
   
       // 正向迭代器（常量与非常量）
       //std::array<int, 4>::iterator it 
       for(auto it = arr.begin();  it != arr.end();  ++it) {  
           *it += 1;  // 修改元素值  
           std::cout << *it << " ";  // 输出：11 21 31 41  
       }  
   
       // 反向迭代器（C++11）  
       for(auto rit = arr.rbegin();  rit != arr.rend();  ++rit) {  
           std::cout << *rit << " ";  // 输出：41 31 21 11  
       }  
       
       std::sort(arr.begin(), arr.end());  
   
       // 查找元素  
       auto pos = std::find(arr.cbegin(), arr.cend(), 21);  
       if(pos != arr.end()) {  
           std::cout << "位置索引：" << pos - arr.begin()<<std::endl;  // 输出：1  
       }  
       
       // 累加计算（C++17）  
       int sum = std::accumulate(arr.cbegin(),  arr.cend(), 0);
       std::cout << "总和：" << sum<<std::endl;  // 输出：104 
   }
   

4. 随机访问操作

   auto first = arr.begin();  
   auto third = first + 2;  // 直接跳转到索引2  
       
   std::cout << *(first + 1) <<std::endl;    // 输出：21（等价于arr[1]）  
   std::cout << (third > first) <<std::endl; // 输出：1（支持比较）  
   std::cout << third[1] <<std::endl;        // 输出：41（索引相对访问）  
   

5. 安全访问：常量迭代器

   void printArray(const std::array<int, 4>& arr) 
   {  
       // 使用cbegin/cend防止意外修改  
       for(auto it = arr.cbegin(); it != arr.cend(); ++it) {  
           std::cout << *it << " ";  
           // *it = 0;  // 错误！常量迭代器禁止修改  
       }  
   }
   

3. 迭代工具用法示例

1. 基础迭代器操作工具

   1. std::next / std::prev（安全位移）

      #include <iterator>
      std::vector<int> vec{10, 20, 30, 40};
      
      // 向前移动2步（支持所有迭代器类型）
      auto it_next = std::next(vec.begin(), 2); // 指向30 
      
      // 向后移动1步（仅双向迭代器可用）
      auto it_prev = std::prev(vec.end(), 1);   // 指向40 
      

   2. std::advance（原位修改迭代器）

      auto it = vec.begin();
      std::advance(it, 3);  // it直接指向40（无返回值，修改原迭代器）
      

      特性对比：

      • 与std::next的区别：直接修改迭代器，适用于循环中逐步推进。

   3. std::distance（计算距离）

      int len = std::distance(vec.begin(), vec.end()); // 输出4（元素总数）
      

      兼容性：

      • 随机访问迭代器：O(1) 时间复杂度
      • 其他迭代器：O(n) 时间复杂度（需遍历）

4. 使用技巧

• 迭代器的显式声明和类型推导

  • 显式声明
    std::array<int, 4>::iterator it;
  • 类型推导
    auto it;

• 获取首尾元素的迭代器

  auto front_it = arr.begin();      // 首元素迭代器  
  auto back_it  = arr.end() - 1;     // 尾元素迭代器（因end()指向末尾后一位）  
  

• 数组与指针互操作

  int* ptr = arr.data();           // 获取原生指针  
  auto it_from_ptr = arr.begin() + (ptr - arr.data()); // 指针转迭代器  
  

• 优先使用范围for循环

  for (int val : arr) { ... }  // 简洁安全  
  

• 只读访问用cbegin/cend

  auto it = arr.cbegin();  // 明确表达只读意图  
  

• 随机访问时检查边界

  if(index < arr.size()) {  
      auto it = arr.begin() + index;  
  }