迭代器与traits技法

STL的中心思想在于：将容器（containers）和算法（algorithm）分开，彼此单独设计，最后通过一帖胶着剂将他们撮合到一起。这个胶着剂就是迭代器。?

3.1.迭代器是一种 smart pointer

迭代器是一种行为类似于指针的东西，而指针最重要的操作就是内容提领 (引用，reference) 和成员访问 (member access) ，因此迭代器最重要的编程工作就是对 operator* 和 operator-> 进行重载 (overloading) 。

//以下为auto_ptr，智能指针的重载函数，用于参考。
T* operator->() const {
	return ptr;
}

T& operator*() const {
	return *ptr;
}

由此引出的一个例子：List、ListItem、ListIter

可以发现为了实现这个迭代器，暴露了许多List的细节，如果不是为了ListIter，ListItem应该完全封装隐藏起来才对。也就是说，设计出ListIter必须对List的细节有足够的了解，因此直接把对ListIter的实现交给List的作者就好了，这也是为什么每个STL容器都有提供有专属迭代器的原因。

3.2.迭代器相应型别（associated types）

什么是相应型别？迭代器所指的型别就是其中一种相应型别。假设算法中有必要声明一个变量，这个变量的型别是迭代器所指的型别，那应该怎么办？比如Iterator<T>，我们，创建了一个 Iterator<int*>，或Iterator<double*>，那么如何通过 T 声明一个 int 或一个 double ?

解决方法：使用 function template 的参数推导出（argument deducation）机制。

template<class I,class T>
void func_impl(I iter,T type){//接收到func传入的int*和int，所以这里I、T自动推导为int*和int
	T tmp;	//于是就得到了iter所指的类型，这里为int
}

tmeplate<class I>
inline
void func(I iter){	//接收到int*，所以I自动推导为int*类型
	func_impl(iter,*iter);	//向func_impl传入 int* 和 int
}

int main(){
	int i;
	func(&i);	//将int*传入func
}

迭代器的相应型别 (associated type) 并非只有这一种，常用的有五种，获取的方法也更复杂——traits技法。

3.3.traits编程技法——STL源代码门钥:?

traits (意为特性) 所扮演的对象为”特性萃取器“，这里的迭代器特性是指类的相应型别 (associated type) 。

对于非指针类型，我们可以直接通过以下的方式得到其五种类型，可以不用traits：

//标准器提供的迭代器类型，为了防止漏写，自己实现迭代器最好继承自 std::iterator<>
template <class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
struct iterator { // base type for iterator classes
	using iterator_category = _Category;
	using value_type = _Ty;
	using difference_type = _Diff;
	using pointer = _Pointer;
	using reference = _Reference;
};

而对于指针类型，则没办法通过上面的类型，直接获得对应的类型，因此需要借助traits技法：

template <class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
struct iterator { // base type for iterator classes
	using iterator_category = _Category;
	using value_type = _Ty;
	using difference_type = _Diff;
	using pointer = _Pointer;
	using reference = _Reference;
};

//非指针类型的traits
template<class Iterator>
struct iterator_traits {
	using iterator_category = typename Iterator::iterator_category;
	using value_type = typename Iterator::value_type;
	using difference_type = typename Iterator::difference_type;
	using pointer = typename Iterator::pointer;
	using reference = typename Iterator::reference;
};

//针对原生指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;
	using difference_type = std::ptrdiff_t;
	using pointer = T*;
	using reference = T&;
};

//针对原生const指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<const T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;	//注意这里是非const的，否则传回去一个const类型的无法定义也没用
	using difference_type = std::ptrdiff_t;
	using pointer = const T*;
	using reference = const T&;
};

所以通过加了一层中间层 iterator_traits ，既可以获得非指针类型的相应型别，也可以获得指针类型的相应型别：

• 对于非原生指针 (native pointer) 类型，会调用非指针的traits。
• 对于const和非const的指针则会调用指针的偏特化版本的traits。

通过traits技法，我们可以得到以下五种类型，并且用他们声明变量。

最常用的五种相应型别：

• value_type
• difference_value
• iterator_category
• reference
• pointer

3.3.1.value_type——迭代器所指类型的型别

迭代器所指对象的型别。

3.3.2.differnce_type——两个迭代器之间的距离

用来表示两个迭代器之间的距离，也可以表示容器的最大容量。

3.3.3.iterator_category——迭代器类型

• input_iterator_tag：只读（read only）
• output_iterator_tag：唯写（write only）
• forward_iterator_tag：允许 ”写入型“ 算法，在此种迭代器形成的区间上进行读写操作。
• bidirectional_iterator_tag：可双向移动。
• random_access_iterator_tag：涵盖所有指针的算数能力。

// from <iterator> iterator的category(意为类型)
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

template <class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
struct iterator { // base type for iterator classes
    using iterator_category = _Category;
    using value_type        = _Ty;
    using difference_type   = _Diff;
    using pointer           = _Pointer;
    using reference         = _Reference;
};

3.3.4.reference/pointer——引用/指针

//traits
template<class I>
struct iterator_tarits{
    using reference = typename I::reference;
	using pointer = typename I::pointer;
}

//原生指针的偏特化版本traits
template<class T>
struct iterator_traits<T*>{
    using reference = T&;
    using pointer = T*;
}

//原生指针 point-to-const 的偏特化版本traits
template<class T>
struct iterator_traits<const T*>{
    using const reference = T&;
    using const pointer = T*;
}

