STL源码剖析第三章迭代器与 traits编程阅读笔记

重点在最下面，赶时间的小伙伴可以直接跳到最后

迭代器是设计模式之一，提供依序访问集合的统一方法
意思是对于数组、链表、或树，都能使用同样的方法来遍历，
原先链表可能是依次用next指针，树可能是right指针来访问
现在统一用iter++来遍历

这个对于通用算法 (无视容器类型) 实现可是意义重大，使得算法与容器分离，否则你可能同一个算法得写多个类似版本

迭代器的行为看起来很像智能指针，有类似指针的行为，先看一个简单的智能指针实现(忽略了很多)

template<class T>
class auto_ptr(){//已被废弃的智能指针
    T& operator*()const{
        return *pointer;
    }
    T* operator->(){//为什么?   ->  ==   (*).
        return pointer;
    }
private: 
    T *pointer;
};

类比它，我们实现一个List的迭代器，这是一个List

template<class T>
class List{//单链表
private:
    ListItem<T> *_front;
    ListItem<T> *_end;
};
template<class T>
class ListItem{
private:
    T value;
    ListItem<T> *next;
};

下面是其迭代器

//现在模仿auto_ptr给List实现一个iterator
template<class T>
class ListIterator{
public:
    T& operator*()const{
        return *pointer;
    }
    T* operator->(){//为什么   ->  ==   (*).
        return pointer;
    }
private:
        ListItem *pointer;
};

但是很多通用算法场景下需要迭代器指向的对象的类型
比如求容器中的元素最大值

template<class I>
max(I iter);

此时就很尴尬，幸好我们可以这样用nested_type救赎

template<class T>
class ListIterator{
public:
    typedef T value_type;//nested type!!!
    T& operator*()const{
        return *pointer;
    }
    T* operator->(){
        return pointer;
    }
private:
        ListItem *pointer;
};
template<class I>
I::value_type max(I iter);

但是还是有问题，当原始指针作为迭代器时，无法用这招，因为原始指针不是class
于是得用偏特化，即允许模板类与模板类的特殊版本共存，就是说
不举例子了，直接给出结果了

template<I>
class IterTrait{
    typedef I::value_type value_type;
};
template<T>
class IterTrait<T*>{//偏特化版本，如果迭代器是原始指针T*，则IterTrait::value 是T
    typedef T value_type;
};
//这俩可以共存，当遇迭代器时走上面，指针时走下面，这层萃取层对迭代器和原始指针的差异进行了一层封装

最后是迭代器的关联类型(5个)，即萃取需要获得的，算法需要

如果迭代器指向T或者是T*，其对应关联类型

difference_type:两个迭代器之间的距离的类型(这个不明白，但是觉得不重要所以忽略了)
value_type                T
referenct_type            &T
pointer_type              *T
iterator_category: 迭代器类型
    Input 只读
    Ouput 只写
    Forward 可读写
    Bidirectional 双向遍历
    Random Access  在双向基础上，允许使用iter+n

图片说明

重点:
1. 使用迭代器可以实现通用算法（无视容器差异，对容器进行遍历、修改）
2. 每个容器有自己专属的迭代器
3. nested_type可以获取迭代器所指向对象的具体类型
4. 偏特化可以实现模板类与模板类的特殊化实现共存
5. STL的traits技法 == nest_type + 原始指针的偏特化

原谅我实实在在对总结很缺乏耐心，所以笔记做的很乱，见谅，如果耽误了诸位的时间，90度鞠躬抱歉