[数据结构与算法]（六）iterator简介、迭代器萃取器、偏特化的应用

Iterator需要遵循的原则

• 迭代器是容器与算法之间的桥梁，算法的最基本特性是它要求其迭代器提供哪些操作
• 算法问迭代器问题，如iterator_catgory是什么，以便于采取最佳的操作方式。
• iterator必需提供的5种assocaited types，后面这两种从来都没有被使用过
  • iterator_category迭代器的分类
    • 输入迭代器：只读，不写；单遍扫描，只能递增
    • 输出迭代器：只写，不读；单遍扫描，只能递增
    • 前向迭代器：可读写；多遍扫描，只能递增
    • 双向迭代器：可读写；多遍扫描，可递增递减
    • 随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算
  • value_type容器中元素的类型
  • difference_type两个迭代器之间的距离应该用什么类型表现，如用unsigned int
  • pointer
  • reference

//G2.9
template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef bidirectional_iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef ptrdiff_t difference_type;
	...
}

---------------------迭代器回答------------------------
---------------------算法提问--------------------------
template<typename I>
inline void
algorithm(I first, I last)
{
...
	I::iterator_category;
	I::pointer;
	I::reference;
	I::value_type;
	I::diference_type;
...
};

• 迭代器是一种泛化的指针，指针是一种退化的迭代器
• 如果算法的参数传入的并不是迭代器而是指针，要如何处理呢
• ->加萃取器
  • 这个机器必需能区分它所收到的是class型的指针（迭代器）还是一般的指针，返回不同的答案。
  • ->用偏特化实现这种效果

解决计算机问题的尚方宝剑：加一个中介层
汉语里的尚方宝剑对应英语中的sliver bullet

• 萃取器的实现如下
  • 如果传入的是指针，则返回第二个版本
  • 传入的是常量指针，则返回第三个版本
• 为什么版本三返回值不加const
  • value_type是用来声明变量的，而声明一个无法被赋值的变量没什么用，所以迭代器的value_type不能加上const

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 T>
struct iterator_traits<const T*>
	typedef T value_type;//注意是T不是const T
};
------------------当需要知道I的value_type时-----------------
template<typename I, ...>
void algorithm(...){
	typename iterator_traits<I>::value_type v1;
}

• 完整的iterator_traits

template<class T>
struct iterator_traits{
	typedef typename I::iterator_category iterstor_category;
	typedef typename I::value_type value_type;
	typedef typename I::difference_type difference_type;
	typedef typename I::pointer pointer;
	typedef typename I::reference 
};
//偏特化，普通指针
template<class T>
struct iterator_traits<T*>{
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef ptrdiff_t difference_type;
	typedef T* pointer;
	typedef T& reference;
};
//偏特化，常量指针
template<class T>
struct iterator_traits<const T*>{
	typedef random_access_iterator_tag iterator_category;
	typedef T value_type;
	typedef ptrdiff_t difference_type;
	typedef const T* pointer;
	typedef const T& reference;
};

萃取的分类

• type traits
• iterator traits
• char traits
• allocator traits
• pointer traits
• array traits