浅谈对SGI-STL迭代器设计思想的理解 --10 May 2014
写这篇文章的目的,主要是想总结一下我看完SGI-STL的迭代器部分代码之后的感悟,说一说自己的理解,这里还是要感谢侯捷老师的«STL源码剖析»一书对我带来的启蒙和引发.另外,需要注明的是本篇涉及到的代码都是笔者自己实现的一套代码,和原生SGI代码相比在类命名等问题上有一些不同.
迭代器需要哪些特征?
我们要设计一个迭代器,那么我们先从迭代器的使用需求上来看迭代器需要哪些特征? 什么是特征?我们看一个例子就知道了.
STL的distance算法
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last);我们知道,distance算法是求两个迭代器的距离,那么我们可以想一下,由于这个是通用函数模板,输入的迭代器可以是vector容器的迭代器,也可以是list容器的迭代器,而我们根据vector和list的数据组织应该可以意识到这两个容器的迭代器的访问能力是不同的,一个是可以随机访问,即随便向前向后移动任意步数,但是另外一个只能每次向前移动一步(pos = pos->next). 基于这个不同,我们的distance算法实现就应该有所不同.那么怎么告知distance函数这个问题呢? 就需要迭代器具有某个特征来说明这点.
通过上面的例子,我们可以看到迭代器确实需要一些特征来作为区别,SGI-STL中的迭代器有五大特征,我们可以通过SGI的标准Iterator基类可以一看究竟,这里需要说一下,SGI中所有的迭代器都继承与这个基类.
template<typename Category, typename T,
typename Pointer = T*, typename Reference = T&,
typename Difference = ptrdiff_t>
struct iterator{
typedef Category iterator_category;
typedef T value_type;
typedef Pointer pointer_type;
typedef Reference reference_type;
typedef Difference difference_type;
};这里面唯一眼生的就是Category,这是标记迭代器的访问能力的一个特征,具体有五种类型分别定义如下:
//声明五种迭代器型别
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{};迭代器萃取器
有了上面的介绍,我们知道迭代器有着五大特征,给你一个迭代器,如何判断其某个特征呢? 我们还是以distance为例.
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance (InputIterator first, InputIterator last){
...
}那么我们怎么根据InputIterator来判断其Category呢? 这里就不得不提到Traits技术.
//迭代器萃取器
template<typename T>
class traits_iterator{
typedef typename T::value_type value_type;
typedef typename T::pointer_type pointer_type;
typedef typename T::reference_type reference_type;
typedef typename T::difference_type difference_type;
typedef typename T::iterator_category iterator_category;
};
//偏特化普通指针T*
template<typename T>
struct traits_iterator<T*>{
typedef T value_type;
typedef T* pointer_type;
typedef T& reference_type;
typedef ptrdiff_t difference_type;
typedef random_access_iterator_tag iterator_category;
};
//偏特化普通const指针 const T*
template<typename T>
class traits_iterator<const T*>{
typedef const T value_type;
typedef const T* pointer_type;
typedef T& reference_type;
typedef ptrdiff_t difference_type;
typedef random_access_iterator_tag iterator_category;
};所以你只需要简单的traits_iterator<InputIterator>::iterator_category就得到了其特征了,然后根据这个特征生成一个对象,根据这个iterator_category就找到具体的重载函数,就达到了不同iterator_category不同处理方式的目的了.
template<typename InputIterator>
typename traits_iterator<InputIterator>::difference_type
distance(InputIterator iter1, InputIterator iter2){
typedef typename traits_iterator<InputIterator>::iterator_category category;
return _distance(iter1, iter2, category());
}
template<typename InputIterator>
typename traits_iterator<InputIterator>::difference_type
_distance(InputIterator iter1, InputIterator iter2,
input_iterator_tag category){
typedef typename traits_iterator<InputIterator>::difference_type difference_type;
difference_type d = 0;
while(iter1++ != iter2){
d++;
}
return d;
}
template<typename InputIterator>
typename traits_iterator<InputIterator>::difference_type
_distance(InputIterator iter1, InputIterator iter2,
random_access_iterator_tag category){
return iter2 - iter1;
}see? 这就把迭代器的特征,traits_iterator萃取技术和重载函数联系到一起了.
类型萃取器
我们现在已经有了traits_iterator,那么似乎一切都已足够了,但是我们考虑uninitialized_copy函数这个问题. #### STL的uninitialized_copy函数
template<typename InputIterator, typename ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator begin, InputIterator end,
ForwardIterator result);uninitialized_copy函数是将[result, end - begin)区间的值一一赋值给[begin, end)区间.这个函数需要根据迭代器指向的类型来做判断,而不是迭代器类型做判断. 因为我们想一下,同样是指向vector的迭代器,但是一个是指向vector<A>,而另外一个是指向vector<B>, A不需要深拷贝而B需要深拷贝,所以这种情形下处理vector<B>就无法像处理vector<A>一样了.
所以,我们需要类型萃取器.类型萃取器和迭代器萃取器如出一辙,具体实现如下:
//特征标记是否可以进行高效拷贝操作等
struct true_POD{};
struct false_POD{};
//默认所有类型都是false_POD
template<typename T>
struct traits_type{
typedef false_POD is_POD;
};
//偏特化版本
template<typename T>
struct traits_type<T*>{
typedef true_POD is_POD;
};
template<>
struct traits_type<char>{
typedef true_POD is_POD;
};
template<>
struct traits_type<bool>{
typedef true_POD is_POD;
};
template<>
struct traits_type<int>{
typedef true_POD is_POD;
};
template<>
struct traits_type<long>{
typedef true_POD is_POD;
};
template<>
struct traits_type<float>{
typedef true_POD is_POD;
};
template<>
struct traits_type<double>{
typedef true_POD is_POD;
};
/*TODO
* unsigned int, unsigned char, ......
*/准备好了类型萃取后,我们就可以这样实现uninitialized_copy了:
/*
* [begin, end) 内容拷贝到[result, result + end - begin)中
* result保持不变，返回result + end - begin
*/
template<typename InputIterator, typename ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator begin, InputIterator end,
ForwardIterator result){
return _uninitialized_copy(begin, end, result, value_type(result));
}
//char* 偏特化
template<>
char* uninitialized_copy(const char* begin, const char* end, char* result){
//memmove当位置重叠时候保证拷贝正确，memcpy不保证
memmove(result, begin, end - begin);
return result + (end - begin);
}
//T*仅仅用来萃取T的POD特性，根据是否是POD类型做出处理
template<typename InputIterator, typename ForwardIterator, typename T>
ForwardIterator _uninitialized_copy(InputIterator begin, InputIterator end,
ForwardIterator result,T*){
typedef typename traits_type<T>::is_POD isPOD;
_uninitialized_copy_aux(begin, end, result, isPOD());
}
//true_POD
template<typename InputIterator, typename ForwardIterator>
ForwardIterator _uninitialized_copy_aux(InputIterator begin,
InputIterator end, ForwardIterator result, true_POD){
//快速拷贝 TODO
std::copy(begin, end, result);
}
//false_POD
template<typename InputIterator, typename ForwardIterator>
ForwardIterator _uninitialized_copy_aux(InputIterator begin,
InputIterator end, ForwardIterator result, false_POD){
//result保持不变
ForwardIterator cur = result;
while(begin != end){
_construct(&*cur, *begin);
++begin;
++cur;
}
return cur;
}总结
SGI的迭代器设计思想就是所有的迭代器都有五大特征,然后通过traits_iterator来萃取出任一特征,再根据不同的特征调用不同的重载函数,以达到不同情况做不同处理的目的.我想这就是迭代器的设计精髓.
声明:本文采用BY-NC-SA协议进行授权.转载请注明: 浅谈对SGI-STL迭代器设计思想的理解
comments powered by Disqus