C++——迭代器Iterator

Iterator简介

    迭代器是一个抽象的概念，其可以说是算法与容器之间的桥梁，迭代器提供一种方法，使之能够依存巡防某个聚合物（容器）所含的所有元素，而有无需暴露该聚合物的内部表达方式。

    迭代器也可以看成一个行为类似指针的对象，而指针的行为主要就是内容提领（*）和成员访问（->）

    根据移动特性和实施操作，迭代器分为五类：

1. Input Iterator：迭代器所指对象为只读
2. Output Iterator：迭代器所指对象为只写
3. Forward Iterator：迭代器可以执行读写操作(replace())
4. Bidirectional Iterator：迭代器可双向移动，如某些算法需要逆向遍历迭代器，可用次
5. Random Access Iterator：随机访问迭代器所指对象

    这五种迭代器分类从属关系由下图可见：

    迭代器的五种型别：

1. value_type:迭代器所指对象的类型
2. difference_type：用来表示两个迭代器之间的距离
3. reference_type：引用型别
4. pointer_type：指针型别
5. iterator_category：指明迭代器的分类（五种之一）

简单例子Iterator

#include <vector>
#include <list>
#include <iostream>
#include <algorithm>
#include <typeinfo>
using namespace std;
int main(int argc, char const *argv[])
{
    const int len=7;
    int a[len]={1,3,5,6,8,11,13};
    vector<int> vec(a,a+len);
    list<int> ls(a,a+len);
    vector<int>::iterator itr=find(vec.begin(),vec.end(),13);
    if(itr==vec.end()){
        cout<<"not find\n";
    }
    else{
        cout<<"find "<<*itr<<endl;
    }
    auto i=ls.begin();
    for(;i!=ls.end();i++){
        cout<<*i<<" ";
    }
    cout<<typeid(i).name()<<endl;
    return 0;
}

Trait

    trait称为“萃取器”，作用就是把Iterator的特性萃取出来，实现的方法就是相当于加了一个中间层（一个类模板）

template <typename T>
struct iterator_traits{
    typedef typename T::value_type value_type;
    ....
}

    除此之外，trait定义为一个类模板还有一个好处就是可以拥有特化的版本，针对原生指针和指向常量对象的指针，分别可以注册一个偏特化的版本，这样就可以使 int* 或者 const int*通过traits正确的萃取出我们期望的型别value_type

template <typename T>
struct iterator_traits<T*>{
    typedef T value_type;
}

template <typename T>
struct iterator_traits<const T*>{
    typedef T value_type;
}

     这里还需说明一点的就是typename的用法（详见effective c++ 条款42）。简述就是两个用法

1. 在模板定义里，表明其后的模板参数是类型参数（与class一样）
2. 在模板中标明“内嵌依赖类型”（内嵌指的是定义在类名中，依赖于一个模板参数，而又是一个类型名而不是变量），这种情况下一定要用typename。两个例外可以省略typename：①类模板定义中基类列表②类模板定义中初始化列表

type_traits

    iterator_traits是萃取出迭代器的特性，type_traits是萃取出型别的特性，当我们输入一个类型时，（无论是系统内置类型还是我们自己定义的类），都可以通过其看出型别的特性，特性指的是：在这个类中，是否（具备）默认构造函数重要吗？拷贝构造函数重要吗（是否具备）？拷贝赋值函数重要吗（是否具备）？析构函数重要吗（是否具备）？

#include <iostream>
#include <type_traits>
using namespace std;

template <typename T>
class myclass{
public:
    myclass(int k):val(k){ }
    ~myclass()=default;

private:
    T val;
};

int main(int argc, char const *argv[])
{
    cout<<"is_abstract\t"<<is_abstract<myclass<int>>::value<<endl;
    cout<<"is_class\t"<<is_class<myclass<int>>::value<<endl;
    cout<<"is_copy_cons\t"<<is_copy_constructible<myclass<int>>::value<<endl;
    cout<<"is_copy_ass\t"<<is_copy_assignable<myclass<int>>::value<<endl;
    cout<<"is_default_constructible\t"<<is_default_constructible<myclass<int>>::value<<endl;
    cout<<"is_trivially_constructible\t"<<is_trivially_constructible<myclass<int>>::value<<endl;
    return 0;
}

参考 《STL源码剖析》、《c++ primer》、《effective c++》