《STL源码剖析》读书笔记

迭代器的设计

1. 迭代器iterator模式在《Design Patterns》中是这么定义的：

提供一直方法，使之能够依序巡防某个聚合物所含的各个元素，而又无线暴露该聚合物的
内部表述方式。

2. 获取迭代器所指对象的型别

template <class I, class T>
void func_impl(I iter, T t)
{
    T tmp;
}

template <class I>
inline
void func(I iter) {
 func_impl(iter, *iter)
}

int main() {
    int i;
    func(&i);
}

这里利用function template的参数推导机制获取迭代器的相应型别。

3. Traits 技巧

由于function template推导的是模板参数，无法推导函数的返回值型别、 所以用 声明内嵌型别的方式

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

template <class I>
tpyename I::value_type
func(I ite) {
    return *ite;
}

MyIter<int> ite(new int(8));
cout << func(ite); // print: 8

又由于内嵌型别只能用于class type，对于原生指针又无法支持。所以需要用到 template partial specialization模板偏特化来对原生指针做支持

利用了偏特化的方式我们提取迭代器value type就可以这么写：

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

template <class T>
struct iterator_traits<T*> { //偏特化版本，迭代器是原生指针
    typedef T value_type;
}

//同样的，对const int *，提取int
//即：对const T*,我们提取类型为T
template <class T>
struct iterator_traits<const T*> {
    typedef T value_type;
}

4. 迭代器分类

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

• Input Iterator: 所指对象只读。支持++操作
• Output Iterator: Write Only.支持++操作
• Forward Iterator: 允许写入。支持++操作
• Bidirectional Iterator: 可双向移动。
• Random Access Iterator:

利用重载函数来对同一个算法的不同类型迭代器做不同的操作，定义相应的五种迭代器结构. 在traits里加入一条iterator_category.

template <class I>
struct iterator_traits {
    ...
    typedef typename I::iterator_category iterator_category;
}
//还需要对原生指针进行偏特化处理


//在算法中就这样使用，来激发函数重载机制(编译时期).
template <class I, class Distance>
inline void advance(I& i, Distance n) {
    __advance(i, n, iterator_traits<I>::iterator_category());//做对应的操作
}

5. stl::iterator

STL为我们提供了一个iterator class我们的迭代器继承它就能符合stl的标准了。

template <class Item>
struct ListIter : public std::iterator<std::forward_iterator_tag, Item> { ... };