C++ 迭代器 iterator 详解

 3.4 迭代器介绍

        迭代器 功能：访问容器对象的元素。

所有标准库容器都可以使用迭代器，其中只有少数几种才同时支持下标运算符。严格来说，string对象不属于容器类型，但是string支持很多与容器类型类似的操作。

迭代器分为有效和无效，类似于指针。

• 有效的迭代器：指向某个元素，或者指向容器中尾元素的下一个位置；
• 无效的迭代器：除上述的其他所有情况。

3.4.1 使用迭代器

        和指针不同，获取迭代器不是使用取地址符，有迭代器的类型同时拥有返回迭代器的成员。例如，这些类型都有 begin 和 end 的成员

        begin 成员：负责返回指向第一个元素(或第一个字符)的迭代器。

auto b = v.begin() , e = v.end();

         end 成员：负责返回指向容器（或string对象）“尾元素的下一个位置”的迭代器，该迭代器指向的容器是一个本不存在的“尾后”元素。

        所以end成员返回的迭代器常被称作为 尾后迭代器 或 尾迭代器。特殊情况当容器是空时，begin成员和end成员返回的是同一个迭代器，都是尾后迭代器。

迭代器运算符

        与指针相同，迭代器也能通过解引用迭代器来获取它所指示的元素，执行解应用的迭代器必须合法并且指示着某个元素。尝试解引用一个非法迭代器或者尾后迭代器都是未被定义的行为。

 下列程序，利用下标运算符进行大小写转换。

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

         s.begin()!=s.end() 检查s是否为空，根据上面我们提到，当容器为空时begin成员和end成员返回的是同一个迭代器。所以当返回结果一样，说明s为空；如果返回结果不一样，说明s不为空，此时s中至少包含一个字符。

        在if内部声明了一个迭代器变量it并且把begin的返回值赋值给它，此时就得到了指示s中第一个字符的迭代器。最后用toupper转换成大写。

输出结果：Some string

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

        迭代器使用递增运算符（++）来从一个元素移动到下一个元素。和整数的递增类似，在整数递增上的"+1"，在迭代器的递增中就意味着“向前移动一个位置”。

        因为end返回的迭代器并不实际指示某个元素，所以不能对其进行递增或解引用的操作。因为我们上文提到过（end 成员：负责返回指向容器（或string对象）“尾元素的下一个位置”的迭代器，该迭代器指向的容器是一个本不存在的“尾后”元素）。

        现在我们使用迭代器把第一个单词全部大写。

#include
#include
using namespace std;
int main()
{
        string s{"some string"};
        for(auto it=s.begin();it!=s.end()&&!isspace(*it);++it)
                *it = toupper(*it);
        printf("%s \n",s.c_str());
        return 0;
}

第一步：创建一个string类型的s。

第二步：创建迭代器it作为s的开始，条件it到结尾就停止，it不能为空，执行完成++it，it指向下一个字符。

第三步：字符大写。

泛式编程

        之前我们说到过，只有string和vector等少数标准库类型有下标运算符。并且大部分标准库类型没有定义<运算符,但是所有标准库容器的迭代器都定义了==和!=。所以我们只要养成使用迭代器和!=的习惯，就不用在意使用的是哪种容器类型。

迭代器类型

        我们不需要知道string和vector的size_type成员到底是什么类型。我们把拥有迭代器的标准库类型，使用iterator和const_iterator来表示迭代器类型；

        例如：每个容器类定义了一个名为iterator的类型，而iterator类型指出迭代器概念所规定的一套操作。这就叫迭代器类型。

vector::iterator it;                    // it 能读写vector的元素

string::iterator it2;                           // it2 能读写string对象中的元素

vector::const_iterator it3;       //  it3只能读元素，不能写元素

string::const_iterator it4;                //  it4只能读字符，不能写字符

begin和end运算符

        begin和end返回的具体类型由对象是否为常量决定，如果对象是常量，begin和end返回const_iterator；如果对象不是常量，返回iterator；

vector v;

const vector cv;

auto it1 = v.begin();        // it1的类型是vector::iterator

auto it2 = cv.begin();      // it2的类型是vector::const_iterator

         有时候这些默认操作不是我们所想要的，我们只需要对象只读不进行操作，最好是使用常量类型(比如const_iterator)，为了方便操作在C++11 中引入了两个新的函数cbegin()和cend()；

        auto it3 = v.cbegin()；//it3的类型是vector::const_iterator

        类似于begin和end，上述两个新函数也分别返回第一个元素和最后一个元素的下一位置的迭代器。不同的是，无论是否是常量，返回的都是const_iterator。

结合解引用和成员访问操作

        解引用迭代器可获得迭代器所指对象，如果该对象的类型恰好是类，就有可能进一步访问它的成员。例如一个vector对象，想要检查其元素是否为空，令it是该vector对象的迭代器，只需要检查it所指字符串是否为空就可以了。

(*it).empty();

         *it的外的()是必须写的，如果不写就会先执行点运算符，再进行解引用。正确的是先对it解引用，然后用解引用的结果再执行点运算符。

(*it).empty();        //解引用it，然后调用结果对象的empty成员

