迭代器简介

迭代器是种遍历容器内元素的 数据类型，这种数据类 型感觉有点像指针，我们理解的时候就理解为迭代器用来指向容器中的某个元素。
string, vector, []， 很少用[]来访问元素，更常用的访问方式就是用迭代器(更通用)。

通过迭代器，我们就可以读容器中的元素值，读string中的每个字符，还可以修改某个迭代器所指向的元素值。迭代器像指针一样支持++，–操作

list,map,通常用迭代器来访问元素。

容器的迭代器类型

1
2
vector<int> iv = {100,200,300};
vector<int>::iterator iter;//定义迭代器，也必须是vector<int>

每个容器都会定义一个iterator固定成员，可以把整个vector<int>::iterator理解为一个类型，这种类型就专门应用于迭代器。
当我们用这个类型定义一个变量的时候，这个变量，就是个迭代器，这里iter这个变量就是个迭代器。

迭代器操作

迭代器begin()/end()操作

begin()/end()返回的是迭代器类型，可以理解为返回一个迭代器。

1
2
3
4
5
6
vector<int> iv = {100,200,300};
vector<int>::iterator iter;
iter = iv.begin();//如果容器中有元素,则begin返回的迭代器，指向的是容器中的第一个元素。
 				//相当于iter指向了iv[0]即100

iter = iv.end();//end返回的迭代器指向的并不是末端元素，而是元素的后边，我们理解为一个不存在的元素

image-20220313162723439

如果一个容器是空容器，那么begin()和end()返回的迭代器相同。

1
2
3
4
5
vector<int>iv2;
vector<int>::iterator iterbegin = iv2.begin();
vector<int>::iterator iterend = iv2.end();
if (iterbegin == iterend)
    cout<< "容器iv2为空" << endl;//打印此句

传统用法：

1
2
3
4
vector<int> iv = {100,200,300};
for(vector<int>::iterator iter = iv.begin();iter != iv.end();iter++){
    //....
}

反向迭代器rbegin()/rend()操作

image-20220313163132913

反向迭代器：大家想从后往前遍历一个容器，那么反向迭代器就比较方便。
反向迭代器(逆向迭代器)，用的rbegin(), rend() ;

rbegin()：返回一个反向迭代器，指向反向迭代器的第一个元素;
rend()：返回一个反向迭代器，

迭代器运算符

*iter

*iter：返回迭代器iter所指向元素的引用。**必须要保证这个迭代器指向的是有效的容器元素，不能指向end(),**因为end()是末端元素的后边。也就是end指向的是一个不存在的元素。

++iter，–iter

++让迭代器指向容器的下一个元素，已经指向end()的时候你不能再++iter;

--让迭代器指向容器的上一个元素，已经指向begin()的时候不能再--iter;

==，!=

iter1 ==iter2, iter1!= iter2。判断两个迭代器是否相等。
如果两个迭代器指向的是同一个元素，就相等，否则就不等。

如何引用结构的成员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct student{
    int num;
};

int main(){
    vector<student> sv;
    student mystu;
    mystu.num = 100;
    
    sv.push_back(mystu);//把mystu拷贝到了sv容器内
    
    vector<student>::iterator iter;
    iter = sv.begin();

    //以下两种写法均可
    cout << (*iter).num << endl;
    cout << iter->num << endl;
    return 0;
}

const_iterator迭代器

表示迭代器指向的元素的值不能改变，但迭代器本身可以改变，可以不断指向下一个元素。表示只能读元素，不能通过这个迭代器改写元素，有点像常量指针。实际而言还是可以修改元素的，只是不用能代器修改元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> iv = { 100,200,300 };
    vector<int>::const_iterator iter;

    iv[1] = 2000;

    for (iter = iv.begin(); iter != iv.end(); iter++) {
        //*iter = 123;//error
        cout << *iter << " ";//成功打印 100 2000 300
    }
    return 0;
}

cbegin(),cend()

c++11引入的两个新函数cbegin (), cend()，跟begin, end类似。cbegin,cend，返回的都是常量迭代器

迭代器失效

1
2
3
4
5
6
7
8
for (auto e : iv) {//内部实质上是迭代器
    cout << e << endl;
}
//等价于
for (auto beg = iv.begin(),end = iv.end(); beg != end; ++beg){
    //iv.push_back(888);error绝对不可以这样做
    cout << *beg << endl;
}

在操作迭代器的过程中(使用了迭代器这种循环体)，千万不要改变vector容器的容量，不要增加或者删除vector容器中的元素

往容器中增加或者从容器中删除元素，这些操作可能会使指向容器元素的指针、引用、迭代器失效，
失效就表示不能再代表任何容器中的元素。一旦使用失效的东西，就等于犯了严重的错误，程序会直接崩溃。

iv.insert(begin,800)插入新值，第一个参数为插入位置，第二个参数为插入的元素。
这一插入，肯定会导致迭代器失效。比如begin, end失效。
具体的哪个迭代器失效，取决于这个容器vector内部的实现原理，最明智的做法，就是我们只要一插入数据， 插入完毕就break出循环体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<vector>
using namespace std;

int main() {
    vector<int> iv = { 100,200,300,400,500 };
    vector<int>::iterator iter;

    auto end = iv.end();

    while (iter != iv.end()) {//iv.end()一直在变
        iv.erase(iter);//危险操作
    }

    while (iter != iv.end()) {//iv.end()一直在变
        iter = iv.erase(iter);//ok
    }

    iv.clear();//ok

    //最优秀的办法如下
    while (!iv.empty()) {
        auto iter = iv.begin();
        iv.erase(iter);
    }

    return 0;
}

