7 迭代器和好用的新for循环

什么是迭代器?
迭代器是一个通用的概念，并不是一个特定类型而是一组对类型的要求，最基本的要求是从一个端点出发，下一步，下一步地到达另一个端点。

容器对begin()和end()成员函数提出了要求，假设前者返回的类型是I，后者返回的类型是S，这些要求是
I对象支持*解引用操作，解引用得到容器内的某个元素对象
I对象那支持++,指向下一个对象
I对象可以和I或S对象进行相等==比较，判断是否遍历到了特定位置(I==S说明已经遍历到了容器末尾)

c++17之前，begin()和end()返回的类型I和S必须是相同的。c++17开始，I和S可以是不同的类型，这带来了更大的灵活性和更多的优化可能性。
这两个类型之间是需要允许比较操作的。后面有个例子，你可以先看一下：
https://github.com/adah1972/geek_time_cpp/blob/master/29/test05_null_sentinel.cpp
要点是，这种情况下，比较的时候可以不是比较迭代器本身，而是做一下更复杂的操作。如检查文件是否结束，读取的内容是否为 NUL（istream_line_reader
例子里的情况），甚至比较永远失败（无限循环的情况）。

迭代器的基本要求:
可以被拷贝构造、拷贝赋值和析构
支持解引用运算符
支持*前置++运算符

下面讲下迭代器类型

输入迭代器(input iterator)
==比较，!=
支持前置和后置++，支持*解引用(输入迭代器在一次成功后 会自动++移动到下一个位置，所以不支持多次解引用)即每个被遍历位置上只能读取一次
不需要支持赋值保存迭代器来重新遍历容器
对输入迭代器的要求就是可以单次访问某个元素，并可以读取这个元素的内容
输入迭代器只能向前，被用来读取容器中的元素，但是不能使用输入迭代器修改容器对象中元素的值(输入是相对程序而言的)

输出迭代器(output iterator)
==比较，!=
支持前置和后置++，支持*，->解引用(输出迭代器在一次成功后 会自动++移动到下一个位置，所以不支持多次解引用)即每个被遍历位置上只能被写一次
不需要支持赋值保存迭代器来重新遍历容器
可以使用输出迭代器向容器中写入元素 it = xx(ok)(修改元素的值)，但不能读取容器中的元素。对输出迭代器的要求就是可以单次访问某个元素，并可以读取这个元素的内容
*通常用来将数据从一个位置拷贝到另一个位置

前向迭代器(forward iterator)
==比较，!= ,=赋值
支持前置和后置++，支持*解引用,解引用后不会自动移到下个位置 即允许多次访问同一个元素
支持赋值保存迭代器来重新遍历容器
可读取容器中的数据 只能向前

双向迭代器(bidirectional iterator)
==比较，!= ,=赋值
支持前置和后置++，支持*解引用,解引用后不会自动移到下个位置 即允许多次访问同一个元素
并且支持前置和后置—,回到前一个对象。即既可以正向遍历，也可以反向遍历
支持赋值保存迭代器来重新遍历容器
可读取容器中的数据

随机访问迭代器(random -acess iterator)
==比较，!=, =赋值 +,-,+=,-=这些跳跃式地移动迭代器 支持[]下标访问 支持大小比较<,>,<=,>=
支持前置和后置++，支持*解引用,解引用后不会自动移到下个位置 即允许多次访问同一个元素
并且支持前置和后置—,回到前一个对象。即既可以正向遍历，也可以反向遍历
支持赋值保存迭代器来重新遍历容器
可以读取容器中的数据

连续迭代器(contiguous iterator) c++20
在随机访问迭代器基础上
满足使(a + n) 等价于 (std::addressof(a) + n)——*即保证迭代器指向的对象在内存里为连续存放的

需要注意指针可以满足上面所有迭代器的要求，所以指针也是迭代器(vector中的迭代器很多就直接用的是指针)。上述的这些迭代器都是都对象。