*it.empty();           //错误，试图访问it的名为empty的成员，当时it是个迭代器没有empty成员

        为了简化上述表达式，C++语言定义了 箭头运算符(->)。箭头运算符把解引用和成员访问两个操作结合在一起。也就是说 it->men 和 (*it).mem是等价的。

        例如，用一个名为text的字符创向量存放文本文件中的数据，其中的元素或者一句话或一个用于表示段落分隔的空字符串。如果要输出text中第一段的内容，可以利用迭代器写一个循环令其遍历text，直到遇到空字符串的元素为止；

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

某些对vector对象的操作会使迭代器失效

        虽然vector对象可以动态地增长，但有一些副作用。

已知的限制是

        1.不能再范围for循环中向vector对象添加元素。

        2.人呢刚和一种可能改变vector对象容量的操作，例如push_back，都会使该vector对象的迭代器失效。

Tips：但凡使用了迭代器循环体，都不要向迭代器所属的容器添加元素。

3.4.2 迭代器运算

        string和vector的迭代器提供了更多额外的运算符，一方面可以使得迭代器的每次移动跨过多个元素，另外也支持迭代器进行关系运算。所有这些运算被称为迭代器运算。

迭代器的算数运算

        可以令迭代器和一个整数值相加或相减，其返回值是向前或向后移动了若干个位置的迭代器。执行这样的操作时，迭代器可能会发生两种情况：

        1.迭代器指示原vector对象(或string对象)内的一个函数；

        2.迭代器指示原vector对象(或stirng对象)尾元素的下一位置。

#include
using namespace std;
const int N=100010;
int n;
int q[N];
void quick(int q[],int l,int r)
{
	if(l>=r) return;
	int i=l-1,j=r+1,x=q[l+r>>1];
	while(i
	{
		do i++;while(q[i]
		do j--;while(q[j]>x);
		if(iswap(q[i],q[j]);
	}
	quick(q,l,j),quick(q,j+1,r);
}

        这里使用快排来解释迭代器的算数运算符。 

auto mid = vi.begin()+vi.size()/2;//计算得到最接近vi中间元素的一个迭代器； 

        在快排的代码中，l和r分别类似vi.begin()和vi.size()，快排中的x和mid是同一个作用。

(l+r)>>2简单理解为(l+r)/2; 建议把圆括号都写上，防止出错，也方便查看。

        x是q中最接近q中间数组的一个元素。

        mid是vi中最接近vi中间元素的一个迭代器。

如果q有20个数组，那么x就是q[10];mid在vi中也是一个道理；

        对于string或者vector的迭代器来说，除了判断是否相等，还能使用关系运算符(<,<=,>,>=)对其进行比较，参与比较的迭代器必须合法并且指向同一个容器的元素(或尾元素的下一个位置)。

例如，假设it和mid是同一个vector对象的两个迭代器，可以用下面的代码来比较他们的位置。

if(it

        相应快排的代码中，do...while语句的条件，比较q[i]和x，对i进行调整；比较q[j]和x,对j进行对比。

if(l>=r) return; 就类比于x.begin() != x.end();

        当头尾相碰时，循环结束。

        只要两个迭代器指向的是同一个容器中的元素或者尾元素的下一位置，就能将其相减,所得结果是两个迭代器的距离。所谓距离指的是右侧的迭代器向前移动多少位置就能追上左侧的迭代器,其类型是名为 difference_type 的带符号整型数。string和vector都定义了 difference_type, 因为这个距离可正可负,所以difference_type 是带符号类型的。

使用迭代器运算

        使用迭代器运算的一个经典算法是二分搜索（上述的快排就是一个典型的二分搜索）。二分搜索从有序序列中寻找某个给定的值。二分搜索从序列中间的位置开始搜索,如果中间位置的元素正好就是要找的元素,搜索完成;如果不是,假如该元素小于要找的元素,则在序列的后半部分继续搜素;假如该元素大于要找的元素，则在序列的前半部分继续搜索。在缩小的范围中计算一个新的中间元素并重复之前的过程,直至最终找到目标或者没有元素可供继续搜索。

//text 必须有序，beg和end表示搜索范围
auto beg = text.begin(),end = test.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.beg指向搜索范围内的第一个元素；

        2.end指向尾元素的下一个位置；

        3.mid指向中间的那个元素。

搜索范围是名为text的vector的全部范围。

        循环部分先检查搜索范围是否为空。

若mid==end，则已经找遍所有元素，条件不满足，循环终止。

当搜索范围不为空时，可知mid指向某个元素，检查该元素是否满足要求，如果是，则终止循环。

        当进入循环体内部后，程序通过规则去移动beg或者end来缩小搜索范围。

        如果mid所指元素>目标元素sought，则推测出若text含有sought，必出现在mid所指元素的前面。此时，可以忽略mid后面的元素比出现在mid所指元素的后面,并且把mid赋值给end就可以了。

        另一种情况，如果*mid

        循环结束时，mid或者等于end或者指向目标元素sought。如果mid等于end，说明text中没有我们要找的元素。

更详细，更全面的介绍，垂阅此文章（该文章篇幅较长，推荐使用电脑阅读）。

C++ Primer 第三章字符串，向量和数组_WWester的博客-CSDN博客