【CPP】C++ 标准库（STL）系列教程 迭代器

发表于 | 分类于 |

C++ 标准库（STL）系列教程， 迭代器部分。

CPP 迭代器快速入门

引言

在C++标准模板库（STL）中，迭代器是一个不可或缺的概念。它们为我们提供了一种抽象的方式来访问和操作容器中的元素，无论这些容器是数组、向量、列表还是其他更复杂的数据结构。

迭代器不仅是连接算法和容器的桥梁，更是实现泛型编程的关键所在。本文将带您深入探索C++迭代器的原理和使用方法。

迭代器介绍

迭代器，作为一种广义化的指针，为C++程序提供了处理不同数据结构的统一手段。 它不仅是指针的抽象化表示，更是C++指针语义的广泛延伸。

因为对应指针，所以迭代器获取对应值的操作都是解引用 *i （迭代器有效时）。

迭代器种类较多，我们先给出下表，再依次详细解释。 | 迭代器类别 | 写 | 读 | 自增(单轮) | 自增(多轮) | 自减 | 随机访问 | 连续存储 | | :—: | :—: | :—: | :—: | :—: | :—: | :—: | :—: | | 迭代器 | | | 支持 | | | | | | 输出迭代器 | 支持 | | 支持 | | | | | | 输入迭代器 | | 支持 | 支持 | | | | | | 向前迭代器 | | 支持 | 支持 | 支持 | | | | | 双向迭代器 | | 支持 | 支持 | 支持 | 支持 | | | | 随机访问迭代器 | | 支持 | 支持 | 支持 | 支持 | 支持 | | | 连续迭代器 | | 支持 | 支持 | 支持 | 支持 | 支持 | 支持 |

范围

在C++标准库中，大部分操作数据结构的算法模板都采用了范围接口作为参数，这极大地提高了代码的灵活性和通用性。

范围是由一对迭代器定义的，这对迭代器指明了计算的起始和结束位置。

对于任意两个迭代器i和j，如果通过有限次应用++i操作后，能够使i等于j，则称j从i可及。 当j从i可及时，它们指向的是同一序列中的元素，这构成了范围定义的基础。

范围[i, j)表示从迭代器i指向的元素开始，直到（但不包括）迭代器j指向的元素为止的序列。如果j不能从i通过递增操作达到，那么这个范围就是无效的。在C++20之前，范围主要有两种表示方式：

  • 迭代器-哨位范围 : [i, s)，由迭代器 i 和哨位 s 组成，指定了计算的开头和结尾

    由迭代器i和哨位s组成。当i等于s时，这个范围是空的； 否则，它表示从i指向的元素开始，直到（但不包括）第一个等于s的迭代器指向的元素为止的序列。 只有当s可以从i通过递增操作达到时，这个迭代器-哨位范围才是有效的。

  • 计数范围 : i + [​0​, n)，由迭代器 i 和计数 n 组成，指定了计算要应用的开头和元素数量

    由迭代器i和计数n组成。当n等于0时，这个范围是空的； 否则，它表示从i指向的元素开始，连续包括n个元素的序列。 计数范围在n为0或满足以下条件时有效：n是正数，i可以被解引用，且++i + [0, –n)也是一个有效的范围。

通过这两种范围表示方式，C++标准库能够灵活地处理各种数据结构，实现各种复杂的算法操作，提高了代码的可重用性和可维护性。

迭代器分类

基础迭代器

迭代器 要求描述可以用来标识和遍历容器中的元素的类型，是所有迭代器的基础。

回想我们之前提到的指针，我们对于一个数组，只要自增指针即可完成遍历。 因此，最基础的迭代器只需要支持自增。

输出迭代器

输出迭代器主要用于向目标写入数据。 这种迭代器只能自增，并将数据写入到指定的位置，如文件或输出流中。 尝试从输出迭代器中读取数据将导致未定义的行为。

设想一个键盘输入字符串的场景，每次我们输入一个字符，记录到迭代器对应的空间。 输入一个后要继续输入下一个，因此输出迭代器需要支持自增； 当前迭代器中还没有写入，因此内部可能是空或者是其他字符，因此读取是未定义行为。

输入迭代器

输入迭代器主要用于读取所指向的值。 每当迭代器自增后，之前所指向的值就变得不可访问。这种迭代器不支持在相同范围内进行多次遍历。 例如，std::istream_iterator就是一个典型的输入迭代器，它用于从输入流中读取数据。

设想一个轮询空间并显示的场景，每次我们读取迭代器的值显示在屏幕上。 显示一个后要继续显示下一个，因此输入迭代器需要支持自增； 当前迭代器中输入后，内存空间中的值就可能改变了，因此不支持多轮访问。

前向迭代器

前向迭代器类似于输入迭代器，但可以在同一范围内进行多次迭代。 这种迭代器类似于单向链表，只能向前遍历，但可以重复访问同一范围内的元素。 std::forward_list的迭代器就是前向迭代器的代表。

设想一个单链表，每个元素指向下一个元素，但没有存储反过来的指针。 前向迭代器就像这个链表存储的指针，它允许(多次)单向遍历，因此支持(单/多轮)自增； 由于没有存储反向的指针，因此不支持自减。

