iterator

1. 迭代器和下标运算符
   
   标准库定义了若干种容器，所有标准库容器都可以使用迭代器，这些容器中只有少数几种支持下标运算符
   

   下标运算符用来遍历，其实是限制了它的能力，下标运算符的本质是随机访问指定元素，而支持随机访问的容器并不多
   

2. 迭代器
   
   一种类型，用于访问容器中的元素或者在元素之间移动
   

   每个容器类都定义了一个名为iterator的类型，该类型支持迭代器概念所规定的的一套操作
   

   迭代器提供了对对象的间接访问
   

   迭代器指向的对象是容器中的元素，或string对象中的字符
   

   迭代器从一个元素移动到另一个元素，借以达到访问某个元素的功能
   

   迭代器有有效和无效之分
   

   有效的迭代器指向某个元素，或指向容器中尾元素的下一位置，否则为无效
   

   拥有迭代器的类型同时拥有返回迭代器的接口
   

   使用迭代器遍历容器时，建议使用相等性判断而不是关系运算符，因为标准库提供的所有容器都实现了相等性判断，而少数容器实现了关系运算符
   

3. string类型
   
   string不是容器，但配有迭代器类型
   

   迭代器遍历容器中的元素, 遍历string对象中的字符
   

接口: 返回迭代器

-
begin()	返回指向第一个元素（或第一个字符）的迭代器
end()	返回指向容器（或string对象）尾元素的下一位置的迭代器
cbegin()	无论vector对象是否是常量，返回const_iterator
cend()	无论vector对象是否是常量，返回const_iterator

Copy1auto b = v.begin(), e = v.end();
2// 可以看出，b和e类型相同

尾后元素和尾后迭代器

1. 尾后元素
   
   将尾元素之后的这个不存在的元素称作尾后元素
   

2. 尾后迭代器
   
   end操作返回尾后迭代器, 指向尾后元素, 又称作尾迭代器
   

   尾后迭代器无实际含义，但作为一个标记，意味着已处理完容器中的所有元素
   

   不可以对尾后迭代器进行解引用
   

判断容器为空

判断容器为空的一个充分必要条件是，begin成员和end成员返回相同迭代器，即尾后迭代器

如果容器对象是常量，begin和end返回const_iterator，否则返回iterator

标准容器迭代器的运算符

-
*iter	返回迭代器所指元素的引用
iter->mem	解引用iter并获取其成员mem的引用；等价于(*iter).mem
++iter	令iter指示容器中的下一个元素；也有一种描述是向前移动一个位置，这里的前应理解为forward，与后backward相对应
–iter	令iter指示容器中的上一个元素

注意:

1. 执行解引用操作时，迭代器必须合法并确实指向某个元素
   
2. 试图解引用一个非法迭代器或者尾后迭代器都会引发未定义的行为
   

判等运算符: 若iter1和iter2指示同一个元素，或同一个容器的尾后迭代器，二者相等；否则不等

-
iter1 == iter2
iter1 != iter2

使用迭代器遍历容器

Copy1for (auto it = s.begin(); it != s.end(); ++it)
2{
3    // Process
4}

迭代器类型

使用关键字iterator和const_iterator

-
iterator	可对迭代器所指的对象进行读写
const_iterator	对迭代器所指的对象，可读不可写；如果vector对象或string对象是常量，则必须使用const_iterator类型；属于底层const，auto和decltype均不会忽略
difference_type	有符号整数类型；表示两个迭代器之间的距离

Copy 1vector<int>::iterator it;
 2string::iterator it2;
 3
 4vector<int>::const_iterator it3;
 5
 6vector<int> v;
 7const vector<int> cv(10);        // 不能使用列表初始化，不知道为什么
 8
 9auto it4 = v.begin();        // it4的类型为vector<int>::iterator
10auto it5 = cv.begin();       // it5的类型为vector<int>::const_iterator

迭代器运算

-
iter + n	给定方向，向前移动n
iter - n	给定方向，向后移动n
iter += n	移动后更新迭代器
iter -= n	移动后更新迭代器

参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾后元素

	-
iter1 - iter2	两个迭代器的距离；类型为difference_type，有符号类型
>, >=, <, <=

Copy 1// 使用迭代器运算的二分查找
 2// 假定text有序
 3
 4auto beg = text.begin(), end = text.end();
 5auto mid = text.begin() + (end - beg) / 2;
 6
 7while (mid != end && *mid != sought)
 8{
 9    // 进入循环体则意味着应该取左右两个区域中的一个
10    if (sought < *mid)
11        end = mid;
12    else
13        begin = mid + 1;
14    mid = beg + (end - beg) / 2;
15}
16
17// 退出循环后比对mid所指的对象和要查找的值，不等则未查找到