3.4.std::iterator的保证

任何迭代器都应该提供5个内嵌相应型别，以利于traits萃取，否则可能无法与其他STL组件顺利搭配。

//五种类型
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

//标准器提供的迭代器类型，为了防止漏写，自己实现迭代器最好继承自 std::iterator<>
template <class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
struct iterator { // base type for iterator classes
	using iterator_category = _Category;
	using value_type = _Ty;
	using difference_type = _Diff;
	using pointer = _Pointer;
	using reference = _Reference;
};

//非原生指针类型的iterator_traits
template<class Iterator>
struct iterator_traits {
	using iterator_category = typename Iterator::iterator_category;
	using value_type = typename Iterator::value_type;
	using difference_type = typename Iterator::difference_type;
	using pointer = typename Iterator::pointer;
	using reference = typename Iterator::reference;
};

//针对原生指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;
	using difference_type = std::ptrdiff_t;
	using pointer = T*;
	using reference = T&;
};

//针对原生const指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<const T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;//const T* 的value_type也是T，而不是const T
	using difference_type = std::ptrdiff_t;
	using pointer = const T*;
	using reference = const T&;
};

3.5.iterator完整源码重列

//五种类型
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : input_iterator_tag {};
struct bidirectional_iterator_tag : forward_iterator_tag {};
struct random_access_iterator_tag : bidirectional_iterator_tag {};

//标准器提供的迭代器类型，为了防止漏写，自己实现迭代器最好继承自 std::iterator<>
template <class _Category, class _Ty, class _Diff = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
struct iterator { // base type for iterator classes
	using iterator_category = _Category;
	using value_type = _Ty;
	using difference_type = _Diff;
	using pointer = _Pointer;
	using reference = _Reference;
};

//非原生指针类型的iterator_traits
template<class Iterator>
struct iterator_traits {
	using iterator_category = typename Iterator::iterator_category;
	using value_type = typename Iterator::value_type;
	using difference_type = typename Iterator::difference_type;
	using pointer = typename Iterator::pointer;
	using reference = typename Iterator::reference;
};

//针对原生指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;
	using difference_type = std::ptrdiff_t;
	using pointer = T*;
	using reference = T&;
};

//针对原生const指针版本而设计的traits偏特版本
template<class T>
struct iterator_traits<const T*> {
	using iterator_category = std::random_access_iterator_tag;
	using value_type = T;//const T* 的value_type也是T，而不是const T
	using difference_type = std::ptrdiff_t;
	using pointer = const T*;
	using reference = const T&;
};

//获取Iterator的category
template<class Iterator>
inline typename iterator_traits<Iterator>::iterator_category 
iterator_category(const Iterator&)
{
	using category = typename iterator_traits<Iterator>::iterator_category;
	return category();
}

//获取Iterator的distance_type
template<class Iterator>
inline typename iterator_traits<Iterator>::distance_type* 
distance_type(const Iterator&)
{
	return static_cast<typename iterator_traits<Iterator>::distance_type*>(0);
}

//获取Iterator的value_type
template<class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&)
{
	return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

//整组的distance函数
template<class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first, InputIterator last,std::input_iterator_tag)
{
	typename iterator_traits<InputIterator>::difference_type n = 0;
	while (first != last) {
		first++;
		n++;
	}
	return n;
}

template<class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first, RandomAccessIterator last, std::random_access_iterator_tag)
{
	return last - first;
}

template<class Iterator>
inline typename iterator_traits<Iterator>::difference_type
distance(Iterator first, Iterator last)
{
    //利用iterator_traits得到iterator的类型，根据不同iterator调用不同_distance函数
	using category = typename iterator_traits<Iterator>::iterator_category;
	return _distance(first, last, category());
}

//整组的advance函数
//input_iterator_tag版本_advance
template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n,std::input_iterator_tag) 
{
	while (n--)i++;
}

//bidirectional_iterator_tag版本_advance
template<class BidirectionalIterator, class Distance>
inline void 
_advance(BidirectionalIterator& i, Distance n, std::bidirectional_iterator_tag) 
{
	if (n >= 0) {
		while (n--)i++;
	}
	else {
		while (n++)i--;
	}
}

//random_access_iterator_tag版本_advance
template<class RandomAccessIterator, class Distance>
inline void 
_advance(RandomAccessIterator& i, Distance n, std::random_access_iterator_tag) 
{
	i += n;
}

template<class Iterator,class Distance>
inline void 
advance(Iterator& i, Distance n)
{
    //使用iterator_traits萃取出iterator的类型，调用对应的_advance函数
	_advance(i, n, typename iterator_traits<Iterator>::iterator_category());
}

本栏目推荐文章
• MacOS - XCode 8.0报 'tr1/type_traits' file not found
• 29. 干货系列从零用Rust编写正反向代理，异步回调(async trait)的使用
• rust程序设计（4）关于 trait ｜ impl 相关的概念和疑问
• 【MMD】MMD三渲二的终极解决方案msToonCoordinator丨核心概念丨赛璐璐丨技法丨资料
• 20_rust的Trait
• 快学会这个技能-.NET API拦截技法
• 迭代器与traits技法
• rust_trait个人理解
• STL(8) 迭代器设计原则和traits
• 7.简单说一下traits技法

技法 traits技法traits 技法 技法 技能net api 技法scope_guard工具scope mstooncoordinator技法mmd终极 trait traits rust_trait 笔记traits type_traits