iterator必须提供5种associated types

1.iterator_category
2.value_type
3.diiference_type
4.pointer
5.reference

对于iterator_category来说，例如双向链表:

typedef bidirectional_iterator_tag iterator_category;

算法和迭代器的关系：

算法提问，迭代器回答

algorithm(I first,I end)
{
...I::iterator_categoryI::value_typeI::diiference_typeI::pointerI::reference
...
}

Traits 萃取机

由于iterator回答的是class中使用的typedef
而算法提问时，可能涉及到non_class iterators
此时就想要中间层：Traits
用于分离class iterators和non_class iterators
Traits：

template <class I> 

struct iterator_traits{typedef typename I::value_type value_type;
};

于是当需要知道I的value type时便可这么写：

void algorithm(...){typename iterator_traits <I>::value_type v1;
}

不同类型传递给萃取器：

value_type的主要目的是用来声明变量，而声明一个无法被赋值的变量没什么用，所以iterator（即便是constant iterator）的value type 不应该加上const。iterator若是const int*，其value_type应该是int而非const int。