Iterator（迭代器）

提供一种方法，能够依序访问某个容器的各个元素，而又无需暴露该聚合物的内部表述方式。迭代器是一种行为类似指针的对象，即迭代器最重要的编程工作就是对operator*和opeator->进行重载。

C++标准程序库中有一个auto_ptr类包装原生指针，以免内存协泄露。

auto_ptr的实现

template<class T>
class auto_ptr {
    public:
      explicit auto_ptr(T *p = 0):pointee(p) {}
      template<class U>
      auto_ptr(auto_ptr<U>& rhs):pointee(rhs.release()) {}   //只能一个指针指向一块内存，rhs返回指向地址给this，将自己的指向置为0
      ~auto_ptr() {
          delete pointee;
      }

      template<class U>   //member template是为了父类指针可以指向子类对象
      auto_ptr<T>& operator=(auto_ptr<U>& rhs){   
          if(this != &rhs){  
              reset(rhs.release());   //通过调用rhs的release函数，将指向U对象的指针从rhs中释放，并返回该指针。然后，将该指针交叉给this的reset函数，并由this接管该资源的所有权
          }
          return *this;
      }
      T& operator*() const{
          return *pointee;
      }
      T* operator->() const {
          return pointee;
      }
      T* get() const {
          return pointee;
      }
    private:
      T* pointee;
}

模拟List和List中的iterator

template<typename T>
class List{         //链表
    public:
    void insert_front(T value);
    void insert_end(T value);
    void display(std::ostream& os = std::cout) const;
    private:
        ListItem<T>* _end;    //尾节点
        ListItem<T>* _front;   //头节点
        long _size;
};

template<typename T>
class ListItem{    //链表中的每个节点定义
  public:
    T value() const{
        return _value;
    }
    ListItem* next() const {
        return _next;
    }
  private:
    T _value;
    ListItem* _next;     //单向链表
};

template<class Item>
struct ListIter{
    Item* ptr;
    ListIter(Item* p = 0):ptr(p){}

    Item& operator*() const { return *ptr; }
    Item* operator->() const { return ptr; }

    ListIte& operator++(){
        ptr = ptr->next();
        return *this;
    }
    ListIte& operator++(int){
        ListIter tmp = *this;
        ++*this;
        return tmp;
    }

    bool operator==(const ListIter& i) const{
        return ptr == i.ptr;
    }
    bool operator!=(const ListIter& i) const{
        return ptr != i.ptr;
    }
};

迭代器相应型别

在算法中运用迭代器时，很可能会用到相应型别。动用RTTI性质中的typeid(),获得的也只是型别名称，不能拿来做变量声明之用。我们可以利用函数模板的参数推导机制来推测。但是函数的模板参数推导机制推而导之的只能是参数，无法推导函数的返回值型别。

函数的模板参数推导机制推而导之的只能是参数，无法推导函数的返回值型别

template<class T>
struct MyIter{
    T* ptr;
    MyIter(T* p = 0):ptr(p) {}
    T& operator*() const {
        return *ptr;
    }
};

template<class T, class T2>
T2 func(T iter){
    return *iter;
}

MyIter<int> ite(new int(8));
cout << func(ite);           //1.编译错误，并没有出现T2的信息，无法推导
cout << func<MyIter, int>(ite);   //2.正常运行，制定了T2的类型，但是这需要客户端主动输入T2的类型，提供iter的型别

//使用内嵌型别声明
template<class T>
struct MyIter{
    typedef T value_type;   //使用内嵌型别声明
    T* ptr;
    MyIter(T* p = 0):ptr(p) {}
    T& operator*() const {
        return *ptr;
    }
};
template<class T>
typename T::value_type func(T iter){       //关键词typename的用意在于告诉编译器这是一个型别
    return *iter;
}

我们可以设置一个类型萃取机，提取每个迭代器的型别

template<class I>
struct iterator_traits{
    typedef typename I::value_type value_type;
};

为什么要多加一个萃取机呢？因为有些迭代器是原生指针，不是类，就需要对萃取机设计模板偏特化，萃取原生指针的型别。

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

当然，若要这个特性萃取机能够有效运作，每个迭代器必须遵循约定，自行以内嵌型别定义的方式定义出相应性别。这是一个约定。

最常用到的迭代器相应型别有五种

template<class I>
struct iterator_traits{
  typedef typename I::value_type value_type;
  typedef typename I::iterator_category iterator_category;
  typedef typename I::difference_type difference_type;
  typedef typename I::pointer pointer;
  typedef typename I::reference reference;
};

• value_type是指迭代器所指对象的型别。
• difference type表示两个迭代器之间的距离。
• reference type指迭代器所指元素的引用
• pointer type指向迭代器所指元素
• iterator_category表示迭代器的类型

iterator_category

struct input_iterator_tag {};  //输入迭代器类型，只能读取，且单步向前迭代元素，不允许修改由该类迭代器引用的元素
struct output_iterator_tag {};   //输出迭代器类型，与输入迭代器相似，不同的是该类迭代器对元素只有写的权力
struct forward_iterator_tag : public input_iterator_tag{};  //前向迭代器类型，具有读写权力，拥有和input_iterator的所有特性
struct bidirectional_iterator_tag : public forward_iterator_tag{};  //双向迭代器类型，在forward_iterator的基础上提供了单步向后迭代元素的能力
struct random_acess_iterator_tag : public bidirectional_iterator_tag{}; //随机迭代器类型，拥有上述迭代器的所有特性，还可以像指针一样进行算数计算

1. 为什么iterator_category有多个种类？因为STL容器有着不同的特性，有些容器中元素是离散的，只能一个一个取值；有些容器元素存储是连续的，可以直接跳跃取值。
2. 为什么进行继承？因为迭代器的功能是分层的，越高级的迭代器就拥有之前迭代器的所有能力，用继承非常符合。重要的是，在算法实现时，可以使用最低层的input_iterator_tag作为形参，因为实参中的迭代器是一个体系的，所以都可以满足该算法。算法中也可以进行细分，根据萃取机萃取的类型进行更细致，更有效率的划分。

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type __distance(InputIterator first, InputIterator last, input_iterator_tag){
    iterator_traits<InputIterator>::difference_type n = 0;
    while(first != last){
        first++;
        n++;
    }
    return n;
}

template<class RandomAccessIterator>
inline iterator_traits<RandomAccessIterator>::difference_type __distance(RandomAccessIterator first, RandomAccessIterator last, random_acess_iterator_tag){
    iterator_traits<RandomAccessIterator>::difference_type n = 0;
    n = last - first;
    return n;
}

template<class InputIterator>
inline iterator_traits<InputIterator>::difference_type __distance(InputIterator first, InputIterator last){
    return __distance(first, last, iterator_traits<InputIterator>::iterator_category());   //萃取机判断迭代器的类型，决定使用相应的重载函数__distance，根据不同的类型进行不同的操作
}

STL提供了一个iterator class ,如果每个新设计的迭代器都继承自它，就可以保证符合STL的需要。

template<class Category,
         class T,
         class Distance = ptrdiff_t,
         class Pointer = T*,
         class Reference = T&>
struct iterator{
  typedef T value_type;
  typedef Category iterator_category;
  typedef Distance difference_type;
  typedef Pointer pointer;
  typedef Reference reference;
};

iterator class不含任何成员，继承它不会招致任何额外负担。由于后三个参数都有默认值，新的迭代器只需提供两个参数即可。

设计适当的相应型别，是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍历自己。traits编程技法利用内嵌型别的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面的能力，弥补C++不为强型别语言的遗憾。