7. 迭代器iterator

string对象的字符或者vector对象的元素都可以使用下标进行访问，但在C++标准库容器中只有少数几种支持下标运算符

迭代器（iterator）是一种更加通用的元素访问方式，所有的标准库容器均可使用

• 类似指针，迭代器提供对对象的间接访问
• 与指针不同的是迭代器不使用取址符号，有迭代器类型，同时有返回迭代器的成员

一、迭代器使用

• begin成员用于返回指向第一个元素（或第一个字符）的迭代器

• end成员返回容器（或string对象）末尾元素的下一个位置的迭代器

  • end返回的迭代器是容器中不存在的一个尾后元素，没有实际含义，仅仅是一个标记
  • 常被称为尾后迭代器或简称尾迭代器

• 如果容器为空，那么begin和end返回的是同一个迭代器

1.1 引用和解引用

*iter			// 返回迭代器iter所指元素的引用
    
iter->mem		// 解引用iter，并获取该元素的名为mem的成员，等价于：(*iter).mem
1
2
3

• 可通过解引用迭代器来获取它所指的元素，执行解引用的迭代器必须合法并确实指示着某个值

string s("some string");

if (s.begin() != s.end()) {	// 确保s非空
    auto it = s.begin();	// 声明一个迭代器变量it并将begin返回结果赋给他, 即得到指示s中首字符的迭代器
    *it = toupper(*it);		// 通过解引用运算符*获取该迭代器指向的元素
}
1
2
3
4
5
6

• 解引用可以获得迭代器所指对象，如果该对象类型是类，那么就可以进一步访问其成员

(*it).empty()
1

it是一个字符串组成的vector对象，则可以用empty成员函数检查其是否为空

• 解引用运算符（*）的运算优先级低于点运算符（.），因此迭代器解引用必须加上圆括号

• 箭头运算符（ -> ）：将解引用和成员访问两个操作结合在一起

it->mem

// 等价于 (*it).mem
1
2
3

1.2 将迭代器从一个元素移动到另外一个元素

++iter		// 令iter指示容器中的下一个元素
    
--iter		// 令iter指示容器中的上一个元素
1
2
3

例子：使用迭代器遍历string对象

for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it) {
    
    *it = toupper(*it);	// 解引用it, 将结果传入toupper函数得到对应大写形式
    
}


// 首先用s.begin的返回值初始化it, it指示的是s中的第一个字符
// 条件部分检查是否到达s的尾部( it != s.end() ), 如果没有则将it解引用结果传入isspace函数检查是否遇到空白
// 每次迭代的最后，执行++it令迭代器前移一个位置以访问下一个元素
1
2
3
4
5
6
7
8
9
10

• end返回的迭代器并不实际指示某个元素，所以不能对其进行递增或解引用操作

二、迭代器运算

iter + n		     // 迭代器加上一个整数值仍得一个迭代器
iter - n		     // 迭代器减去一个整数值仍得一个迭代器
    
iter += n	         // iter = iter + n
iter -= n		    // iter = iter - n    
    
iter1 - iter2		// 两个迭代器之间的距离
    
> 、>= 、< 、 <=	  // 两个迭代器的关系运算符，一个迭代器iter1的位置在另一个迭代器iter2位置之前, 则iter1 < iter2 
1
2
3
4
5
6
7
8
9

例子：二分搜索，寻找sought

// text必须是有序的
// beg和end表示我们搜索的范围
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg)/2;	// 初始状态下的中间点

// 当还有元素没有检查且还没找到sought时执行循环
while (mid != end && *mid != sought) {
    
    if (sought < *mid) {	// 判断是否在前半部分
        end = mid;		    // 如果是，则忽略掉后半部分
    } else {			   // 不在前半部分那就在后半部分
        beg = mid + 1;		// 调整搜索范围，在mid之后开始找
    }
    
    mid = beg + (end - beg)/2;	// 计算新的中间点	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16