STL源码剖析读书笔记
目录
一．迭代器
1. 迭代器的定义 2. 为什么需要迭代器 3. 迭代器工作原理 4. 迭代器的分类
二．Traits编程技法
1. 为什么需要Traits编程技法？ 2. Traits编程技法原理 3. iterator_traits剖析 4. std::iterator的约定 5. 扩展，SGI STL的__type__traits
三．总结
正文
一．迭代器
1.迭代器的定义
迭代器是一种抽象的设计概念，迭代器是一种数据结构，提供统一方法（如遍历，获取元素）对容器内部的元素进行操作，而又无需暴露容器元素的内部表达方式。
举个例子，指针可以看做是数组的迭代器（尽管不太符合STL规范），但是指针有很多种，我们可以提供一个封装来解决这个问题
template<tyname PtrType>
class Proxy
{
PtrType* ProxyPtr;
//……
}
通过模板，我们用Proxy这个类统一了指针 Proxy<int>就是int指针Proxy<string>就是string指针
它提供了统一的操作（取地址，随机访问）不管什么类型数组，反正都是用Proxy<PtrType>取地址，地址上的值就是数组内对应的元素，指针p+n对应的就是数组第n个元素，不管p是什么类型指针。
也就是说，迭代器是一类对象（不管Proxy特化为什么类型指针，都是Proxy类，都是针对数组这个容器），有着统一的方法与针对不同容器特定的行为，对容器进行操作，而不论容器类型，使得通用算法通过迭代器对不同容器起同样的效果。不同容器有专有的迭代器，但是这些迭代器都有统一的接口（方法），区别只是这些方法的内部实现不一样。
2.为什么需要迭代器？
迭代器是GP泛型编程的重要组件，是容器与算法重要的胶合剂，多种容器对应多种专有迭代器，但是这些迭代器是外在统一的方法，内在不同的实现。可以对应同一个算法正常运作。没有迭代器，通用算法就没法实现通用。
3.迭代器的工作原理
迭代器的工作原理与指针类型，因为迭代器是对象，通过对操作符*，->的重载，完成对容器\内被指向的元素的获取，通过++，--，operator[]操作符重载，完成迭代器指向下一个元素，上一个元素，随机访问容器内元素。
例如STL的通用算法find（begin，end，value）；
template<typename T>
Iterator find(Iterator begin, Iteratorend,const T& value)
{
While(begin!=end&& *begin != value)
++begin;
Return begin;
}
假设这里的iterator是一个指针，那么久很好理解了，第一个参数是指向某一个容器头部的指针，第二个参数指向容器尾部的指针，value是要搜索的值，find要搜索的value就返回指向容器内部那个值的指针。
对于内置数据类型的顺序容器，很多就可以像我那个proxy<PtrType>这样封装一下就是个迭代器，放到这个算法里面也没有问题。如果是关联容器，底层是树，哈希表这样的数据结构，为了也能满足这个算法，很明显不能用原始的指针了，需要对++ *->这些运算符重载，指定遍历树中的元素顺序，来模拟普通的顺序遍历，从而满足find这样的算法。
1. 迭代器的分类
对于STL，内置的迭代器相应的可以划分为这么几个类型：
|
迭代器类型 |
说明 |
|
Input |
这种迭代器所指对象是只读的，迭代器取出所指的值，可以访问下一个元素，判断是否到达最后元素，支持操作 *p(返回值不允许修改),++p,p++,p!=q,p==q |
|
Output Iterator |
和Input Iterator迭代器类型，不过返回值允许修改，支持*p,++p,p++,p!=q,p==q的操作 |
|
Forward |
前向迭代器，和Output Iterator支持操作一致 |
|
Bidirectional Iterator |
双向迭代器，Forward Iterato支持的操作都支持，还支持--p,p--. |
|
Random Access Iterator |
随机访问迭代器，Bidirectional |
迭代器分类表
从左到右，迭代器越来越高等
不同算法对所需要的迭代器有要求，不过根据STL的算法参数命名规则，以算法能接受的最初等的迭代器类型来为参数命名，也就是说，接受Input Iterator类型参数的算法肯定也支持Random Access Iterator类型的参数。
二．Traits编程技法
1．为什么需要Traits编程技法？
STL的算法分通用算法和专有算法，对于有些容器，由于容器特殊，用通用算法比较耗时，为了提高效率，又针对这一容器编写了专有的算法来优化效率。
对于算法来说，如果知道操作的迭代器所指对象的类型，可以根据所指对象的不同类型，进行不同的优化。从而提高算法的效率。例如copy算法，如果知道是元素是POD类型（POD类型指在内存布局上与C兼容的类型，可以用memcpy直接拷贝对象），可以直接用memcpy(),对于是char*的类型封装的迭代器，甚至可以用memmove()函数来优化效率。
2. Traits编程技法原理
那么，一个关键性问题，对于通用算法，获取到的信息只有迭代器本身的信息，它如果知道迭代器所指对象的类型呢？毕竟C++不支持C#的typeof，而typeid属于RTTI，不能用来声明变量，而且RTTI的效率不高，那么为了解决这个问题，就诞生了Traits编程技法。Traits在英文中是特征的意思，根据事先约定的迭代器编写规则，在迭代器类中给出足够的所指对象信息，在通用算法中获取迭代器所指对象的信息。
对于一个迭代器类，列如一开始举得例子模板类Proxy，在实例化的时候，模板参数PtrType就是这个array容器的迭代器所指的元素类型。那么我们可以在Proxy中内嵌类型声明。这样在Proxy模板外我们可以用typename 调用模板类作用域下属的内嵌类型。
例如
template<tynamePtrType>
class Proxy
{
typedef T value_type;
PtrType* ProxyPtr;
//……
}
在Proxy类模板类外面
template<typenameIterator>
void Find(Iteratora)
{
typedef typename Iterator::value_type Value_type//可以用typename来获取所指对象的类型，搭配typedef来声明新类型。
Value_type test; //用迭代器所指对象的类型来声明变量
}
Int main()
{
Proxy<int>iter;
Find(iter);
}
对于自定义迭代器，可以通过在迭代器内内嵌声明来解决问题，但是对于原生指针的迭代器，如何在Find函数内获取声明呢，这里可以通过增加一个间接层代理类iterator_traits来解决问题。
对于自定义的迭代器，因为已经内嵌声明了，所以有
template<typename T>//自定义迭代器 T是传入的类型
class Iterator
{
public:
typedef T value_type;
protected:
private:
T* iter;
};
template<typename Iterator>
struct Iterator_traits
{
typedef Iterator::value_type value_type;
};
对于原生指针作为迭代器的，可以使用模板偏特化来解决。模板偏特化指需要根据模板的某些但不是全部的参数进行特化,就解决了原生指针的迭代器获取指向对象的类型的问题了。如下
template<typename T>//T是一个原生指针
class Iterator_traits<T*>
{
public:
typedef T value_type;
protected:
private:
};
那么通用算法的find（）应该改写成这样
template<typename Iterator,typenameT>
typename iterator_traits<Iterator>::value_typeFind(Iterator begin, Iterator end,const T& Value)
{
/*…………*/
}
现在，不论是原生指针还是封装过的自定义迭代器，都可以通过iterator_traits获取正确的指向对象的类型。
3. iterator_traits剖析
实际上，SGI STL的源码内，Iterator_traits类可以获取的信息是非常丰富的，
如
struct iterator_traits
{
typedef typename::I::iterator_categoryiterator_category;
typedef typename::I::value_typevalue_type;
typedef typename::I::difference_typedifference_type;
typedef typename::I::pointerpointer;
typedef typename::I::referencereference;
};
下面一一解释。
（1） value_type
value_type是指迭代器所指对象的的类型，任何一个自定义迭代器，都应该内嵌value_type类型。做法如上节所述
（2） difference_type
difference_type是定义两个迭代器之间距离的变量的类型。也可以作为保存容器最大容器的变量类型。如果一个泛型的通用算法提供计数功能，那应该是这样的
template<typename I,typenameT>
typename::iterator_traits<I>::difference_type count(I begin,I end,const T& Value)
{
typename::iterator_traits<I>::difference_type n= 0;
for (;begin!=end;++begin)
{
if (*begin == Value)
{
n++;
}
}
return n;
}
对于原生指针，C++内建了ptrdiff_t作为原生指针的difference_type(定义在<cstddef>，在VS2010上看，其实就是int)
template<typename T>
struct iterator_traits<T*>
{
typedef ptrdiff_t difference_type;
/*………………*/
};
（3） reference
当迭代器需要返回容器内的元素本身来对元素的值进行修改时，即使用具有写入功能的迭代器，就应该在*p时，返回一个p所指元素的引用，那么返回的应该是对象的引用类型，即返回这个reference类型。具体实现的源码在pointer后。
（4） pointer
当迭代器需要返回容器内的元素本身来对元素的值进行修改时，即使用具有写入功能的迭代器，就应该在*p时，返回一个p所指元素的引用，既然引用可以，那么用指针也可以，不过指针没有引用安全而已。
所以我们可以这样设计
template<typename PtrType>//PtrType是原生指针，iterator是自定义迭代器
struct iterator
{
...
typedef T* pointer;
typedef T& reference;
};
template<typename I>//I是自定义迭代器
struct iterator_traits
{
...
typedef I::pointer pointer;
typedef I::reference reference;
};
template<typename T>//T是原始指针?
struct iterator_traits<T*>
{
...
typedef T* pointer;
typedef T& reference;
};
（5） iterator_category
iterator_category是迭代器所属分类的标示符，具体分类请看一，4.迭代器的分类。
STL的算法是追求效率的极致，为了效率最高，最好是对不同分类的迭代器都有不同的算法优化，如有一个通用算法test。为了通用于5种不同迭代器，一种解决办法就是写5个接受不同种迭代器参数的同名函数，这样即使我的ForwardIterator 和InputIterator的test算法优化一样，我也要复制粘贴两遍，这样才能对ForwardIterator和InputIterator类型的迭代器使用test算法，这是极其违反软件工程的DRY原则的。那么另外一个解决办法可能是这样的
void test(Iterator a)
{
if (is_InputIterator(a)) //函数能不能设计出来另说，判断是不是InputIterator
{
}
else if(is_OutputIterator(a))//判断是不是OutputIterator
{
}
else if(is_XXXIterator(a))
{
}
....
}
这样的if-else分支选择和判断函数的使用会影响效率，如果使用重载机制来确定使用什么函数的话，就可以在编译器解决这个问题，从而提高算法效率。
编译期解决方案如下，如果iterator_traits能够获取迭代器所属种类的话，就可以在通用算法中加入第三个参数来匹配迭代器种类，通过iterator_traits<I>::iterator_category()作为第三个参数，来确定使用的函数类型，就可以编译期通过函数重载解决大量if-else这个问题。
为了解决同一个算法，因为两个不同迭代器要复制一遍的问题，可以使用派生类的隐式类型转换到基类来做。
解决方案如下，先构造迭代器分类的类型继承链
struct input_iterator_tag{};
struct output_iterator_tag{};
struct forward_iterator_tag : publicinput_iterator_tag{};
struct bidirectional_iterator_tag : publicforward_iterator_tag {};
struct random_access_iterator_tag : publicbidirectional_iterator_tag{};
现在假设一个算法test，对所有迭代器都适用，并且inputforward bidirectional random迭代器的代码相同，那么只要写两个版本的迭代器算法如下。
template<typename InputIterator>
void __test(InputIterator a,input_iterator_tag)
{
}
template<typename OutputIterator>
void __test(OutputIterator a,output_iterator_tag)
{
}
template<typename InputIterator>
void test(InputIterator a)
{
__test(a,iterator_traits<InputIterator>::iterator_category())
}
当传入给a的是input迭代器，那么会通过__test()的第二个参数确定重载，确定使用的函数，当传给a的是random迭代器，因为random是input迭代器的派生类，所以为了匹配__test函数。第二个参数会被隐式转换为input基类，然后调用使用input_iterator_tag的函数,这样就解决了违反DRY原则的问题。
下面是SGI iterator的部分源码
// 节录自SGI STL <stl_iterator.h>
// 五种迭代器类型
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 {};
// 为避免写码时挂㆒漏万，自行开发的迭代器最好继承自下面这个，具体细节后述
std::iterator
template <class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&>
struct iterator {
typedef Category iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
// 「榨汁机」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;
};
// 针对原生指标（native pointer）而设计的traits 偏特化版。
template <class T>
struct iterator_traits<T*> {
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
};
// The overloaded functions iterator_category, distance_type,and
// value_type are not part of the C++ standard. (They have been
// replaced by struct iterator_traits.) They are included for
// backward compatibility with the HP STL.
// We introduce internal names for these functions.
//这个函数方便确定迭代器类型
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
__iterator_category(const _Iter&)
{
typedef typenameiterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
//这个函数方便确定迭代器之间距离的类型
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)
{
returnstatic_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}
//这个函数方便确定迭代器所指对象的类型
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
returnstatic_cast<typename iterator_traits<_Iter>::value_type*>(0);
}
template <class _Iter>
inline typename iterator_traits<_Iter>::iterator_category
iterator_category(const _Iter& __i) { return__iterator_category(__i); }
template <class _Iter>
inline typename iterator_traits<_Iter>::difference_type*
distance_type(const _Iter& __i) { return__distance_type(__i); }
template <class _Iter>
inline typename iterator_traits<_Iter>::value_type*
value_type(const _Iter& __i) { return __value_type(__i); }
//下面了是利用了重载判断和iterator_traits特性的distance函数和advance函数
template <class _InputIterator, class _Distance>
inline void __distance(_InputIterator __first, _InputIterator__last,
_Distance& __n, input_iterator_tag)
{
while (__first !=__last) { ++__first; ++__n; }
}
template <class _RandomAccessIterator, class _Distance>
inline void __distance(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Distance& __n, random_access_iterator_tag)
{
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__n += __last - __first;
}
template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first,
_InputIterator __last, _Distance& __n)
{
__STL_REQUIRES(_InputIterator, _InputIterator);
__distance(__first,__last, __n, iterator_category(__first));
}
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _InputIterator>
inline typenameiterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,input_iterator_tag)
{
typenameiterator_traits<_InputIterator>::difference_type __n = 0;
while (__first !=__last) {
++__first; ++__n;
}
return __n;
}
template <class _RandomAccessIterator>
inline typenameiterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator__last,
random_access_iterator_tag) {
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
return __last - __first;
}
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last) {
typedef typenameiterator_traits<_InputIterator>::iterator_category
_Category;
__STL_REQUIRES(_InputIterator, _InputIterator);
return__distance(__first, __last, _Category());
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
template <class _InputIter, class _Distance>
inline void __advance(_InputIter& __i, _Distance __n,input_iterator_tag) {
while (__n--) ++__i;
}
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM!= _MIPS_SIM_ABI32)
#pragma set woff 1183
#endif
template <class _BidirectionalIterator, class _Distance>
inline void __advance(_BidirectionalIterator& __i, _Distance__n,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIterator,_BidirectionalIterator);
if (__n >= 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
#if defined(__sgi) && !defined(__GNUC__) &&(_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1183
#endif
template <class _RandomAccessIterator, class _Distance>
inline void __advance(_RandomAccessIterator& __i, _Distance__n,
random_access_iterator_tag) {
__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
__i += __n;
}
template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
__STL_REQUIRES(_InputIterator, _InputIterator);
__advance(__i, __n,iterator_category(__i));
}
__STL_END_NAMESPACE
4.std::iterator的约定
为了符合STL迭代器设计规范，任何迭代器都应该提供这5个内嵌类型。以利于iterator_traits获取类型信息，否则可能无法与其他STL组件顺利搭配。然而谁都有粗心大意的时候，为了让自定义的每一个类都符合规范，STL提供了一个iterator class，只要继承这个类，就可以保证每一个自定义的迭代器都符合规范。
template<class Categroy,class T,class Distance =ptrdiff_t,class Pointer = T*,class Reference = T&>
struct iterator
{
typedef Categroy iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
};
template<class Ptr>
struct MyIter : publiciterator<iterator<forward_iterator_tag>,Ptr >
{
/*………………………………….*/
};
5.扩展，SGISTL的__type__traits
在SGI STL中还有一个特有的扩展，TypeTraits，判断传给它的类型是否具有
trivial_default_constructor无用的默认构造函数
trivial_copy_consturctor 无用的拷贝构造函数
trivial_assignment_operator无用的赋值函数
trivial_destructor无用的析构函数
trivial_des1tructor is_POD_type;类型是POD类型
知道这些信息后，我们就可以对类型进行相应的优化，例如，如果传给typeTraits类型是属于POD类型的，那么就可以用memcpy函数快速构造，对于析构函数，可以什么都不做，直接标记空间不再使用即可。这样对于容器类可以大幅提升效率。
根据iterator_traits编写的经验，我们希望可以这样用__type__traits<T>,T代表任意类型。
__type__traits<T>::has_trivial_default_constructor;
__type__traits<T>::has_trivial_default_destructor;
__type__traits<T>::has_trivial_copy_constructor;
__type__traits<T>::has_trivial_assgnment_operator;
__type__traits<T>::is_POD_type;
我们希望上面的式子返回真或假，为了能激活函数重载，不再运行期影响效率，我们构建两个类来作为上式的返回值。
Struct __true__type{};
Struct __false__type{};
为了完成上述式子，__type__traits内必须定义一些typedefs，SGI源码做法如下：
struct __true_type {};
struct __false_type {};
template <typename type>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;//和编译器相关
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_constructor;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
//POD指的是这样一些数据类型：在内存布局中和C兼容的类型、
//构造函数是 trivial 的 struct 或者 class
};
所有自定义的类型，为了优化效率，也应该在类型内嵌这些声明。来使STL的算法通过__type__traits<T>::has_trivial_xxxx得知类型信息，进行效率优化。
SGI对于所有内置类型都给出了包含这些声明的特化版本。下面是源码：
//type_traits.h
#ifndefTYPE_TRAITS_H
#defineTYPE_TRAITS_H
struct__true_type {};
struct__false_type {};
template<typename type>
struct__type_traits {
//不要移除
typedef __true_typethis_dummy_member_must_be_first;
//trivial指无意义的
typedef __false_typehas_trivial_default_constructor;
typedef __false_typehas_trivial_copy_constructor;
typedef __false_typehas_trivial_assignment_constructor;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
//POD指的是这样一些数据类型：基本数据类型、指针、union、数组、
//构造函数是 trivial 的 struct 或者class
};
//特化版本
template<>
struct__type_traits<char> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<signed char> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<unsigned char> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<short> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<unsigned short> {
typedef __true_type has_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<int> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<unsigned int> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<long> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<unsigned long> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<float> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<double> {
typedef __true_type has_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本
template<>
struct__type_traits<long double> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
//特化版本(原生指针)
template<class T>
struct__type_traits<T*> {
typedef __true_typehas_trivial_default_constructor;
typedef __true_typehas_trivial_copy_constructor;
typedef __true_typehas_trivial_assignment_constructor;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#endif
三．总结
1.Traits编程技法，通过与迭代器约定编写规范，成功的获取了对象的类型信息，从而使得算法可以通过类型信息来优化效率。
2.使用重载判断来去掉运行期冗余的if-else条件分支，再一次的提高了效率。通过结构体类型的相互继承，利用派生类与向基类指针的隐式转换，减少了算法的编写量。提高了效率。
3.通过对迭代器的traits扩展，使得所有类型都满足traits编程规范，这样STL算法可以通过type__traits获取类型信息后，进一步优化效率。
4.对于迭代器和原生指针获取对象类型信息的方法不统一的问题，通过增加一个间接层代理类来统一对外的方法和接口。成功运用代理模式解决了问题。