C++ STL（1）迭代器

前言：

在C++标准模板库（STL）中，迭代器是一个核心概念，它提供了一种统一的方法来访问和遍历容器中的元素，而无需关心容器的具体类型。迭代器就像是一个智能指针，封装了对容器内部元素的访问方式，使得算法能够以一致的方式操作不同的容器。

一、迭代器详解

1、迭代器的定义与功能

迭代器本质上是一个对象，它支持指针的某些操作，如访问、解引用、递增和递减等。通过迭代器，可以遍历容器中的所有元素，读取或修改它们的值，甚至可以在某些情况下连接算法与容器，实现复杂的操作。

迭代器的主要功能包括：

• 遍历容器：通过迭代器可以遍历容器中的所有元素。例如，使用begin()和end()方法获取容器的起始和结束迭代器，然后通过循环来访问每个元素。
• 访问元素：可以通过迭代器读取或修改容器中的元素。这通常是通过解引用迭代器（使用*操作符）来实现的。
• 连接算法与容器：STL中的很多算法（如排序、查找等）都是通过迭代器来操作容器的。迭代器为算法提供了一个统一的接口，使得算法可以独立于容器的具体实现。

2、迭代器类型

STL中定义了五种主要的迭代器类型，它们提供了不同级别的功能和灵活性：

• 输入迭代器（Input Iterators）：这种迭代器用于从容器中读取数据。它只支持单向遍历，即只能向前移动（通过++操作符）。输入迭代器只能进行一次读取，读取后迭代器就会前进到下一个元素。
• 输出迭代器（Output Iterators）：与输入迭代器相反，输出迭代器用于向容器中写入数据。它同样只支持单向遍历，且只能进行一次写入操作，写入后迭代器会自动前进到下一个位置。
• 前向迭代器（Forward Iterators）：前向迭代器类似于输入和输出迭代器，但它支持多次读写操作。它也只能单向遍历，但可以对同一个元素进行多次访问。
• 双向迭代器（Bidirectional Iterators）：双向迭代器可以在容器中向前和向后移动。它扩展了前向迭代器的功能，使得迭代器可以使用--、++操作符向前后移动。双向迭代器在像list、set和map这样的容器中非常有用。不能使用类似it + n的表达式来直接跳转到容器中的第n个元素。
• 随机访问迭代器（Random Access Iterators）：这是最强大的迭代器类型，它支持所有前面提到的迭代器的功能，并且能够进行随机访问。这意味着除了能够向前和向后移动，随机访问迭代器还能够直接跳跃到任意位置（如通过+或-操作符）。vector和deque容器提供了随机访问迭代器。

3、示例

使用迭代器遍历并修改std::vector中元素，示例：

#include <iostream>
#include <vector>int main() {std::vector<int> v = {1, 2, 3, 4, 5};// 使用迭代器遍历并修改 vector 中的元素for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it) {*it *= 2; // 将每个元素的值乘以 2}// 打印修改后的 vectorfor (int val : v) {std::cout << val << " ";}std::cout << std::endl;return 0;
}

在这个例子中，我们创建了一个std::vector<int>并初始化了它。然后，我们使用迭代器遍历了这个vector，并通过解引用迭代器来修改每个元素的值。最后，我们打印了修改后的vector。

4、迭代器失效

迭代器失效是STL编程中常见的问题。当容器发生变化时（如元素被删除、容器被重新分配或插入新元素等），之前获取的迭代器可能会失效，即不再指向有效的元素或不再有意义。为了避免迭代器失效导致的未定义行为，应该谨慎操作容器，并在必要时更新迭代器。

4.1、vector 迭代器失效分析

std::vector是C++标准库中的一个序列容器，它提供了动态数组的功能。然而，在使用std::vector的迭代器时，需要注意迭代器失效的问题。迭代器失效通常发生在容器的底层存储结构发生改变时，如扩容、插入或删除元素等。

迭代器失效的原因:

• 扩容操作： 当std::vector需要增加其容量以容纳更多元素时，它可能会分配一个新的更大的内存块，并将现有元素复制到新的内存块中。这个过程中，原有的内存块会被释放，因此指向原有内存块的迭代器将失效。引起扩容的操作包括：resize()、insert()、push_back()等。
• 插入操作： 在std::vector中插入元素时，如果插入点之后的元素需要移动位置以腾出空间给新元素，那么插入点之后的迭代器将失效。这是因为这些迭代器现在指向的是已经被移动的元素的新位置，而不再是它们原来的位置。
• 删除操作： 使用erase()删除std::vector中的元素时，删除点之后的元素会向前移动以填补被删除元素留下的空隙。虽然这不会改变底层存储结构（即不会重新分配内存），但删除点之后的迭代器仍然会失效，因为它们现在指向的是已经被移动的元素的新位置。

