STL中的traits技术

STL中有个函数advance，用来将某个迭代器移动某个给定距离：

template<typename IterT,typename DistT> void advance(IterT& iter, DistT d) { } 另外，我们知道，STL中有5中类型的迭代器：

input迭代器：只能向前移动，每次移动一步，并且只可读取其所指的东西；

output迭代器：只能向前移动，每次移动一步，并且只能涂写其所指的东西；

forward迭代器：只能向前移动，每次移动一步，并且可以读写其所指的东西；

Bidirectional迭代器：可以向前向后移动过，每次移动一步，可以读取所指的东西；

random access迭代器：可以向前向后移动过，每次移动n步，可以读取所指的东西；

对于这5类迭代器，C++标准库分别提供专属的卷标结构加以识别：

struct input_iterator_tag{}; struct outnput_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{}; 因此，从性能方面考虑，我们当然希望对random access迭代器特殊处理，所以：

template<typename IterT,typename DistT> void advance(IterT& iter, DistT d) { if (iter is random_access_iterator) { iter += d; } else { if (d > 0) { while (d--) ++iter; } else { while (d++) --iter; } } } 所以，我们必须有一种办法，知道迭代器的种类。下面是STL的做法：（以STL的list为例）

template<typename T> class list { public: class iterator { public: typedef bidirectional_iterator_tag iterator_category; ... }; ... }; template<typename T> class vector { public: class iterator { public: typedef random_access_iterator_tag iterator_category; ... }; ... }; 也就是在容器的class里表明它的迭代器属于哪个类型的迭代器！！！

所以我们可以通过vector<int>::iterator::iterator_category 知道vector<int>的迭代器类型

于是，我们可以用一个iterator_traits实现traits技术：

template<typename IterT> struct iterator_traits { typedef typename IterT::iterator_category iterator_category; ... }; 然后我们的advance函数就可以这样写：

template<typename IterT,typename DistT> void advance(IterT& iter, DistT d) { if (typeid(typename iterator_traits<IterT>::iterator_category) == typeid(random_access_iterator_tag)) { iter += d; } else (...) { ... } }但是，这份代码还是存在问题。IterT类型是在编译期间获知，所以iterator_traits<IterT>::iterator_category也可以在编译期间确定，但是if语句确是运行期才会核定。因此，我们应该把它都放到编译期。

我们可以这样做：

template<typename IterT,typename DistT> void doAdvance(IterT& iter, DistT d, random_access_iterator_tag) { iter += d; } template<typename IterT, typename DistT> void doAdvance(IterT& iter, DistT d, bidirectional_iterator_tag) { if (d > 0) { while (d--) ++iter; } else { while (d++) --iter; } } template<typename IterT, typename DistT> void doAdvance(IterT& iter, DistT d, input_iterator_tag) { if (d < 0) { throw ... } while (d--) ++iter; } 于是，我们的advance函数最终为：

template<typename IterT,typename DistT> void advance(IterT& iter, DistT d) { doAdvance(iter, d, typename iterator_traits<IterT>::iterator_category); }