[C++知识库]C++学习笔记5：迭代器

补充C++基础笔记。

迭代器

所有标准库容器都可以使用迭代器，但只有少数几种才同时支持下标运算符。

使用迭代器

1. begin和end
   begin返回指向第一个元素的迭代器auto b = v.begin();
   end返回指向容器“尾元素的下一位置”的迭代器auto e = v.end()。

2. 标准容器迭代器的运算符

*iter   //返回迭代器iter所指元素的引用
iter->mem   //解引用iter并获取该元素的名为mem的成员，等价于(*iter).mem
++iter   //令iter指示容器中的下一个元素
--iter   //令iter指示容器中的上一个元素
iter1 == iter2   //判断两个迭代器是否相等
iter1 != iter2

一个小例子：string中的第一个字母改成大写

string s("some string");
if (s.begin() != s.end()) {
	auto it = s.begin();
	*it = toupper(*it);
}

3. 迭代器类型：拥有迭代器的标准库使用iterator和const_iterator来表示迭代器的类型

vector<int>::iterator it;    //it能读写vector<int>的元素
string::iterator it2;   //it2能读写string对象中的字符

vector<int>::const_iterator it3;   //it3只能读元素，不能写元素
string::const_iterator it4;   //it4只能读字符，不能写字符

使用begin和end时，返回的类型由对象是否是常量决定，如果对象是常量，那么begin和end返回const_iterator。
C++11新标准引入了cbegin和cend，这时无论vector对象(或string对象)本身是否是常量，返回值都是const_iterator。

4. 解引用和成员访问操作
   解引用迭代器可以获得迭代器所指对象，若该对象的类型恰好是类，就有可能希望进一步访问它的成员，由字符串组成的vector，想检查其元素是否为空，则令it是该vector对象的迭代器，检查it所指字符串是否为空就可以：
   (*it).empty
   C++定义了箭头运算符：
   it -> empty() 与 (*it).empty 表达的意思相同。
   小例子：输出text字符串向量中第一段的内容：

for (auto it = text.cbegin(); it != text.end && !it->empty(); ++it)
	cout << *it <<endl;

5. 注意点：凡是使用了迭代器的循环体，都不要向迭代器所属的容器添加元素。

迭代器运算

iter + n    //向前移动n个元素的迭代器
iter - n    //向后移动n个元素的迭代器
iter1 += n
iter1 -= n
>, >=, <, <=    //前后关系

小例子：使用迭代器完成二分搜索

//text必须是有序的
//beg和end表示我们的搜索范围
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg)/2;   //中间点，end和beg只能做减法，不能做加法

while (mid != end && *mid != sought) {
	if (sought < *mid)
		end = mid;
	else
		beg = mid + 1;
	mid = beg + (end - beg)/2;	
}