迭代器有哪几种类型输入输出前向双向随机访问迭代器-C++-PHP中文网

迭代器在c++++中是访问容器元素的抽象指针，分为输入、输出、前向、双向和随机访问五种类型，能力依次递增；输入迭代器支持单向读取，输出迭代器支持单向写入，前向迭代器可多次读写并支持多趟遍历，双向迭代器可在前后方向移动，随机访问迭代器支持指针算术运算和高效随机访问；迭代器类型决定了算法的适用性与性能，如std::sort要求随机访问迭代器，而std::list不满足该条件需使用其成员函数sort()；可通过查阅文档、根据容器底层结构（如连续内存容器支持随机访问，链表结构支持前向或双向）或使用std::iterator_traits进行编译时判断来确定容器的迭代器类型；迭代器失效发生在容器结构改变导致迭代器指向无效位置时，常见于插入删除操作或内存重分配，如std::vector插入可能使所有迭代器失效，std::list删除仅使对应迭代器失效；避免失效的方法包括熟悉容器规则、用erase返回值更新迭代器、使用范围for循环、避免循环中修改容器或选用迭代器稳定的容器，掌握这些原则是编写高效安全c++代码的基础。

迭代器有哪几种类型输入输出前向双向随机访问迭代器

迭代器在C++中，本质上是一种抽象，它提供了一种统一的方式来访问容器中的元素，而无需暴露容器内部的具体结构。它们根据所提供的功能和能力，被划分为五种主要类型：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器。每种类型都像一个能力清单，定义了你能用这个“指针”做什么，以及它能以何种效率完成这些操作。

解决方案

理解这五种迭代器类型，就如同掌握了C++标准库中各种容器和算法的“语言”。它们形成了一个能力递增的层次结构，从最基础的单向读写，到最强大的随机访问。

输入迭代器 (Input Iterator) 这是最基础的迭代器类型。它只能单向（向前）遍历，并且只能读取元素，每个元素通常只能读取一次。想象一下从标准输入流（

std::cin

登录后复制

）读取数据，你读过的数据就“过去了”，不能回头再读，也不能写入。它们支持的操作包括：解引用（

*it

登录后复制

，返回const引用）、相等/不等比较（

it == it2

登录后复制

）、前置/后置自增（

++it

登录后复制

it++

登录后复制

）。它们是“一次性”的，主要用于算法中读取序列。

输出迭代器 (Output Iterator) 与输入迭代器类似，它也只能单向（向前）遍历，但它只能写入元素，每个位置通常也只能写入一次。你可以把它看作是向标准输出流（

std::cout

登录后复制

）写入数据。它们支持的操作包括：解引用（

*it

登录后复制

，返回非const引用，用于赋值）、前置/后置自增（

++it

登录后复制

it++

登录后复制

）。它们是“写一次性”的，主要用于算法中将结果写入序列。

前向迭代器 (Forward Iterator) 前向迭代器是输入迭代器和输出迭代器的结合体，并且能力有所提升。它既可以读取也可以写入元素（如果元素本身可写），并且可以多次遍历同一个范围。这意味着你可以安全地复制、存储和使用前向迭代器，多次经过同一个位置。它支持输入和输出迭代器的所有操作，但增加了多趟遍历的能力。

std::forward_list

登录后复制

的迭代器就是典型的前向迭代器。

双向迭代器 (Bidirectional Iterator) 顾名思义，双向迭代器在前向迭代器的基础上，增加了向后遍历的能力。这意味着你不仅可以

++it

登录后复制

，还可以

--it

登录后复制

。这对于需要双向遍历的算法非常有用，比如反转一个序列。

std::list

登录后复制

、

std::set

登录后复制

、

std::map

登录后复制

等容器的迭代器都是双向迭代器。我记得刚开始学C++的时候，能往回走的感觉简直是“解放”，很多算法的思路一下就打开了。

随机访问迭代器 (Random Access Iterator) 这是功能最强大的迭代器类型，也是能力层级中的“顶配”。它在双向迭代器的基础上，增加了像指针一样进行算术运算的能力，比如

it + n

登录后复制

（向前跳跃n个位置）、

it - n

登录后复制

（向后跳跃n个位置）、

it[n]

登录后复制

