阅读STL源码时有两个疑问:
1.在源码中大量出现的typedef有什么用?
2.源码中所谓的type_traits(类型萃取)是个什么东西?
其实这两个问题是有相关性的,想搞懂问题2必须先解决问题1
首先看STL中如何使用typedef,并解答问题1.
//STL中typedef大多用在相关容器的迭代器的设计中
//迭代器作为容器和算法之间沟通的桥梁,其作用就是在算法对某迭代器进行操作时
//告知算法有关当前容器的基本信息,如容器类型,容器中数据的类型等
//而typedef的作用就是将各容器中的基本信息统一命名,例如容器中数据元素的类型都叫value_type
//我们先来看STL中针对不同容器的迭代器的设计
//vector类
template <class T, class Alloc=alloc> //缺省使用alloc为vector的配置器
calss vector {
public:
typdef T value_type;
typedef value_type* iterator; //vector的迭代器是普通指针
...
};
//list的迭代器源码中这样设计
template <class T, class Ref, class Ptr>
struct _list_iterator {
....
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
}
//deque的迭代器设计
template <class T, class Ref, class Ptr>
struct _deque_iterator {
....
typedef T value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type;//这五个是迭代器必须有的相应型别的内嵌类型定义
}
//如此这般,当算法sort拿到某种类型iterator迭代器进行排序操作时
//便可以通过统一的value_type名称获取当前操作的容器中的数据类型是什么
//我们接着看一下STL内置的sort算法如何使用typedef重命名的value_type
//sort部分源码
template <class RandomAccessIterator>
void _insertion_sort(RandomAccessIterator first, RandomAccessIterator last){
if(first==last) return;
for( RandomAccessIterator i = first+1, i!=last, ++i){
_linear_insert (first, i, value_type(first));
}
}
//可以看到 无论sort接收的是什么类型的iterator,统一使用value_type进行排序操作
//这就是typedef的作用,可以告诉算法当前迭代器所指向容器中元素的数据类型是什么
问题1解决了,那问题2就好解决了
先说type_traits(类型萃取)的作用:说人话,type_traits实际上就相当于一个中介,或者是背调公司,当算法需要获取当前接收到的迭代器所指向容器中的数据信息时,通过type_traits来调查这个iterator,并且返回iterator里面的五个必要信息给算法。
有了上面的typedef,算法已经可以通过迭代器获取当前容器中元素的信息了,为什么还要单独弄个type_traits呢?
答:可以看到上面的代码中,除了vector外,其他容器的迭代器都是struct结构,其中包含了当前容器内容的有关信息,而vector的迭代器只是一个普通指针,并不能包含其他信息。所以其他容器的迭代器是封装好的类似智能指针的东西,这些封装好的iterator内已经包含了算法需要的必要信息,但是vector容器的迭代器呢?你无法在原始指针里再去包含其他信息。这个时候中介公司traits的作用就体现出来了,中介公司可以再做一层封装,特殊情况我特殊处理一下,然后向算法提供统一的调用接口,这样就避免了算法还需要根据不同的容器类型去设计不同的处理方式,那traits是如何进行统一化处理的呢?看源码
//1.如果传给traits的迭代器是封装好的迭代器则按此获取当前容器相关信息
template <class _Iterator>
struct iterator_traits {
typedef typename Iterator::iterator_category iterator_category;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
};
//如果传给traits的迭代器是原始指针(如vector的迭代器),则这样获取
template <class _Tp>
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag itrator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp*& reference;
};
template <class _Tp>
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag itrator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp*& reference;
};
可以看到,traits对不同种类的迭代器分别进行处理,当算法向traits询问当前迭代器所指容器中的各种信息时,traits根据接收到的迭代器类型不同,使用不同的访问方式,将获得的信息返回给算法,这样算法就方便了很多;
总结:迭代器Iterator作为算法对容器操作的桥梁,在面对不同种类型容器的迭代器时,为了避免算法麻烦,创建了traits这个中间人来统一向算法提供当前迭代器所指向容器中元素的相关信息。