1
2
3
4
5
6
    // 示例
    std::list<int> lst = {1, 2, 3, 4, 5};  
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {  
        std::cout << *it << ' '; // 前向迭代器，只能自增，用于遍历列表  
    }  
    std::cout << std::endl;

双向迭代器

双向迭代器不仅可以自增，还可以自减，因此可以在序列中向前或向后迭代。 这种迭代器提供了更多的灵活性，使得我们可以方便地访问序列中的任意元素。 std::list、std::set和std::map等容器都支持双向迭代器。

设想一个双向链表，每个表项都存储指向相邻元素的指针。 双向迭代器就像这个链表存储的指针，它既可以访问上一个元素，又可以访问下一个元素，因此支持(单/多轮)自增自减。

1
2
3
4
5
6
7
8
9
10
11
12
    // 示例
    std::set<int> s = {5, 3, 1, 4, 2};  
    for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {  
        std::cout << *it << ' '; // 双向迭代器，可以自增和自减，用于遍历集合  
    }  
    std::cout << std::endl;  
  
    // 反向遍历集合  
    for (std::set<int>::reverse_iterator rit = s.rbegin(); rit != s.rend(); ++rit) {  
        std::cout << *rit << ' ';  
    }  
    std::cout << std::endl;

随机访问迭代器

随机访问迭代器与其他迭代器不同，它可以在一次操作中直接跳转到容器中的任意元素，而无需逐个遍历。 这种迭代器提供了最高的灵活性，使得我们可以进行复杂的元素访问和算法操作。 std::vector和std::deque的迭代器就是随机访问迭代器的典型代表。

设想一个数组，每个元素都有自己对应的序。 随机访问迭代器就像这个数组的索引，它可以根据索引访问任意一个元素，因此支持随机访问； 既然可以随机访问，那么自然可以访问前后元素，因此支持(单/多轮)自增自减。 假如我们把数组拆成多个数组，我们依然可以用索引访问对应元素，( index / len(arr) 获取对应数组， index % len(arr) 获取子数组的序)，因此不需要支持连续存储。

1
2
3
4
5
6
    // 示例
    std::vector<int> vec = {10, 20, 30, 40, 50};  
  
    // 随机访问迭代器，支持快速访问任意元素  
    std::cout << "Third element: " << vec[2] << std::endl; // 使用下标运算符  
    std::cout << "Second element: " << *(vec.begin() + 1) << std::endl; // 使用指针算术

连续迭代器

连续迭代器不仅具有前述几种迭代器的所有特性，而且要求容器内容在内存上是连续的，类似于数组std::array或std::vector。 这种迭代器在访问元素时具有更高的效率，因为可以通过简单的指针运算来定位元素。

显然，连续迭代器就是随机访问迭代器的连续存储的特化。

可变迭代器

可变迭代器结合了输出迭代器的特性以及其他迭代器的功能，它既可以读取也可以写入数据。 当我们从一个非常量容器的实例中获取迭代器时，这个迭代器通常就是可变迭代器。 可变迭代器提供了对容器内容的完整访问权限，使得我们可以进行各种读写操作。

迭代器总结

从以上介绍不难发现，迭代器之间的深化是继承关系，更强的迭代器自然会满足比他弱的迭代器的需求。

  • 迭代器支持的越全面，对容器的要求就越高；
  • 迭代器支持的越基础，适用容器的泛用性就越广。

实际开发中主要从完成需求(算法)的角度选择容器和对应迭代器。

迭代器操作

  • advance : 令迭代器前进给定的距离

    增加给定的迭代器 it 向前 n 个元素。 如果 n 为负，那么迭代器会自减。

  • distance : 返回两个迭代器间的距离

    从 first 走到 last 所需的自增数。 在使用随机访问迭代器且 first 从 last 可及的情况下值可能为负。

  • next : 令迭代器自增

    返回迭代器 it 的第 n 个后继（或当 n 是负数时为其第 n 个前驱）。

  • prev : 令迭代器自减

    返回迭代器 it 的第 n 个前驱（或当 n 是负数时为其第 n 个后继）。

容器获取迭代器

  • begin cbegin: 返回指向起始的迭代器，c 前缀代表 const 不可修改(下同)

    返回指向 容器 首元素的迭代器。 如果 容器 为空，那么返回的迭代器等于 end()。

  • end cend: 返回指向末尾的迭代器

    返回指向 容器 末元素后一元素的迭代器。 此元素表现为占位符；试图访问它导致未定义行为。

  • rbegin crbegin: 返回指向起始的逆向迭代器

    返回指向逆向的 容器 的首元素的逆向迭代器。它对应非逆向 容器 的末元素。 如果 容器 为空，那么返回的迭代器等于 rend()。

  • rend crend: 返回指向末尾的逆向迭代器

    返回指向逆向的 容器 末元素后一元素的逆向迭代器。它对应非逆向 容器 首元素的前一元素。此元素表现为占位符，试图访问它导致未定义行为。

至此常见的迭代器相关用法已经介绍完毕了，接下来会讲一些迭代器内部的知识。