3.4.0 为什么要有迭代器

为了遍历与处理容器（container）中的数据元素

因为不是所有容器向string和vector一样支持下标，但每种容器都支持用迭代器来实现遍历和随机访问

3.4.1使用迭代器

迭代器使用与指针类似，都指向一个对象，并都用解引用符*来取出指向的对象

迭代器指向容器中的对象或者末尾对象的下一个位置

每个支持迭代器的类都有两个基本的迭代器成员(member)

vector<int> v;
//（暂时先用auto 自动指定迭代器类型）
auto it1 = v.begin(); //头迭代器：指向v的第一个对象
auto it2 = v.end();   //尾末迭代器：指向v的最后一个对象的 下一个位置

v.begin() == v.end()说明容器为空

迭代器的比较操作

iter1 == iter2：iter1和iter2指向相同的对象，反之iter1 != iter2

需要注意的是：迭代器一定支持 == 与 != 的比较，但不一定支持 < 和 > 等比较

用迭代器写一个遍历

#include<iostream>
#include<vector>
using namespace std;
int main(){
    vector<int> v = {1,2,3,4,5};
    for(auto it = v.begin(); it != v.end(); it++)  //it != v.end() 在此处也可写作 it < v.end()
        cout<<*it<<endl;
    return 0;
}

为什么写it != v.end()而不写 it < v.end()?

因为不是所有迭代器都定义了<比较符号

取出迭代器中的元素：解引用 *

• *it：取出迭代器it所指的对象
• it->member：取出迭代器it所指的对象的成员member，等价于(*it).member

注意：

1. 如果p是指向结构体的指针，p->member表示取出指针p所指向的结构体对象的成员member，等价于(*p).member【和迭代器的语法一致。】

2. 迭代器指向的对象的成员可能是数据成员，也可能是函数成员

   //如果v存储的第一个string非空，则打印出来
   vector<string> v; //v中存储的对象是string
   auto it = v.begin();
   if(!it->empty())  //it指向string类的对象,it->empty()调用了该对象的函数成员
       cout<<*it<<endl;
   

迭代器的类型

以string的迭代器为例，迭代器有两种类型

• string::iterator it：可以通过it读取和修改指向对象的值
• string::const_iterator it：只能通过it读取指向对象的值，无法修改

看几个典型情况

1. const容器的.beigin()和.end()的迭代器类型是xxx::const_iterator
2. 非const容器的.beigin()和.end()的迭代器类型xxx::iterator
3. 如果const容器需要使用const类型的迭代器，可以这么写x.cbegin()和x.cend()。x.cbegin()++的类型仍是const.

使用迭代器时的注意点

1. 在范围for内不要改变容器大小【如进行push_back()操作】
2. 在使用迭代器时，也不要改变容器大小【如进行push_back()操作】

3.4.2 迭代器的算术操作

常见操作

典型案例：二分查找

注意，auto mid = (beg + end) /2是错误写法，两迭代器的相加运算式未定义的