常用迭代器
最常用的迭代器就是容器的iterator类型，以我们学过的顺序容器为例，他们都定义了嵌套的iterator类型和const_iterator类型。 一般iterator可写入，const_iterator不可写入，这些迭代器都被定义为输入迭代器或其派生类型

vector::iterator和array::iterator可以满足到连续迭代器(及其子类的功能)
deque::iterator可以满足到随机访问迭代器(及其子类的功能 deque的内存本身就是只有部分是连续的 所以不需要满足到连续迭代器)
list::iterator可以满足到双向迭代器(及其子类的功能 链表无法快速跳转+-n 只能一个一个节点地向下遍历)
forward_list::iterator 可以满足到前向迭代器(及其子类的功能 单向链表无法反向—遍历)

常见的输出迭代器是back_inserter的返回类型back_inserter_iterator，用它可以很方便地在容器尾部进行插入操作，另一个常见的输出迭代器是ostream_iterator方便我们把容器内容拷贝到一个输出流

输出迭代器通常用来将数据从一个位置拷贝到另一个位置

#include <algorithm>  // std::copy
#include <iterator>   // std::back_inserter
#include <vector>     // std::vector
using namespace std;
vector<int> v1{1, 2, 3, 4, 5};
vector<int> v2;
copy(v1.begin(), v1.end(),
back_inserter(v2));
//v2 {1,2,3,4,5}
#include <iostream>  // std::cout
copy(v2.begin(), v2.end(),
ostream_iterator<int>(cout, " "));

//屏幕输出 1 2 3 4 5

使用输入行迭代器

实现一个输入迭代器，把输入流(istream)的内容一行行读进来，配上c++11引入的基于范围的for循环语法，可以把遍历输入流的代码以一种自然非过程的方式写出来 如下

for (const string& line :
istream_line_reader(is)) {
    // 示例循环体中仅进行简单输出
    cout << line << endl;
}
//如果用传统的方法来写则如下
string line;
for (;;) {
    getline(is, line);
    if (!is) {
    break;
    }
    cout << line << endl;
}

用迭代器实现只用了1行，而传统写法用了5行

先讲一下基于范围的for循环这个语法糖，对提高代码的可读性非常重要

for (const string& line :
istream_line_reader(is)) {
    // 示例循环体中仅进行简单输出
    cout << line << endl;
}

将上面这个迭代器循环展开来讲

auto&& r = istream_line_reader(is);//获取范围表达式对象 如果返回的是左值则auto&&万能引用推导为左值引用，如果返回的是右值万能引用推到为右值引用,因为临时对象绑定到引用上其生命周期会被延长的机制，这个对象在循环结束后才会被销毁
//生成遍历指定范围的迭代器
auto it = r.begin();
auto end = r.end();
for (; it != end; ++it) {
    const string& line = *it;
    cout << line << endl;
}

c++11新的好用的 范围循环的特性如下 直接可以省去多句语句
这一句话
const string& line :istream_line_reader(is)
等同于
1 auto&& r = istream_line_reader(is); — istream_line_reader(is)叫范围表达式，生成的是一个范围而不是迭代器
原获取冒号候变表达式的结果，并隐式产生一个引用在，整个循环期间都有效，如果返回的是一个临时变量，因为临时对象绑定到引用上其生命周期会被延长的机制，这个对象在循环结束后才会被销毁
2 自动生成编列指定范围的迭代器
auto it = r.begin();
auto end = r.end();

其实不一定是调用r的begin和end成员函数，具体规则是
对于C数组(是数组而不是退化为指针的情况)，编译器会自动生成指向数组头尾的指针(而不是调用begin和end )
对于迭范围表达式返回对象有begin()和end()成员的情况，编译器会像我们写的这种情况一样，调用begin和end得到首尾迭代器
不属于上述两种情况，编译器会尝试在范围表达式返回对象所在的命名空间寻找可以用于这个范围对象的begin和end函数，并尝试调用begin(r)和end(r),找不到的化就失败报错

