C++迭代器（Iterator）详解：从原理、使用方法到底层实现全面掌握

1. 什么是迭代器？

在C++ STL（Standard Template Library，标准模板库）中，迭代器（iterator）是连接容器和算法的桥梁。

简单来说：

迭代器是一种类似指针的对象，它可以访问容器中的元素，并且能够遍历容器。

例如：

vector<int> v = {1,2,3,4,5};

for(auto e : v)
{
cout << e << " ";
}

这是C++11提供的范围for，本质上编译器帮我们使用了迭代器。

实际上：

for(auto e : v)

大致等价于：

auto begin = v.begin();
auto end = v.end();

while(begin != end)
{
cout << *begin << " ";

++begin;
}

这里：

• begin() 返回第一个元素的位置

• end() 返回最后一个元素的下一个位置

• *begin 获取元素

• ++begin 移动到下一个元素

2. 为什么需要迭代器？

2.1 不同容器底层结构不同

STL中有很多容器：

访问方式完全不同。

例如：

vector

内存连续：

+—+—+—+—+
|10 |20 |30 |40 |
+—+—+—+—+

地址:
100 104 108 112

可以通过指针移动：

ptr++;

list

链表：

10
|
v
20
|
v
30
|
v
40

节点地址可能完全不连续：

1000 -> 5000 -> 2000

无法：

ptr++;

因为下一个节点不一定在下一个地址。

2.2 迭代器统一访问方式

有了迭代器：

vector：

vector<int>::iterator it;

list：

list<int>::iterator it;

map：

map<int,int>::iterator it;

虽然底层完全不同，但是遍历方式一样：

for(auto it=container.begin();
it!=container.end();
++it)
{
cout<<*it;
}

这就是STL设计思想：

不关心容器底层，只通过迭代器访问元素。

3. 迭代器的本质

迭代器本质是一种类对象。

例如：

vector<int>::iterator it;

实际上：

iterator

是vector内部定义的一个类型。

简单模拟：

template<class T>
class VectorIterator
{
public:

T* ptr;

T& operator*()
{
return *ptr;
}

VectorIterator& operator++()
{
ptr++;

return *this;
}
};

这个类实现：

• *

• ++

• !=

于是它就像指针一样使用。

4. 迭代器的基本使用

4.1 begin()

返回第一个元素的位置：

vector<int> v={1,2,3};

auto it=v.begin();

cout<<*it;

输出：

1

结构：

begin()
|
v

+—+—+—+
| 1 | 2 | 3 |
+—+—+—+
^
it

4.2 end()

返回最后一个元素后面的位置：

auto it=v.end();

注意：

end不是最后一个元素。

而是：

+—+—+—+—-+
| 1 | 2 | 3 | |
+—+—+—+—-+
^
end

所以：

错误：

cout<<*v.end();

这是非法访问。

5. 使用迭代器遍历容器

vector遍历

#include<iostream>
#include<vector>

using namespace std;

int main()
{
vector<int> v={1,2,3,4};

vector<int>::iterator it=v.begin();

while(it!=v.end())
{
cout<<*it<<" ";

++it;
}

return 0;
}

输出：

1 2 3 4

6. auto简化迭代器

以前：

vector<int>::iterator it;

非常长。

C++11：

auto it=v.begin();

编译器自动推导类型。

推荐：

for(auto it=v.begin();
it!=v.end();
++it)
{
cout<<*it;
}

7. const_iterator

普通迭代器：

iterator

可以修改元素。

例如：

vector<int> v={1,2,3};

auto it=v.begin();

*it=100;

结果：

100 2 3

但是：

如果只想读取：

使用：

const_iterator

例如：

vector<int>::const_iterator it;

it=v.begin();

此时：

*it=100;

错误。

原因：

不能通过const迭代器修改数据。

8. reverse_iterator（反向迭代器）

普通迭代器：

方向：

begin()
|
v

1 2 3 4

反向迭代器：

rbegin()

4 3 2 1

使用：

vector<int> v={1,2,3,4};

auto it=v.rbegin();

while(it!=v.rend())
{
cout<<*it<<" ";

++it;
}

输出：

4 3 2 1

9. 五种迭代器类型

STL根据功能不同，把迭代器分为五类。

9.1 输入迭代器（Input Iterator）

特点：

只能读取。

支持：

*
++
==
!=

例如：

读取文件：

istream_iterator

9.2 输出迭代器（Output Iterator）

只能写。

例如：

ostream_iterator

用于输出：

copy(v.begin(),
v.end(),
ostream_iterator<int>(cout," "));

9.3 前向迭代器（Forward Iterator）

支持：

• 读取

• 写入

• ++移动

例如：

forward_list

9.4 双向迭代器（Bidirectional Iterator）

支持：

向前：

++

向后：

—

例如：

list
map
set

9.5 随机访问迭代器（Random Access Iterator）

功能最强。

支持：

+
–
[]
<
>

例如：

vector：

it+5

deque：

it-2

迭代器能力关系

Random Access
|
Bidirectional
|
Forward Iterator
|
Input Iterator

能力越往上越强。

10. 不同容器迭代器类型

11. 迭代器失效问题（重点）

这是面试高频问题。

所谓迭代器失效：

迭代器仍然保存地址，但是这个地址已经不是有效元素。

11.1 vector插入导致失效

例如：

vector<int> v={1,2,3};

auto it=v.begin();

v.push_back(4);

cout<<*it;

可能错误。

原因：

vector扩容：

原空间：

1000:

1 2 3

扩容：

5000:

1 2 3 4

旧地址释放。

it仍指向1000。

失效。

11.2 vector删除导致失效

vector<int> v={1,2,3};

auto it=v.begin();

v.erase(it);

删除后：

2 3

原来的it失效。

11.3 list迭代器失效

list：

node1 -> node2 -> node3

删除node2：

node1 -> node3

只有删除节点的迭代器失效。

其他迭代器仍有效。

12. erase正确使用方式

错误：

for(auto it=v.begin();
it!=v.end();
++it)
{
if(*it==3)
v.erase(it);
}

原因：

erase后it失效。

正确：

for(auto it=v.begin();
it!=v.end();)
{
if(*it==3)
{
it=v.erase(it);
}
else
{
++it;
}
}

因为：

vector/list的erase会返回删除位置后的迭代器。

13. 迭代器和指针区别

很多人认为：

迭代器就是指针。

不完全正确。

指针：

直接操作地址：

int* p;

只能访问内存。

迭代器：

是一种抽象。

可能：

• 是指针

• 是类对象

例如：

vector：

iterator ≈ T*

list：

iterator:

{
Node* node;
}

14. 迭代器和算法

STL算法：

sort
find
copy
reverse

都使用迭代器。

例如：

排序：

vector<int> v={3,1,2};

sort(v.begin(),
v.end());

sort不知道：

• vector是什么

• 数据在哪里

它只认识：

begin()
end()
++
*

15. 迭代器底层思想

STL采用：

泛型编程

算法：

template<class Iterator>

void sort(Iterator first,
Iterator last)

不关心类型。

只要求：

这个Iterator满足随机访问能力。

这就是：

面向接口编程。

16. 常用迭代器接口总结

17. 迭代器总结

什么是迭代器？

迭代器是STL中用于访问容器元素的一种对象，本质是对指针的封装。

为什么需要迭代器？

因为：

• 不同容器底层不同

• 统一算法访问方式

核心使用：

auto it=container.begin();

while(it!=container.end())
{
cout<<*it;

++it;
}

必须掌握：