（访问it之后第n个位置的元素），以及迭代器之间的比较运算（

it < it2

登录后复制

）。这使得它们能够像访问数组元素一样高效地访问容器中的任何位置。

std::vector

登录后复制

、

std::deque

登录后复制

、

std::array

登录后复制

的迭代器都属于随机访问迭代器。可以说，如果你需要高效的随机访问，那么这些容器和它们的迭代器就是你的首选。

迭代器类型如何影响算法选择和性能？

迭代器的类型直接决定了C++标准库中各种算法（如

std::sort

登录后复制

、

std::find

登录后复制

、

std::reverse

登录后复制

等）能否应用于特定的容器，以及它们的执行效率。这不仅仅是“能不能用”的问题，更是“好不好用”、“快不快”的关键。

比如，

std::sort

登录后复制

算法需要能够随机访问元素，因为它在排序过程中需要频繁地跳跃到序列中的任意位置进行比较和交换。因此，它要求其操作的范围由随机访问迭代器来指定。如果你尝试用

std::list

登录后复制

（它只提供双向迭代器）去直接调用

std::sort

登录后复制

，编译器会告诉你不行，因为

std::list

登录后复制

的迭代器不满足

std::sort

登录后复制

对随机访问能力的要求。这时，你可能需要将

std::list

登录后复制

的内容拷贝到一个

std::vector

登录后复制

中进行排序，再拷贝回去，或者使用

std::list

登录后复制

自带的

sort()

登录后复制

成员函数，后者是为链表结构优化过的。

再比如，

std::advance(it, n)

登录后复制

函数，它的作用是将迭代器

it

登录后复制

向前移动

登录后复制

个位置。如果

it

登录后复制

是随机访问迭代器，这个操作通常是O(1)时间复杂度，因为它可以直接跳跃。但如果

it

登录后复制

只是一个前向迭代器或双向迭代器，那么它就需要通过

登录后复制

次递增（或递减）操作来达到目标位置，这会是O(n)的时间复杂度。这种差异在处理大数据集时，对程序性能的影响是巨大的。我记得有一次，我为了图方便，在一个循环里对一个

std::list

登录后复制

的迭代器做了很多次

std::advance

登录后复制

，结果程序慢得像蜗牛，最后才意识到是迭代器类型限制了操作效率。所以，理解迭代器能力，是写出高效、正确C++代码的基石。

如何判断一个容器支持哪种迭代器？

判断一个容器支持哪种迭代器类型，通常有几种方法，从最直接的查文档到更深入的语言特性探索。

最直接也是最推荐的方式，是查阅C++标准库的官方文档（例如cppreference.com）。每个标准容器的页面都会明确指出其提供的迭代器类型。例如，

std::vector

登录后复制

的文档会告诉你它提供的是随机访问迭代器，而

std::list

登录后复制

则提供双向迭代器。这就像查字典一样，是最权威、最准确的信息来源。

其次，可以根据容器的底层数据结构特性进行推断。

Giiso写作机器人

Giiso写作机器人，让写作更简单

查看详情

连续内存容器（如
```
std::vector
```
登录后复制
,
```
std::deque
```
登录后复制
,
```
std::array
```
登录后复制
）：它们的数据在内存中是连续存放的，因此天生就支持像数组下标一样的随机访问，所以它们提供随机访问迭代器。
链式结构容器（如
```
std::list
```
登录后复制
,
```
std::forward_list
```
登录后复制
）：它们的数据元素通过指针链接，一个元素只知道下一个（或上一个和下一个）元素的位置。因此，它们无法进行O(1)的随机跳跃，
```
std::list
```
登录后复制
提供双向迭代器，
```
std::forward_list
```
登录后复制
（单向链表）则只提供前向迭代器。
基于树的容器（如
```
std::set
```
登录后复制
,
```
std::map
```
登录后复制
,
```
std::multiset
```
登录后复制
,
```
std::multimap
```
登录后复制
）：这些容器通常基于平衡二叉树实现。虽然它们内部结构复杂，但迭代器设计上支持双向遍历，因此它们提供双向迭代器。

最后，如果你在写模板代码，并且需要在编译时判断迭代器类型以进行特化或优化，可以使用

std::iterator_traits<IteratorType>::iterator_category

登录后复制

