為什麼標準庫里要有traits？

我們先回憶一下，標準庫提供的演算法的一些特征：

• 參數一般包括iterator。

• 要根據iterator的種類，和iterator包裝的元素的類型等信息，來決定使用最優化的演算法。

  比如如果是vector的iterator，那麼就可以使用+，-操作；

  如果是list的iterator，那麼就不可以使用+，-操作。

所以，演算法必須知道一些關於iterator的信息。

有一些容器對應的iterator是個類，所以在這個類里，定義瞭如下的信息：

template<typename T>
struct __list_iterator { 
  typedef bidirectional_iterator_tag     iterator_category;
  typedef T                              value_type;
  typedef T*                             pointer;
  typedef T&                             reference;
  typedef ptrdiff_t                      difference_type;

有了上面定義的定義，演算法就能夠知道iterator的信息了，演算法就可以正常工作了。到這裡位置貌似沒有traits什麼事，

但是，vector，array的iterator並不是類，而是c++里內置的指針，當把內置指針當參數傳遞給演算法後，演算法無法得知iterator里定義的iterator_category，value_type，difference_type等信息，演算法就無法工作。怎麼辦？

加一個中間層，也就是創建一個iterator_traits類，它包裝了iterator，並使用模板局部特化技術，來解決上面的問題。

traits是萃取機的意思，也就是萃取iterator里的信息，並給到演算法。

traits技術：

//使用iterator提供的信息
template<typename Iterator>
struct iterator_traits
{
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_typep;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

//由於無法使用iterator的信息，所以traits自己提供了。
//局部特化，c++內置指針。
template<typename 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;
};

//由於無法使用iterator的信息，所以traits自己提供了。
//局部特化，c++內置指針。
template<typename T>
struct iterator_traits<const T *>
{
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;//註意這裡不是const T;如果是const T，演算法拿到這個類型，用這個類型定義變數後，卻無法改變其值，那就沒有作用了，所以是T。
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

演算法向iterator_traits類要它需要的信息，iterator_traits再向iterator要，如果要到了，就使用；如果沒有要到就使用iterator_traits提供的。

演算法舉例：list類的size方法。

size_type size() const {
  size_type result = 0;
  distance(begin(), end(), result);
  return result;
  //return distance(begin(), end());    
}

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 InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, 
                       input_iterator_tag)
{
  while (first != last) { ++first; ++n; }
}

template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last, 
                       Distance& n, random_access_iterator_tag)
{
  n += last - first;
}

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;//--①
  return category();
}

template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n)
{
  __distance(first, last, n, iterator_category(first));
}

代碼解說：在①處，演算法向iterator_traits要iterator_category的信息，如果iterator能提供，就使用iterator里的iterator_category，如果iterator不能提供，就使用iterator_traits里的iterator_category。得到iterator_category後，就可以在編譯階段確定調用哪一個__distance方法了。

註意：是在編譯階段就可以確定，比在運行階段確定調用哪個__distance方法的效率要高。

下麵代碼是沒有trais技術，是在運行階段才能確定調用哪個__distance方法。

template <class Iterator>
void distance(Iterator& i){
  if(is_random_access_iterator(i)){
    __distance1();
  }  
  if(is_bidirectional_iterator(i)){
    __distance2();
  }
}

標準庫的iterator_traits類，定義在stl_iterator.h文件里。