C++ 迭代器

C++ 迭代器

迭代器用于通过"指向"元素来访问和遍历数据结构（向量、集合等）中的元素。

之所以称为"迭代器"，是因为"迭代"是循环的技术术语。

以下是通过迭代器遍历向量的示例：

实例

// 创建存储字符串的向量 cars
vector<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 创建向量迭代器 it
vector<string>::iterator it;

// 使用迭代器遍历向量
for (it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

亲自试一试

例子解释：

  1. 首先创建存储汽车品牌名称的字符串向量
  2. 然后创建名为 "it" 的向量迭代器用于遍历
  3. 使用 for 循环配合迭代器遍历向量。迭代器 (it) 指向向量第一个元素 (cars.begin())，循环持续直到迭代器不等于 cars.end()
  4. 递增运算符 (++it) 将迭代器移动到向量中的下一个元素
  5. 解引用运算符 (*it) 访问迭代器指向的元素

注意：迭代器的类型必须与其遍历的数据结构类型匹配（本例中为 string）

begin() 和 end() 函数

begin() 和 end() 是属于数据结构（如向量和列表）的成员函数，它们不属于迭代器本身，而是与迭代器配合使用来访问和遍历数据结构元素。

  • begin() 返回指向数据结构第一个元素的迭代器
  • end() 返回指向最后一个元素之后位置的迭代器

继续以向量为例说明它们的工作原理：

vector<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};
vector<string>::iterator it;

begin() 实例

begin() 指向向量中的第一个元素（索引 0，即 "Volvo"）：

实例

// 指向向量第一个元素
it = cars.begin();

亲自试一试

要指向第二个元素 (BMW)，可以使用 cars.begin() + 1：

实例

// 指向第二个元素
it = cars.begin() + 1;

亲自试一试

同理，cars.begin() + 2 指向第三个元素：

实例

// 指向第三个元素
it = cars.begin() + 2;

亲自试一试

end() 实例

end() 指向向量中最后一个元素之后的位置（不指向实际元素，仅表示向量结束）。

因此，要指向 cars 向量的最后一个元素 (Tesla)，可以使用 cars.end() - 1：

实例

// 指向最后一个元素
it = cars.end() - 1;

亲自试一试

为什么说"指向"？

迭代器类似于"指针"，它们"指向"数据结构中的元素而不是返回元素值。它们引用特定位置，提供访问和修改值的方式，而无需复制值。例如：

实例

// 指向向量第一个元素
it = cars.begin();

// 修改第一个元素的值
*it = "Audi";

// Volvo 现在变为 Audi

亲自试一试

auto 关键字

在 C++11 及更高版本中，可以使用 auto 关键字代替显式声明和指定迭代器类型。

auto 关键字让编译器自动确定正确的数据类型，简化代码并提高可读性：

替代这种写法：

vector<string>::iterator it = cars.begin();

可以简写为：

auto it = cars.begin();

亲自试一试

在上面的例子中，编译器根据 cars.begin() 的返回类型（即 vector<string>::iterator）自动推导出 it 的类型。

在 for 循环中也可以使用 auto 关键字：

for (auto it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

亲自试一试

for-each 循环 vs 迭代器

可以使用 for-each 循环遍历数据结构元素：

实例

// 创建存储字符串的向量 cars
vector<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 打印向量元素
for (string car : cars) {
  cout << car << "\n";
}

亲自试一试

但当需要在迭代过程中添加/删除元素、反向迭代或跳过元素时，应该使用迭代器：

实例

// 创建存储字符串的向量 cars
vector<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 遍历向量元素
for (auto it = cars.begin(); it != cars.end(); ) {
  if (*it == "BMW") {
    it = cars.erase(it); // 移除 BMW 元素
  } else {
    ++it;
  }
}

// 打印向量元素
for (const string& car : cars) {
  cout << car << "\n";
}

亲自试一试

反向迭代

要反向迭代，可以使用 rbegin() 和 rend() 代替 begin() 和 end()：

实例

// 反向迭代
for (auto it = cars.rbegin(); it != cars.rend(); ++it) {
  cout << *it << "\n";
}

亲自试一试

遍历其他数据结构

迭代器具有很好的代码复用性，可以使用相同语法遍历向量、列表、双端队列、集合和映射：

列表实例

// 创建一个名为 cars 的链表 (list)，用于存储字符串
list<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 使用迭代器遍历链表
for (auto it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

亲自试一试

双端队列实例

// 创建一个名为 cars 的双端队列 (deque)，用于存储字符串
deque<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 使用迭代器遍历双端队列
for (auto it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

亲自试一试

集合实例

// 创建一个名为 cars 的集合 (set)，用于存储字符串
set<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

// 使用迭代器遍历集合
for (auto it = cars.begin(); it != cars.end(); ++it) {
  cout << *it << "\n";
}

亲自试一试

映射实例

// 创建一个映射 (map)，用于存储字符串到整数的键值对
map<string, int> people = { {"Bill", 19}, {"Steve", 32}, {"Elon", 26} };

// 使用迭代器遍历映射
for (auto it = people.begin(); it != people.end(); ++it) {
  cout << it->first << " is: " << it->second << "\n";
}

亲自试一试

迭代器支持

上面的例子展示了如何遍历支持迭代器的不同数据结构（向量、列表、双端队列、映射和集合支持迭代器，而栈和队列不支持）。

算法函数

迭代器的另一个重要特性是可以与各种算法函数（如 sort() 和 find()，位于 <algorithm> 库中）配合使用，对数据结构中的元素进行排序和搜索。

例如，sort() 函数接受迭代器（通常由 begin() 和 end() 返回）作为参数，对数据结构中的元素从头到尾进行排序。

下例按字母顺序排序字符串元素：

实例

#include <iostream>
#include <vector>
#include <algorithm>  // 包含算法库
using namespace std;

int main() {
  // 创建一个存储字符串的 vector 容器，名为 cars
  vector<string> cars = {"Volvo", "BMW", "Ford", "Tesla"};

  // 对 cars 中的元素按字母顺序进行排序
  sort(cars.begin(), cars.end());

  // 按字母顺序打印排序后的汽车品牌
  for (string car : cars) {
    cout << car << "\n";
  }

  return 0;
}

亲自试一试

下例对整数元素进行数值排序：

实例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  // 创建一个整型 vector 容器，名为 numbers，并初始化 6 个整数
  vector<int> numbers = {1, 7, 3, 5, 9, 2};

  // 对 numbers 中的元素进行数值排序（默认升序）
  sort(numbers.begin(), numbers.end());

  for (int num : numbers) {
    cout << num << "\n";
  }

  return 0;
}

亲自试一试

要反向排序，只需使用 rbegin() 和 rend() 代替 begin() 和 end()：

实例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  // 创建一个整型 vector 容器 numbers，初始化 6 个整数
  vector<int> numbers = {1, 7, 3, 5, 9, 2};

  // 使用 rbegin() 和 rend() 反向迭代器实现降序排列
  sort(numbers.rbegin(), numbers.rend());

  for (int num : numbers) {
    cout << num << "\n";
  }

  return 0;
}

亲自试一试