。这个类型别名会返回一个标签类型，如

std::random_access_iterator_tag

登录后复制

、

std::bidirectional_iterator_tag

登录后复制

等，你可以用这些标签类型进行编译时判断。这在编写高度泛型和高效的库函数时非常有用，但对于日常应用开发来说，前两种方法更为常见和实用。说实话，这种编译时判断一开始会觉得有点“黑魔法”，但用熟了会发现它在构建通用算法时的强大之处。

迭代器失效（Iterator Invalidation）是如何发生的？

迭代器失效是C++中一个非常常见且容易导致运行时错误的问题，尤其是在对容器进行修改操作时。简单来说，当一个迭代器所指向的内存位置或元素不再有效，或者其内部状态与容器的实际状态不一致时，我们就说这个迭代器失效了。使用一个失效的迭代器，会导致未定义行为（Undefined Behavior），这通常意味着程序崩溃、数据损坏或者产生难以追踪的bug。我当年在这上面栽过不少跟头，那种莫名其妙的崩溃，查半天都不知道问题出在哪，最后才发现是迭代器偷偷“变质”了。

迭代器失效的主要原因通常与容器的结构性修改有关：

插入或删除元素导致容器重新分配内存：
- std::vector
  登录后复制
  和
  std::deque
  登录后复制
  ：当你向
```
std::vector
```
  登录后复制
  中插入元素，尤其是在中间或开头插入，或者当
```
std::vector
```
  登录后复制
  的容量不足需要重新分配更大的内存时，所有现有迭代器（包括指向
```
end()
```
  登录后复制
  的迭代器）都会失效。这是因为元素可能被移动到了新的内存地址。删除元素也可能导致迭代器失效，特别是删除点之后的元素。
```
std::deque
```
  登录后复制
  在头部或尾部插入/删除通常不会使所有迭代器失效，但在中间操作或容量变化时仍可能失效。
- 示例：
```
std::vector<int> v = {1, 2, 3};
auto it = v.begin() + 1; // it 指向 2
v.insert(v.begin(), 0);  // 插入元素，可能导致重新分配内存
// 此时，it 已经失效，再次使用 it 会导致未定义行为
```
  登录后复制
删除元素：
- std::list
  登录后复制
  、
  std::set
  登录后复制
  、
  std::map
  登录后复制
  ：这些容器的迭代器通常对插入操作比较健壮，因为它们是基于节点实现的，插入新节点不会影响现有节点的内存地址。然而，删除一个元素会使指向该元素的迭代器失效。
- 示例：
```
std::list<int> l = {1, 2, 3};
auto it = l.begin(); // it 指向 1
l.erase(it);         // 删除 1
// 此时，it 已经失效。
// 注意：l.erase(it) 会返回一个指向下一个有效元素的迭代器，应该使用返回值。
```
  登录后复制
容器清空（
```
clear()
```
登录后复制
）：
- 调用容器的
```
clear()
```
  登录后复制
  成员函数会移除所有元素，这会使所有指向该容器内部的迭代器失效。

如何避免迭代器失效？

了解容器特性： 熟记不同容器的迭代器失效规则是第一步。
重新获取迭代器： 在对容器进行可能导致迭代器失效的操作（如
```
insert
```
登录后复制
、
```
erase
```
登录后复制
）后，重新获取新的有效迭代器。
```
erase
```
登录后复制
成员函数通常会返回一个指向被删除元素之后的新有效迭代器，你应该使用它。
使用基于范围的for循环： 在许多情况下，使用
```
for (auto& elem : container)
```
登录后复制
这样的基于范围的for循环可以避免直接操作迭代器，从而减少迭代器失效的风险。
避免在循环中修改容器： 如果必须在循环中修改容器（例如删除元素），请小心处理迭代器。对于
```
std::vector
```
登录后复制
，通常从后向前遍历删除是更安全的策略，或者使用
```
remove-erase
```
登录后复制
惯用法。
使用
std::list
登录后复制
或关联容器：如果你的主要操作是频繁的插入和删除，并且对随机访问性能要求不高，那么
```
std::list
```
登录后复制
、
```
std::map
```
登录后复制
或
```
std::set
```
登录后复制
可能是更好的选择，因为它们的迭代器在插入和删除非自身元素时通常不会失效。