3 自动生成根据冒号左边的声明const string&和 it内容来进行初始化
const string& line = it;

下面讲一下如何实现这个范围表达式返回对象类

class istream_line_reader {
public:
    // 仿照容器的写法，讲迭代器定义为范围对象类的嵌套类
    class iterator {  // 实现 InputIterator
        public:
        //c++里对迭代器iterator有固定的类型要求 如下
        //下面这5个类型是迭代器必须定义的 其他泛型c++代码会用到下面5个类型，之前标准库定义了一个可以继承的模板类std::iterator来产生这些类型定义，但是这个类目前以及被废弃 所以需要自己写
        typedef ptrdiff_t   difference_type;//difference_type代表迭代器之间距离的类型，定义为ptrdiff_t(指针间差值的类型)是标准做法
        typedef string  value_type;//value_type是迭代器指向对象的值类型 按照需求定义为string,表示迭代器内容*it为string
        typedef const value_type* pointer;// pointer是迭代器指向对象的指针类型，这里定义为value_type的常指针(因为我们做的是输入迭代器 不希望对象内容被修改)
        typedef const value_type& reference;// reference是迭代器指向对象的引用类型，这里定义为value_type的常引用(因为我们做的是输入迭代器 不希望对象内容被修改)
        typedef input_iterator_tag
        iterator_category;
        // iterator_category是指我们这个迭代器的类型 是输入迭代器还是输出迭代器还是... 我们做的是输入迭代器 所以定义为input_iterator_tag
        …
    };
…
};

输入迭代器每个元素每次只能访问一次(只能读一次的迭代器 在后自动++到下个元素)，输入迭代器有个特殊的麻烦，到底让负责读取还是++负责读取。这里采用常见也较为简单的做法，让++负责读取，*负责返回读取的内容(这个做法会有些副作用 我们目前的用法ok)。这样的话，这个迭代器需要一个数据成员指向输入流，一个数据成员来存放读取的结果

在讲设计前这里补充一下对operator->()的重载，c++对operator->的返回值做了强制规定必须返回一个裸指针 或者 返回同样重载了运算符->的对象的引用或值

对于形如point->mem的表达式来说
point是类的对象，这个类重载了->。 point->mem == point.operator->() ->mem

point.operator->()可以返回一个指针，则就和普通指针一样操作，
返回的这个指针->mem == (*返回指针).mem。

point.operator->()可以返回一个重载了运算符->的对象的引用或值，则会重复调用这个返回对象的operator->()，直到某次调用operator->()返回了一个指针而不是一个对象，将这个指针作为最后的返回。

除了上面两种情况，代码都将发生错误

下面是一个完整的istream_line_reader类设计

