STL之traits编程技法

迭代器概念与traits编程技巧

迭代器：

STL的中心思想在于：将数据容器和算法分开，彼此独立设计，最后再以一贴胶着剂将他们撮合在一起。这边是迭代器的功能。

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最重要的便是内容提领和成员访问，因此迭代器最主要的编程工作就是对operator*和operator->进行重载工作。关于这一点C++标注程序库有一个auto_ptr可供我们参考，auto_ptr源代码在<memory>中。简单的设计一个迭代器例子如下：

template<typename T>
class List
{
public:
	void insert_front(T value);
	void insert_end(T value);
	void display(ostream& os = 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; }

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

	ListIter 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; }
};

迭代器相应型别

如果算法中有必要声明一个变量，以“迭代器所指对象的型别”为型别，如何是好？

解决办法：利用function template的参数推导机制。

例如：

template<class I, class T>
void func_impl(I iter, T t)
{
	T tmp;	//这里解决了问题。T就是迭代器所指之物的型别，本例为int
	//....这里做原本func()应该做的全部工作
}；

template <class I>
inline void func(I iter)
{
	func_impl(iter, *iter);		//func的工作全部移往func_impl
}
int main()
{
	int i;
	func(&i);
	return 0;
}

这里在fucn_impl中推导出了型别T。T是迭代器多只对象的型别，但最常用的相应型别有5种。然而并非任何情况下任何一种相应型别都可以利用参数推到机制来取得。

Traits编程技法-------------STL源代码门钥

迭代器所指对象的型别，称为该迭代器的value type。上述的参数推到机制虽然可用于value type，却非全面可用：万一value type必须用于函数的传回值，就束手无策了，毕竟函数的“template参数推导机制”推到的只是参数，无法推导函数的返回值型别。声明内嵌型别似乎可以解决这个问题，如下：

template<class T>
struct MyIter{
	typedef T value_type;	//内嵌型别声明(nested type)
	T* ptr;
	MyIter(T* p=0):ptr(p){}
	T& operator*() const {return *ptr;}
	//....
};

template<class I>
typename I::value_type	//这整一行是func的返回值型别
func(I ite)
{ return *ite;}

MyIter<int> ite(new int(8));
cout << func(itr);	//输出：8

注意,func()的返回型别必须机上关键词typename，因为T是一个template参数，typename的用意在告诉编译器这是一个型别，如此编译器才能顺利通过编译，否则编译器对T一无所悉。

如果STL接受原声指着作为一种迭代器，但我们无法为原生指针定义内嵌型别。所以上面的做法还不够。可以用template partial specialization解决这个问题。

首先我们需要知道以下知识：

template<typename T>
class C{...};	//这个泛华版本允许T为任何型别

template<typename T>	
class C<T*>{...};	//这个偏特化版本只适用于"T为原声指针"情况

现在我们可以针对”迭代器的template 参数为原生指针”的情况，设计偏特化的迭代器。

下面这个class template专门用来萃取迭代器的特性，而value type正式迭代器的特性之一：

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

而针对原生指针的偏特化版本如下：

template<class T>
struct iterator_traits<T*>{	//偏特化版----迭代器是个原生指针
	typedef typename T value_type;
};
初次之外，还定义了一个针对”指向常数对象的指针”的偏特化版本，如下：
template<class T>
struct iterator_traits<const T*>{	//迭代器是个pointer-to-const
	typedef typename T value_type;
};

现在不论面对的是迭代器MyIter这种类型，或是原生指针int*等或是const int*等,都可以通过traits取出正确的value type。

根据经验，最常用到的迭代器相应型别有五种：value type,differencetype,pointer,reference,iterator catagoly。

上面提到的五种相应类型，前四种实现差不多，此处不在累赘。对于第五种，详述如下：

Iterator_category

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

Input Iterator:这种迭代器所指对象，不允许外界改变。只读

Output Iterator:只写

Forward Iterator：允许“写入型”算法在此种迭代器所形成的的区间上进行读写操作。

