迭代器

迭代器简介

迭代器（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的返回值类型，之后将对相关内容做更详细的介绍。

比较运算

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;

ANOTHR string

循环首先用s.begin的返回值来初始化it，意味着it指示的是s中的第一个字符（如果有的话）。

条件部分检查是否已到达s的尾部，如果尚未到达，则将it解引用的结果传入isspace函数检查是否遇到了空白。

每次迭代的最后，执行++it令迭代器前移一个位置以访问s的下一个字符。

循环体内部和上一个程序if语句内的最后一句话一样，先解引用it，然后将结果传入toupper函数得到该字母对应的大写形式，再把这个大写字母重新赋值给it所指示的字符

迭代器类型

就像不知道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;

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);
}

同样我们执行删除操作也要注意，我们可以通过vector的erase操作删除迭代器指向的元素

//删除第一个元素
numbers.erase(numbers.begin() );

erase会返回删除元素的下一个元素的迭代器

练习题

vector容器存储了一系列数字，在循环中遍历每一个元素，并且删除其中的奇数，要求循环结束，vector元素为偶数，要求时间复杂度o(n)

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;