C++ Primer第三章④

C++ Primer

第三章字符串，向量和数组

迭代器介绍

前面我们介绍了可以使用下标运算符来访问string对象的字符和vector对象的元素，这部分我们来介绍一种更通用的机制，迭代器。为什么要在下标运算符之外再搞出个迭代器呢？因为所有的标准库容器都可以使用迭代器，但其中只有少数几种才同时支持下标运算，
总之，迭代器更普遍，更吊。

使用迭代器

比如我们要输出vector中所有的元素

vector<string> str = {"a", "b", "c"};
for(auto it = str.begin(); it != str.end(); ++it)
{
    cout << *it << endl;
}

我们来分析一下这段代码，开始是列表初始化一个vector<string>对象，关键语句在for循环中，先让it指向str的首元素，当它不等于str.end()时，输出它，并++，其中begin返回指向第一个元素的迭代器，注意它返回的是迭代器，不是元素本身，所以在访问它的时候，比如下面输出它，要加一个解引用迭代器*，end返回容器最后一个元素的下一个位置，也就是说，该迭代器指示的是容器中一个本不存在的尾后元素，虽然没什么实际含义，但是方便我们写循环啊。++it使得it后移一位，指向下一个元素。

迭代器类型

就像不知道string和vector的size_type成员到底是什么类型一样，我们也不知道（而且无须知道，对，就是这么）能不能有auto之外的定义方式呢？有的，如下：

vector<int>::iterator it; //it能读写vector<int>的元素
vector<int>::const_iterator is; //is只能读vector<int>的元素

一般我们说迭代器这个名词，有三种不同的含义，在不同语境下你会知道它什么意思的：一是迭代器概念本身，二是容器定义的迭代器类型，三是某个迭代器对象。

begin和end运算符

vector<int> v;
const vector<int> cv;
auto it1 = v.begin(); //it1的类型是vector<int>::iterator
auto it2 = cv.begin(); //it2的类型和it1不一样哦，是vector<int>::const_iterator

为了便于专门得到const_iterator（为什么要专门得到它呢，因为这样通过迭代器就只能访问而不能修改了，相当于实现了只读，比较安全），C++11开始引入了两个新函数：

auto it3 = v.cbegin();
auto it4 = v.cend();
//不管v是不是const的，二者都是const_iterator

下面我们来写个小程序：假设用一个名为text的字符串向量存放文本数据，输出第一段内容，可以用迭代器写一个循环遍历text，直到遇到空字符串为止：

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

大家有疑惑的应该是那个类似箭头的符号->，其实这个也就是程序员偷懒的方法，it->empty()等价于(*it).empty()，先对迭代器it解引用得到对象本身，再去调用对象的empty函数，当然你可以直接理解为it指向的对象是不是空，知其所以然就好。

接下来的程序厉害了，算是我们写到现在第一个实用的程序，二分查找，不知道二分查找的点我,text是一个从小到大排好序的容器：

//text必须是有序的，我们要找的是target
auto beg = text.cbegin(), end = text.cend();
auto mid = (end + beg)/2; //中间点
while(mid != end && *mid != target)
{
    if(target < *mid) //我们要找的元素是否在前半部分
    {
        end = mid; //如果是，则忽略后半部分
    }
    else //我们要找的元素在后半部分
    {
        beg = mid + 1; //忽略前半部分
    }
    mid = (end + beg)/2; //更新中间点
}

萌新们好好看看这个程序，会有所收获的。