Bidirectional Iterator:可双向移动

Random Access Iterator:前四种迭代器都只供应一部分指针算术能力（operator++,第四种再加上operator--）,第五种则涵盖所有指针算术能力，包括p+n,p-n,p[n],p1-p2,p1<p2。

这些迭代器关系如下：

下面五个classes，代表迭代器类型：

struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag:public input_iterator_tag{};
struct bidirectional_iterator_tag:public forward_iterator_tag{};
struct radom_access_iterator_tag:public bidirectional_iterator_tag{};

以advance为例来讲解第五种相应型别Iterator_category：

template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n, input_iterator_tag)
{
	//单项，逐一前进
	while(n--) ++i;
};

template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n, forwrard_iterator_tag)
{
	//淡村的调用
	_advance(i,n, input_iterator_tag());
};

template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n, bidirectional_iterator_tag)
{
	//双向，逐一前进
	if(n>=0)
		while(n--) ++i;
	else
		while(n++) --i;
};

template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n, random_access_iterator_tag)
{
	//双向，跳跃前进
	i += n;
};

template<class InpuIterator, class Distance>
inline void advance(InputIterator& i, Distance n)
{
	_advance(i,n,iterator_traits<InputIterator>::iterator_category);
}

template<class I>
struct iterator_traits
{
	...//其他特性萃取
	typedef typename I::iterator_traits iterator_category;
};

//针对原生指针而设计的偏特化版本
//原生指针是一种random_access_iterator_tag
template<class T>
struct iterator_traits<T*>
{
	typedef random_access_iterator_tag iterator_category;
};
//针对pointer-to-const而设计的偏特化版本
template<class T>
struct iterator_traits<const T*>
{
	typedef random_access_iterator_tag iterator_category;
};

从上面advance函数实现的代码中可以看出Iterator_category运用了traits技法。

以下是iterator的traits实现源代码：

// 五种迭代器类型
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

template <class T, class Distance> struct input_iterator {
  typedef input_iterator_tag iterator_category;
  typedef T                  value_type;
  typedef Distance          difference_type;
  typedef T*                 pointer;
  typedef T&                 reference;
};

struct output_iterator {
  typedef output_iterator_tag iterator_category;
  typedef void                value_type;
  typedef void                difference_type;
  typedef void                pointer;
  typedef void                reference;
};

template <class T, class Distance> struct forward_iterator {
  typedef forward_iterator_tag iterator_category;
  typedef T                    value_type;
  typedef Distance             difference_type;
  typedef T*                   pointer;
  typedef T&                   reference;
};


template <class T, class Distance> struct bidirectional_iterator {
  typedef bidirectional_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T, class Distance> struct random_access_iterator {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

#ifdef __STL_USE_NAMESPACES
//为避免写代码时挂一漏万，自行开发的迭代器最好继承自下面这个std::iterator
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
struct iterator {
  typedef Category  iterator_category;
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
};
#endif /* __STL_USE_NAMESPACES */

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
//”榨汁机”traits
template <class Iterator>
struct iterator_traits {
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_type;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};
//针对原生指针(native pointer)而设计traits偏特化版
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;
};

//针对原生之pointer-to-const而设计traits偏特化版
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;
};

//这个函数可以很方便地决定某个迭代器的类型（category）
template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

//这个函数可以很方便地决定某个迭代器的类型distance type
template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&) {
  return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

//这个函数可以很方便地决定某个迭代器的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);

除此之外，SGI STL还设定了_type_traits的负责萃取型别(type)的特性。此处我们所关注的型别特性是指：这个型别是否具备non-trivial defaltctor?是否具备non-trivial copyctor?是否具备non-trivialassignment operator?是否具备non-trivial dtor?如果答案是否定的，我们在对这个型别进行构造、析构、拷贝、赋值等操作时，就可以采用最有效率的措施，而采用内存直接处理操作如malloc()、memcpy()等等，获得最高效率。