迭代器简介
迭代器（Iterator）是C++标准模板库（STL）中的一个重要概念，它提供了一种方法，按顺序访问容器（如vector, list, map等）中的元素，而无需暴露容器的内部表示。迭代器就像是一个指针，但它比指针更加安全，因为它只能访问容器内的元素，并且它的类型与容器紧密相关。
使用迭代器
和指针不一样的是，获取迭代器不是使用取地址符，有迭代器的类型同时拥有返回迭代器的成员。比如，这些类型都拥有名为begin和end的成员，其中begin成员负责返回指向第一个元素（或第一个字符）的迭代器。如有下述语句：
auto b = v.begin(), e = v.end(); //b和e的类型相同
end成员则负责返回指向容器（或string对象）“尾元素的下一位置（one past the end）”的迭代器，也就是说，该迭代器指示的是容器的一个本不存在的“尾后（off the end）”元素。
这样的迭代器没什么实际含义，仅是个标记而已，表示我们已经处理完了容器中的所有元素。end成员返回的迭代器常被称作尾后迭代器（off-the-end iterator）或者简称为尾迭代器（end iterator）。特殊情况下如果容器为空，则begin和end返回的是同一个迭代器。
特殊情况下如果容器为空，则begin和end返回的是同一个迭代器。
一般来说，我们不清楚（不在意）迭代器准确的类型到底是什么。在上面的例子中，使用auto关键字定义变量b和e，这两个变量的类型也就是begin和end的返回值类型，之后将对相关内容做更详细的介绍。
迭代器运算
符表3.6列举了迭代器支持的一些运算。使用==和！=来比较两个合法的迭代器是否相等，如果两个迭代器指向的元素相同或者都是同一个容器的尾后迭代器，则它们相等；否则就说这两个迭代器不相等。
和指针类似，也能通过解引用迭代器来获取它所指示的元素，执行解引用的迭代器必须合法并确实指示着某个元素。
试图解引用一个非法迭代器或者尾后迭代器都是未被定义的行为。举个例子，利用下标运算符把string对象的第一个字母改为了大写形式，下面利用迭代器实现同样的功能：
比较运算
std::string s("some string");
//确保s非空
if(s.begin() != s.end()){
//第一个字母改为大写
auto it = s.begin();
*it = toupper(*it);
}
本例和原来的程序一样，首先检查s是否为空，显然通过检查begin和end返回的结果是否一致就能做到这一点。如果返回的结果一样，说明s为空；
如果返回的结果不一样，说明s不为空，此时s中至少包含一个字符。
我们在if内部，声明了一个迭代器变量it并把begin返回的结果赋给它，这样就得到了指示s中第一个字符的迭代器，接下来通过解引用运算符将第一个字符更改为大写形式。
和原来的程序一样，输出结果将是：
Some string
自增运算
将迭代器从一个元素移动到另外一个元素迭代器使用递增（++）运算符。
来从一个元素移动到下一个元素。从逻辑上来说，迭代器的递增和整数的递增类似，整数的递增是在整数值上“加1”，迭代器的递增则是将迭代器“向前移动一个位置”。
注意
因为end返回的迭代器并不实际指示某个元素，所以不能对其进行递增或解引用的操作。
把字符串中的第一个单词改为大写
std::string s2 = "another string";
for(auto it = s2.begin(); it != s2.end() &&
!isspace(*it); ++it) {
*it = toupper(*it);
}
std::cout << s2 << std::endl;
输出
ANOTHER string
循环首先用s.begin的返回值来初始化it，意味着it指示的是s中的第一个字符（如果有的话）。
条件部分检查是否已到达s的尾部，如果尚未到达，则将it解引用的结果传入isspace函数检查是否遇到了空白。
每次迭代的最后，执行++it令迭代器前移一个位置以访问s的下一个字符。
循环体内部和上一个程序if语句内的最后一句话一样，先解引用it，然后将结果传入toupper函数得到该字母对应的大写形式，再把这个大写字母重新赋值给it所指示的字符。
关键概念：泛型编程
原来使用C或Java的程序员在转而使用C++语言之后，会对for循环中使用！=而非<进行判断有点儿奇怪，
C++程序员习惯性地使用！=，其原因和他们更愿意使用迭代器而非下标的原因一样：因为这种编程风格在标准库提供的所有容器上都有效。
之前已经说过，只有string和vector等一些标准库类型有下标运算符，而并非全都如此。与之类似，所有标准库容器的迭代器都定义了==和！=，但是它们中的大多数都没有定义<运算符。因此，只要我们养成使用迭代器和！=的习惯，就不用太在意用的到底是哪种容器类型。
迭代器类型
就像不知道string和vector的size_type成员到底是什么类型一样，一般来说我们无须知道迭代器的精确类型。而实际上，那些拥有迭代器的标准库类型使用iterator和const_iterator来表示迭代器的类型：
// 迭代器it, it能读写vector<int>的元素
std::vector<int>::iterator it;
// it2能读写string对象的字符
std::string::iterator it2;
// it3只能读元素，不能写元素
std::vector<int>::const_iterator it3;
// it4只能读字符,不能写字符
std::string::const_iterator it4;
const_iterator和指向常量的指针差不多，能读取但不能修改它所指的元素值。相反，iterator的对象可读可写。
如果vector对象或string对象是一个常量，只能使用const_iterator；如果vector对象或string对象不是常量，那么既能使用iterator也能使用const_iterator。
std::vector<int> numbers = {1, 2, 3, 4, 5};
// 使用 const_iterator 遍历
std::vector<int>::const_iterator it;
for (it = numbers.cbegin(); it != numbers.cend(); ++it) {
std::cout << *it << " "; // 读取元素值
}
std::cout << std::endl;
术语：迭代器和迭代器类型
迭代器这个名词有三种不同的含义：可能是迭代器概念本身，也可能是指容器定义的迭代器类型，还可能是指某个迭代器对象。
重点是理解存在一组概念上相关的类型，我们认定某个类型是迭代器当且仅当它支持一套操作，这套操作使得我们能访问容器的元素或者从某个元素移动到另外一个元素。
每个容器类定义了一个名为iterator的类型，该类型支持迭代器概念所规定的一套操作。
begin和end运算符
begin和end返回的具体类型由对象是否是常量决定，如果对象是常量，begin和end返回const_iterator；如果对象不是常量，返回iterator：
std::vector<int> v;
const std::vector<int> cv;
//it1是 vector<int>的迭代器，
auto it1 = v.begin();
//it2是const vector<int>的迭代器
auto it2 = cv.begin();
c++11
如果一个容器非常量，我们也可以通过分别是cbegin和cend：获取对应的常量迭代器
//it3的类型是vector<int>::const_iterator
auto it3 = v.cbegin();
结合解引用和成员访问操作
解引用迭代器可获得迭代器所指的对象，如果该对象的类型恰好是类，就有可能希望进一步访问它的成员。例如，对于一个由字符串组成的vector对象来说，要想检查其元素是否为空，令it是该vector对象的迭代器，只需检查it所指字符串是否为空就可以了，其代码如下所示：
(*it).empty()
(*it).empty()中的圆括号必不可少，该表达式的含义是先对it解引用，然后解引用的结果再执行点运算符。
如果不加圆括号，点运算符将由it来执行将报错
完整案例
std::vector<std::string> vs = {"hello", "world"};
for(auto it = vs.begin(); it != vs.end(); ++it){
//(*it)解引用获取string对象，再次调用empty()方法判断为空
if((*it).empty()){
std::cout << "empty string" << std::endl;
}
}
为了简化上述表达式，C++语言定义了箭头运算符（->）。箭头运算符把解引用和成员访问两个操作结合在一起，也就是说，it->mem和(*it).mem表达的意思相同。
例如，假设用一个名为text的字符串向量存放文本文件中的数据，其中的元素或者是一句话或者是一个用于表示段落分隔的空字符串。如果要输出text中第一段的内容，可以利用迭代器写一个循环令其遍历text，直到遇到空字符串的元素为止：
//依次输出text的每一行直到遇到第一个空行为止
std::vector<std::string> text = {
"hello",
"",
"world",
};
for(auto it = text.cbegin(); it != text.cend() && !it->empty(); ++it) {
std::cout << *it << std::endl;
}
我们首先初始化it令其指向text的第一个元素，循环重复执行直至处理完了text的所有元素或者发现某个元素为空。
每次迭代时只要发现还有元素并且尚未遇到空元素，就输出当前正在处理的元素。
值得注意的是，因为循环从头到尾只是读取text的元素而未向其中写值，所以使用了cbegin和cend来控制整个迭代过程。
迭代器失效
曾经介绍过，虽然vector对象可以动态地增长，但是也会有一些副作用。已知的一个限制是不能在范围for循环中向vector对象添加元素。另外一个限制是任何一种可能改变vector对象容量的操作，比如push_back，都会使该vector对象的迭代器失效。
//注意下面逻辑错误，在for循环中push元素导致死循环
std::vector<int> numbers = {1, 2, 3, 4, 5};
for(auto i = 0; i < numbers.size(); ++i) {
numbers.push_back(i);
}
也不要在循环中执行push操作
//注意下面逻辑错误，在for循环中push元素导致迭代器失效,也会导致死循环
for(auto it = numbers.begin(); it != numbers.end(); ++it) {
numbers.push_back(1);
}
同样我们执行删除操作也要注意，我们可以通过vector的erase操作删除迭代器指向的元素
//删除第一个元素
numbers.erase(numbers.begin() );
erase会返回删除元素的下一个元素的迭代器
面试题
vector
std::vector<int> numbers = {1, 2, 3, 4, 5};
//循环遍历,并删除其中奇数
for(auto it = numbers.begin(); it != numbers.end(); ) {
// 删除奇数
if(*it % 2 != 0){
it = numbers.erase(it);
continue;
}
++it;
}
for(auto num : numbers) {
std::cout << num << " ";
}
std::cout << std::endl;
迭代器运算
迭代器的递增运算令迭代器每次移动一个元素，所有的标准库容器都有支持递增运算的迭代器。
类似的，也能用==和！=对任意标准库类型的两个有效迭代器，进行比较。
string和vector的迭代器提供了更多额外的运算符，一方面可使得迭代器的每次移动跨过多个元素，另外也支持迭代器进行关系运算。所有这些运算被称作迭代器运算（iterator arithmetic）。
迭代器的算术运算
可以令迭代器和一个整数值相加（或相减），其返回值是向前（或向后）移动了若干个位置的迭代器。
执行这样的操作时，结果迭代器或者指示原vector对象（或string对象）内的一个元素，或者指示原vector对象（或string对象）尾元素的下一位置。
举个例子，下面的代码得到一个迭代器，它指向某vector对象中间位置的元素：
std::vector<int> numbers = {1, 2, 3, 4, 5};
//中间位置的迭代器
auto mid = numbers.begin() + numbers.size()/2;
//判断迭代器是否有效
if(mid != numbers.end()){
std::cout << *mid << std::endl;
}else{
std::cout << "mid is end" << std::endl;
}
mid指向了中间的元素3
使用迭代器运算
使用迭代器运算的一个经典算法是二分搜索。二分搜索从有序序列中寻找某个给定的值。
二分搜索从序列中间的位置开始搜索，如果中间位置的元素正好就是要找的元素，搜索完成；
如果不是，假如该元素小于要找的元素，则在序列的后半部分继续搜素；
假如该元素大于要找的元素，则在序列的前半部分继续搜索。
在缩小的范围中计算一个新的中间元素并重复之前的过程，直至最终找到目标或者没有元素可供继续搜索。
下面的程序使用迭代器完成了二分搜索：
std::vector<int> numbers = {1, 2, 3, 4, 5};
//二分查找4所在的迭代器为止
auto beg = numbers.begin(), end = numbers.end();
auto mid = beg + (end - beg) / 2;
//二分查找
while(mid != end && *mid != 4){
//4在mid的右边
if(*mid < 4){
beg = mid + 1;
}else{ //4在mid的左边
end = mid;
}
mid = beg + (end - beg) / 2;
}
if(mid != end){
std::cout << "4 is found" << std::endl;
}else{
std::cout << "4 is not found" << std::endl;
}
程序的一开始定义了三个迭代器：beg指向搜索范围内的第一个元素、end指向尾元素的下一位置、mid指向中间的那个元素。
初始状态下，搜索范围是名为numbers的vector<int>的全部范围。
循环部分先检查搜索范围是否为空，如果mid和end的当前值相等，说明已经找遍了所有元素。
此时条件不满足，循环终止。当搜索范围不为空时，可知mid指向了某个元素，检查该元素是否就是我们所要搜索的，如果是，也终止循环。
当进入到循环体内部后，程序通过某种规则移动beg或者end来缩小搜索的范围。
如果mid所指的元素比要找的元素4大，可推测若numbers含有4，则必出现在mid所指元素的前面。此时，可以忽略mid后面的元素不再查找，并把mid赋给end即可。
另一种情况，如果＊mid比4小，则要找的元素必出现在mid所指元素的后面。此时，通过令beg指向mid的下一个位置即可改变搜索范围。因为已经验证过mid不是我们要找的对象，所以在接下来的搜索中不必考虑它。
循环过程终止时，mid或者等于end或者指向要找的元素。如果mid等于end，说明numbers中没有我们要找的元素。
练习题
1 相邻元素的和
题目描述：
编写一个程序，读取一组整数到一个 std::vector 中，并打印每对相邻元素的和。例如，给定输入 1 2 3 4，输出应为 3 5 7。
代码示例：
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
int num;
std::cout << "请输入一组整数（以 -1 结束）: ";
while (std::cin >> num && num != -1) {
numbers.push_back(num);
}
std::cout << "相邻元素的和: ";
for (auto it = numbers.begin(); it + 1 != numbers.end(); ++it) {
std::cout << (*it + *(it + 1)) << " ";
}
std::cout << std::endl;
return 0;
}
答案：
- 输入示例：
1 2 3 4 -1 - 输出示例：
相邻元素的和: 3 5 7
2 反向打印
描述： 编写一个程序，从用户输入一组整数到一个 std::vector 中，然后使用迭代器反向打印这些元素。
代码：
#include <iostream>
#include <vector>
int main() {
std::vector<int> numbers;
int input;
std::cout << "请输入一组整数（输入-1结束输入）：\n";
while (std::cin >> input && input != -1) {
numbers.push_back(input);
}
std::cout << "反向打印结果：";
for (std::vector<int>::reverse_iterator it = numbers.rbegin(); it != numbers.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
示例输入：
1 2 3 4 5 -1
示例输出：
反向打印结果：5 4 3 2 1
3 合并两个 vector
描述： 编写一个程序，创建两个 std::vector，从用户输入填充它们。使用迭代器将这两个 vector 合并为一个新 vector。
代码：
#include <iostream>
#include <vector>
int main() {
std::vector<int> vector1, vector2, mergedVector;
int input;
std::cout << "请输入第一个向量的整数（输入-1结束输入）：\n";
while (std::cin >> input && input != -1) {
vector1.push_back(input);
}
std::cout << "请输入第二个向量的整数（输入-1结束输入）：\n";
while (std::cin >> input && input != -1) {
vector2.push_back(input);
}
// 合并两个向量
mergedVector.insert(mergedVector.end(), vector1.begin(), vector1.end());
mergedVector.insert(mergedVector.end(), vector2.begin(), vector2.end());
std::cout << "合并后的向量结果：";
for (std::vector<int>::iterator it = mergedVector.begin(); it != mergedVector.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
示例输入：
1 2 3 -1
4 5 6 -1
示例输出：
合并后的向量结果：1 2 3 4 5 6