迭代器（Iterator）是C++标准模板库（STL）中的一种工具，用于在不暴露底层数据结构的前提下遍历容器。它类似于指针，可以指向容器中的元素，通过一系列操作访问和修改容器中的数据。

STL中的大部分容器（如vector、list、set等）都提供迭代器，用来遍历其中的元素。每个容器的迭代器类型会有所不同，以满足不同的需求。

迭代器的类型

根据功能的不同，迭代器分为以下几种类型：

  1. 输入迭代器（Input Iterator）：只能单向遍历元素，只能读取不能修改。
  2. 输出迭代器（Output Iterator）：只能单向遍历元素，只能修改不能读取。
  3. 前向迭代器（Forward Iterator）：可以单向遍历，可以读取和修改。
  4. 双向迭代器（Bidirectional Iterator）：可以在容器中双向遍历。
  5. 随机访问迭代器（Random Access Iterator）：可以双向遍历，可以随机访问任意位置元素。vector和deque等连续存储结构支持此类型的迭代器。

常见容器的迭代器类型

  • vector、deque：随机访问迭代器
  • list：双向迭代器
  • set、map：双向迭代器

迭代器的基本操作

下面是一些常用的迭代器操作：

  1. 获取迭代器
    每个容器提供begin()和end()方法，分别返回指向容器起始位置和结束位置的迭代器。

    • begin()：指向第一个元素
    • end()：指向最后一个元素的下一个位置（不包含在容器中）

  2. 迭代器的递增和递减

    • ++it：将迭代器移动到下一个元素。
    • --it：将迭代器移动到前一个元素（仅双向或随机访问迭代器支持）。

  3. 解引用迭代器

    • *it：访问迭代器所指向的元素。
    • it->：访问迭代器指向对象的成员（当元素是类或结构体时）。

  4. 迭代器的比较

    • 可以使用==和!=比较两个迭代器是否相等（是否指向同一位置）。

迭代器的使用示例

以下是几个常见容器的迭代器操作示例：

1. vector 迭代器

vector是动态数组，支持随机访问迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {10, 20, 30, 40, 50};

    // 使用迭代器遍历vector
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用范围for循环和自动类型推导遍历vector
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

2. list 迭代器

list是双向链表，支持双向迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {10, 20, 30, 40, 50};

    // 使用迭代器正向遍历list
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用迭代器反向遍历list
    for (std::list<int>::reverse_iterator rit = lst.rbegin(); rit != lst.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. map 迭代器

map是关联容器，存储键值对，支持双向迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> age;
    age["Alice"] = 25;
    age["Bob"] = 30;
    age["Charlie"] = 35;

    // 使用迭代器遍历map
    for (std::map<std::string, int>::iterator it = age.begin(); it != age.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

在map中，it->first访问键，it->second访问值。

4. set 迭代器

set是集合容器，支持双向迭代器，元素是唯一的且有序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <set>

int main() {
    std::set<int> s = {10, 20, 30, 40, 50};

    // 使用迭代器遍历set
    for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

常见的迭代器操作实例

  1. 插入和删除操作（适用于vector和list等可修改容器）

    • 插入操作：在指定位置插入元素

      1
      2
      3
      4
      std::vector<int> vec = {10, 20, 30};
      auto it = vec.begin();
      vec.insert(it + 1, 15); // 在第二个位置插入15
      // vec: {10, 15, 20, 30}

    • 删除操作：删除指定位置元素

      1
      2
      3
      4
      5
      std::list<int> lst = {10, 20, 30, 40};
      auto it = lst.begin();
      ++it; // 指向20
      lst.erase(it); // 删除20
      // lst: {10, 30, 40}

  2. 查找和修改元素

    • 查找元素的迭代器位置

      1
      2
      3
      4
      5
      std::vector<int> vec = {10, 20, 30, 40};
      auto it = std::find(vec.begin(), vec.end(), 30);
      if (it != vec.end()) {
          std::cout << "Found 30 at position " << std::distance(vec.begin(), it) << std::endl;
      }

    • 修改元素

      1
      2
      3
      4
      std::vector<int> vec = {10, 20, 30, 40};
      for (auto it = vec.begin(); it != vec.end(); ++it) {
          *it *= 2; // 每个元素乘以2
      }

  3. 反向迭代器

    • 对于支持反向迭代的容器，可以使用rbegin()和rend()获得反向迭代器。
    • 示例：
      1
      2
      3
      4
      std::vector<int> vec = {10, 20, 30, 40};
      for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
          std::cout << *it << " "; // 输出：40 30 20 10
      }

总结

  • 迭代器提供了灵活的接口，使得容器可以在不暴露底层实现的前提下进行遍历、插入、删除等操作。
  • 常用迭代器操作包括：begin()、end()、++、--、*解引用等。
  • 通过迭代器，可以更高效、简洁地对容器进行操作，使得代码独立于容器的具体实现。