如何避免迭代器失效：

在进行插入、删除或扩容操作后，如果需要继续使用迭代器，应该重新获取迭代器。例如，在使用insert()或erase()后，可以使用它们返回的迭代器（如果适用）或重新从容器的begin()或end()开始遍历。

示例：

#include <iostream>  
#include <vector>  int main() {  std::vector<int> vec = {1, 2, 3, 4, 5};  // 使用迭代器遍历vector并删除元素  for (auto it = vec.begin(); it != vec.end(); /* 注意这里没有递增迭代器的操作 */) {  if (*it % 2 == 0) { // 假设我们要删除所有偶数元素  // 使用erase删除当前元素，并获取新的迭代器  it = vec.erase(it); // erase返回删除点之后的迭代器  // 注意：此时it已经更新为指向下一个元素的迭代器，因此不需要再递增  } else {  // 如果当前元素不是偶数，则递增迭代器以继续遍历  ++it;  }  }  // 输出剩余的元素  for (int num : vec) {  std::cout << num << " ";  }  std::cout << std::endl;  return 0;  
}

4.2、list 迭代器失效分析

std::list 的迭代器在大多数情况下不会因为容器的扩容或元素移动而失效。然而，std::list 的迭代器在某些操作下仍然可能失效。

迭代器失效的原因:

• 元素删除： 当使用 erase() 删除 std::list 中的元素时，指向被删除元素的迭代器会失效。这是因为 erase() 操作会移除链表中的节点，而迭代器实际上是指向这些节点的指针或引用。
• 迭代器自身失效： 如果迭代器被显式地销毁或赋值为其他迭代器的值（特别是如果赋值操作导致了迭代器的复制或移动，并且原始迭代器被销毁），那么该迭代器将失效。

如何避免迭代器失效：

当使用 erase() 删除元素时，应该立即使用 erase() 返回的迭代器（它指向被删除元素之后的第一个元素）来更新你的迭代器。

示例：

#include <iostream>  
#include <list>  int main() {  std::list<int> lst = {1, 2, 3, 4, 5};  // 使用迭代器遍历list并删除元素  for (auto it = lst.begin(); it != lst.end(); /* 注意这里没有固定的递增操作位置 */) {  if (*it % 2 == 0) { // 假设我们要删除所有偶数元素  it = lst.erase(it); // 使用erase删除当前元素，并更新迭代器  // 注意：此时it已经更新为指向下一个元素的迭代器（如果存在）  } else {  // 如果当前元素不是偶数，则递增迭代器以继续遍历  ++it;  }  }  // 输出剩余的元素  for (int num : lst) {  std::cout << num << " ";  }  std::cout << std::endl;  return 0;  
}

4.3、set 与 map 迭代器失效分析

std::map 和 std::set 是两种常见的关联容器。它们基于平衡二叉树（通常是红黑树）实现，提供了高效的查找、插入和删除操作。插入新元素时不会导致已有的迭代器失效，删除元素时，只会让当前的迭代器失效，别的迭代器不受影响。但是，在遍历容器的过程如果调用erase()函数删除元素，需要更新迭代器。当删除元素时，下面两种方法都可有效避免迭代器失效：

方法一：使用erase()返回值更新迭代器

set<int> valset = { 1,2,3,4,5,6 };
set<int>::iterator iter;
for (iter = valset.begin(); iter != valset.end(); ){if (3 == *iter){iter = valset.erase(iter);} else {++iter;}
}

方法二：使用it ++

set<int> valset = { 1,2,3,4,5,6 };
set<int>::iterator iter;
for (iter = valset.begin(); iter != valset.end(); ){if (3 == *iter){valset.erase(iter++);} else {++iter;}
}

传给erase()的是iter的一个副本，iter++是下一个有效的迭代器。

5、总结

STL迭代器是C++标准模板库中的一个重要概念，它提供了一种统一的方法来访问和遍历容器中的元素。通过迭代器可以实现复杂的算法和容器操作，而无需关心容器的具体类型。了解迭代器的类型和使用方法对于编写高效、可维护的C++代码至关重要。