迭代器分类

image-20220315210814195

大多数容器里边都有一个::iterator迭代器类型;并不是所有容器里都有迭代器;比如stack,queue这种容器就不提供迭代器;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <map>
#include <set>
using namespace std;


void _display_category(input_iterator_tag) {
    cout << "input_iterator_tag" << endl;
}
void _display_category(random_access_iterator_tag) {
    cout << "random_access_iterator_tag" << endl;
}
void _display_category(forward_iterator_tag) {
    cout << "forward_iterator_tag" << endl;
}
void _display_category(output_iterator_tag) {
    cout << "output_iterator_tag" << endl;
}
void _display_category(bidirectional_iterator_tag) {
    cout << "bidirectional_iterator_tag" << endl;
}

template <typename T>
void display_category(T ite) {
    cout << "-------------begin-------------" << endl;

    //这个类型叫 过滤器（萃取机）用来获取T迭代器类型的种类
    typename iterator_traits<T>::iterator_category cagy;//相当于获取迭代器种类
    _display_category(cagy);
    cout << "typeid(ite).name = " << typeid(ite).name() << endl;

    cout << "-------------end-------------" << endl;
}

void func()
{
    display_category(array<int, 100>::iterator());//iterator()表示产生一个临时对象
    display_category(vector<int>::iterator());
    display_category(list<int>::iterator());
    display_category(map<int, int>::iterator());
    display_category(set<int>::iterator());
}

int main()
{
    func();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-------------begin-------------
random_access_iterator_tag
typeid(ite).name = class std::_Array_iterator<int,100>
-------------end-------------
-------------begin-------------
random_access_iterator_tag
typeid(ite).name = class std::_Vector_iterator<class std::_Vector_val<struct std::_Simple_types<int> > >
-------------end-------------
-------------begin-------------
bidirectional_iterator_tag
typeid(ite).name = class std::_List_iterator<class std::_List_val<struct std::_List_simple_types<int> > >
-------------end-------------
-------------begin-------------
bidirectional_iterator_tag
typeid(ite).name = class std::_Tree_iterator<class std::_Tree_val<struct std::_Tree_simple_types<struct std::pair<int const ,int> > > >
-------------end-------------
-------------begin-------------
bidirectional_iterator_tag
typeid(ite).name = class std::_Tree_const_iterator<class std::_Tree_val<struct std::_Tree_simple_types<int> > >
-------------end-------------

image-20220315212756345

输入迭代器 (input iterator)

image-20220315213304559

输入迭代器用于从一个对象中不断读出元素。

除了迭代器基本操作，还需要支持：

  1. 比较两个迭代器是否指向相同元素 i == j 和 i != j
  2. 访问元素的成员 i->m
  3. 后缀自增操作 i++

输入迭代器不需要保证自增操作之后，之前的迭代器依然有意义。典型的例子是用于读取流文件的迭代器：每次自增之后，都无法回复到原来的位置。也包括随机数生成器的迭代器：每次自增之后，随机数生成器的状态都发生了变化。

输出迭代器 (output iterator)

image-20220315213243741

输出迭代器用于向一个对象不断添加元素。

除了迭代器基本操作，还需要支持：

  1. 修改元素 *i = v
  2. 后缀自增操作 i++

输出迭代器也不保证自增之后，之前的迭代器有意义，并且它还不保证修改元素之后访问元素有意义。典型的例子是用于写入流文件的迭代器和向容器中插入元素的 **插入迭代器 (insert iterator)**。

前向迭代器 (forward iterator)

image-20220315213344909

前向迭代器用于访问一个容器中的元素。

因此，它必须提供输入迭代器的所有操作，如果它用于访问一个非 const 容器，还需要支持输出迭代器的所有操作。

在此基础上，它需要保证自增之后，其他的迭代器仍然有意义（比输入迭代器要求更高）。它也需要保证可以不受限制地修改和访问当前元素（比输出迭代器要求更高）。

典型的例子包括各种容器的迭代器，比如 vector、list、map 的迭代器。

双向迭代器 （bidirectional iterator）

image-20220315213402298

双向迭代器首先是一个前向迭代器，除此之外，它还需要支持自减操作 --i 和 i-- 。

一个线性存储元素的容器应该提供双向迭代器，例如 vector 和 list。

随机访问迭代器 (random access iterator)

image-20220315213432378

随机访问迭代器是所有迭代器种类中最强大的，它除了需要支持前向迭代器的所有操作，还支持加上任意偏移量并得到新的迭代器，即 i + n，其中 n 可以是正数也可以是负数，分别表示向前或向后随机访问。

它需要支持的完整操作包括：

  1. 加上或减去一个偏移量 i + n 和 i - n
  2. 自加或自减一个偏移量 i += n 和 i -= n
  3. 计算两个迭代器的距离 i - j
  4. 使用下标形式的加上一个偏移量 i[n]，其效果等价于 *(i + n)
  5. 比较两个迭代器的先后顺序 a < b a <= b a > b a >= b

我们可以发现，随机访问迭代器在功能上已经等价于指针。

一般来说，只有 vector 这类线性且连续存储元素的容器才会提供随机访问迭代器。