#include <string>
#include <assert.h>             // assert
#include <stddef.h>             // ptrdiff_t/size_t
#include <stdio.h>              // file streams
#include <iterator>             // std::input_iterator_tag
class istream_line_reader {
public:
// 仿照容器的写法，讲迭代器定义为范围对象类的嵌套类
    class iterator {  // 实现 InputIterator
    public:
        //c++里对迭代器iterator有固定的类型要求 如下
        //下面这5个类型是迭代器必须定义的 其他泛型c++代码会用到下面5个类型，之前标准库定义了一个可以继承的模板类std::iterator来产生这些类型定义，但是这个类目前以及被废弃 所以需要自己写
        typedef ptrdiff_t difference_type;//difference_type代表迭代器之间距离的类型，定义为ptrdiff_t(指针间差值的类型)是标准做法
        typedef std::string value_type;//value_type是迭代器指向对象的值类型 按照需求定义为string,表示迭代器内容*it为string
        typedef const value_type *pointer;// pointer是迭代器指向对象的指针类型，这里定义为value_type的常指针(因为我们做的是输入迭代器 不希望对象内容被修改)
        typedef const value_type &reference;// reference是迭代器指向对象的引用类型，这里定义为value_type的常引用(因为我们做的是输入迭代器 不希望对象内容被修改)
        typedef std::input_iterator_tag
        iterator_category;
        // iterator_category是指我们这个迭代器的类型 是输入迭代器还是输出迭代器还是... 我们做的是输入迭代器 所以定义为input_iterator_tag
        //默认构造
        iterator() noexcept
        : stream_(nullptr) 
        {}
        /*
        ++负责读取，*负责返回读取的内容!!!!
        */
        //参数构造 传入一个输入流对象 根据传入的输入流来设置stream_
        explicit iterator(std::istream& is)
        : stream_(&is)
        {
        //因为是用++取内容的
        //所以再构造的时候直接++取一次内容 存到line里
        //相当于
        // for (; it != end; ++it) {
        //     const string& line = *it;
        //     cout << line << endl;
        // }
        //第一次进这个循环 是不会调用++it再取内容的 而是直接*it取string的内容
        //这构造里的++就是为了第一次将字符串内容存在line里 供第一次*it直接取内容
            ++*this;
        }
        //解引用直接返回字符串内容
        reference operator*() const noexcept
        {
            return line_;
        }
        //看笔记里的上面的解释
        pointer operator->() const noexcept
        {
            return &line_;
        }
        //使用++来读取输入流的内容
        iterator& operator++()
        {
        //前置++ 先++读内容 再返回迭代器本身istream的getline istream类中也有一个getline不要混淆
        getline(*stream_, line_);//这个getline是string的getline
        //getline会改变传入的流对象的内容,并将提取出来的字符串对象放在第二个参数中 当流读取完毕后*stream为null
        //getline会改变传入的流对象的内容 是不可逆的，读了多少就没多少
        //此时的迭代器就和end()一样了 其中的流对象都为null
        // istream& getline ( istream &is , string &str , char delim );//delim为分隔符
        // istream& getline ( istream& , string& );
            if (!*stream_) {
            stream_ = nullptr;
            }
            return *this;
        }
        //使用++来读取输入流的内容
        //后置++ 使用前置++和拷贝构造来实现
        iterator operator++(int)
        {
            //后置++ 返回+之前的对象 再++
            iterator temp(*this);//保存+之前的迭代器
            ++*this;//++迭代器
            return temp;//返回+之前的迭代器
        }
        //通常用于判断迭代器是否到达尾部了 比如begin()迭代器和end()迭代器==时说明已经遍历到迭代器尾部了
        //从从istream_line_reader的begin和end函数可知 begin或者其他迭代器的流对象一定不是null 只有end迭代器的流对象为null
        bool operator==(const iterator& rhs)
        const noexcept
        {
            return stream_ == rhs.stream_;
        }
        bool operator!=(const iterator& rhs)
        const noexcept
        {
            return !operator==(rhs);
        }
        // int main()
        // {
        //     ifstream ifs{"test.cpp"};//可以读自己代码的内容
        //     istream_line_reader reader{ifs};
        //     auto begin = reader.begin();//begin()会传入istream对象来构造一个iterator对象,并调用一次++读istream一次内容存在line里
        //     for (auto it = reader.begin();
        //又调用了一次begin() 但因为之前的istream对象因为已经读过一次内容(++)，那么第一行内容已经给读走存在line中
        //这里又调用一次begin()在构造中又调用一次++,将下一行的内容覆盖line,但上次的line我们并没有保存其内容，导致上次的line内容丢失
        //         it != reader.end(); ++it) {
        //         cout << *it << '\n';
        //     }
        // }
     private:
        std::istream* stream_;
        std::string line_;    
    };
istream_line_reader() noexcept
: stream_(nullptr) 
{}
explicit istream_line_reader(
istream& is) noexcept
: stream_(&is) 
{}
iterator begin()//begein负责构造一个真正有意义的迭代器
{
    return iterator(*stream_);
}
iterator end() const noexcept //end返回一个默认构造的迭代器
{
    return iterator();
}
private:
    istream* stream_;
};