首页 > 代码库 > STL源码剖析(迭代器)
STL源码剖析(迭代器)
在STL中，容器跟算法是分开设计的，算法是通过迭代器来对容器进行操作的。
在算法运用迭代器的时候，可能会用到其相应的型别，例如返回值为容器中元素的型别，又或者说根据迭代器的类型来选择更好的算法等等。
为了实现这一点，还有为了兼容内置型别的迭代器(vector迭代器直接使用原生pointer)，STL使用了traits技法，用于提取迭代器的特性(相应的型别)。
1.首先在iterator中typedef相应的型别
1 // 这是迭代器的基类 所有迭代器必须定义这5种型别 2 template<class Category, class T, class Distance = ptrdiff_t, 3 class Pointer = T*, class Reference = T&> 4 struct iterator { 5 typedef Category iterator_category; 6 typedef T value_type; 7 typedef Distance difference_type; 8 typedef Pointer pointer; 9 typedef Reference reference; 10 };
2.定义萃取器iter_traits
1 // 以迭代器为模板参数，用于萃取相应的型别 2 template <class Iterator> 3 struct iter_traits { 4 typedef typename Iterator::iterator_category iterator_category; 5 typedef typename Iterator::value_type value_type; 6 typedef typename Iterator::difference_type difference_type; 7 typedef typename Iterator::pointer pointer; 8 typedef typename Iterator::reference reference; 9 };
3.定义相应的偏特化版本(这就是为什么要使用iter_traits封装多一层)，因为内置型别的迭代器并不是class，不能定义相应的型别。
1 // 原生指针的偏特化版 2 template <class T> 3 struct iter_traits<T*> { 4 typedef typename random_access_iter_tag iterator_category; 5 typedef typename T value_type; 6 typedef typename ptrdiff_t difference_type; 7 typedef typename T* pointer; 8 typedef typename T& reference; 9 }; 10 11 // 原生const的偏特化版 12 template <class T> 13 struct iter_traits<const T*> { 14 typedef typename random_access_iter_tag iterator_category; 15 typedef typename T value_type; 16 typedef typename ptrdiff_t difference_type; 17 typedef typename const T* pointer; 18 typedef typename const T& reference; 19 };
4.5种迭代器类型，只是一个标志，用于根据萃取出来的iterator_category来选择相应的算法。
1 struct input_iter_tag {}; 2 struct output_iter_tag {}; 3 struct forward_iter_tag : public input_iter_tag {}; 4 struct bidirectional_iter_tag : public forward_iter_tag {}; 5 struct random_access_iter_tag : public bidirectional_iter_tag {};
下面是distance()的实现，展示了怎么使用traits萃取相应的型别。
1 // input迭代器只支持operator++ 2 template<class InputIterator> 3 inline typename iter_traits<InputIterator>::difference_type 4 __distance(InputIterator first, InputIterator last, input_iter_tag) 5 { 6 iter_traits<InputIterator>::difference_type n = 0; 7 while (first != last) 8 { 9 first++; 10 n++; 11 } 12 return n; 13 } 14 15 // random access迭代器支持迭代器之间的加减法 16 template<class RandomAccessIterator> 17 inline typename iter_traits<RandomAccessIterator>::difference_type 18 __distance(RandomAccessIterator first, RandomAccessIterator last, random_access_iter_tag) 19 { 20 return last - first; 21 } 22 23 // 根据迭代器的iterator_category来调用适合的版本 24 template<class Iterator> 25 inline typename iter_traits<Iterator>::difference_type 26 distance(Iterator first, Iterator last) 27 { 28 return __distance(first, last, iter_traits<Iterator>::iterator_category()); 29 }
STL的__type_traits也是使用traits技法，它可以萃取一个class是否有不重要的构造函数、是否为POD类型等等。
1 // __type_traits也是运用traits技术 2 struct __true_type {}; 3 struct __false_type {}; 4 5 template <class type> 6 struct __type_traits { 7 // 默认为false 可以实现自己的偏特化版本 8 // 内置类型的偏特化版本定义在stl_config.h中 都是__true_type 9 typedef __false_type has_trivial_default_constructor; 10 typedef __false_type has_trivial_copy_constructor; 11 typedef __false_type has_trivial_assignment_operator; 12 typedef __false_type has_trivial_destructor; 13 typedef __false_type is_POD_type; 14 };
自定义的类型可以定义相应的偏特化版本，例如定义is_POD_type为__true_type，STL会在元素析构的时候只进行内存回收，而不调用析构函数以用来提高效率。
STL源码剖析(迭代器)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。