在STL程式設計中，容器和算法是獨立設計的，即資料結構和算法是獨立設計的，連接配接容器和算法的橋梁就是疊代器了，疊代器使其獨立設計成為可能。Traits程式設計技術是STL中最重要的程式設計技術，Traits可以擷取一個類型的相關資訊。
3.4 Traits程式設計技術
Traits可以擷取一個類型的相關資訊，首先我們看下面的程式：
template <class T, class type>
void function(T t, type u) {
type temp;
// ... The rest work of function…
}
在上面的程式中，我們怎麼樣才能獲得已聲明變量temp的類型type呢？在模闆中，模闆參數推導機制可以解決這個問題，在下面程式中編譯器知道變量temp的類型為int：
template <class T, class type>
void function(T iter, type u)
{
type temp; // 通過模闆參數推導獲得temp變量的類型
....
}
template <class T>
void func(T iter)
{
function(iter, *iter);
}
int main()
{
int i = 12;
func(&i)
}
上面介紹的是獲得 局部變量的類型，這個可以通過模闆參數推導機制完成；如果我們要獲得函數傳回值的類型時，該怎麼處理呢？這個問題針對不同類型有不同的方法可以解決，類型型别：使用者自定義類型（如結構體，類）和内置類型（如整型，原生指針等）。
若我們要知道使用者自定義類型的函數傳回值類型，我們可以使用内嵌型别技術就可以知道傳回值的類型；看下面程式：
templates <class T>
struct Iterator
{
typedef T value_type;//内嵌型别聲明
...
};
template <class Iterator>
typename Iterator::value_type //傳回值類型
GetValue(Iterator iter)
{
return *iter;
}
int main()
{
...
Iterator<int> ite(new int(9));
std::cout<<GetValue(ite)<<std::endl;
return 0;
}
在使用者自定義類型中我們可以通過内嵌型别獲得傳回值的類型，若不是使用者自定義的類型，而是内置類型時，例如是原生指針，這時候該怎麼處理呢？因為原生指針不能内嵌型别聲明，是以内嵌型别在這裡不适用。于是Traits技術就出現了。以下利用Traits技術也可以擷取使用者自定義類型的傳回值類型。
template <class Iterator>
struct iterator_traits {
typedef typename Iterator::value_type value_type;
...
};
template <class Iterator>
typename iterator_traits<Iterator>::value_type //傳回值類型
GetValue(Iterator iter)
{
return *iter;
}
以上這種方法對原生指針不可行，是以iterator_traits針對原生指針的一個版本就應運而生。下面是針對*Tp和const *Tp的版本，也稱為 iterator_traits版本的偏特化。iterator_traits的偏特化版本解決了原生指針的問題。現在不管疊代器是自定義類模闆, 還是原生指針(Tp*, const Tp*),struct iterator_traits都能萃取出正确的value type類型。
template <class Tp>
struct iterator_traits<Tp*> {
typedef Tp value_type;
...
};
template <class Tp>
struct iterator_traits<const Tp*> {
typedef Tp value_type;
...
};
我們之是以要萃取（Traits）疊代器相關的類型，就是要把疊代器相關的類型用于聲明局部變量、用作函數的傳回值等一系列行為。對于原生指針和point-to-const類型的指針，采用模闆偏特化技術對其進行特殊處理。 要使用Traits功能，則必須自行以内嵌型别定義的方式定義出相應型别。我們上面講解的隻是疊代器其中一種類型value type，在疊代器中還有其他類型：
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; //疊代器引用之物
};
在STL的思想中，容器和算法是彼此獨立設計的，再通過某種方式使它們連接配接；而疊代器是使算法獨立于使用的容器類型，即疊代器是連接配接算法和容器的方法。由于疊代器是一種行為類似指針的對象，也就說疊代器是一種廣義指針，即疊代器對解除引用操作（operator*）和通路成員操作（operator->）進行重載。然而要對這兩個操作符進行重載，對容器内部對象的資料類型和存儲結構有所了解，于是在 STL 中疊代器的最終實作都是由容器本身來實作的，每種容器都有自己的疊代器實作。
3.5 疊代器
疊代器的分類
在SGI STL中根據讀寫和通路方式，在源碼中疊代器大緻可分為五類：
輸入疊代器input_iterator：隻讀，且隻能一次讀操作，支援操作：++p,p++,!=,==,=*p,p->；
輸出疊代器output_iterator：隻寫，且隻能一次寫操作，支援操作：++p,p++；
正向疊代器forward_iterator：可多次讀寫，支援輸入輸出疊代器的所有操作；
雙向疊代器bidirectional_iterator：支援正向疊代器的所有操作，且支援操作：--p,p--；
随機通路疊代器random_access_iterator：除了支援雙向疊代器操作外，還支援：p[n],p+n,n+p,p-n,p+=n,p-=n,p1-p2,p1<p2,p1>p2,p1>=p2,p1<=p2；
/*This program is in the file of stl_iterator_base.h form line 42 to 92*/
//疊代器類型标簽
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 {};
/*以下是五種疊代器類型資料類型*/
template <class _Tp, class _Distance> struct input_iterator {
typedef input_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
struct output_iterator {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template <class _Tp, class _Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp, class _Distance> struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp, class _Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
3.6 疊代器iterator源碼
在STL的算法設計中需要疊代器的型别，根據不同要求和不同型别，有不同的技巧解決；如：使用模闆參數推導機制推導出局部變量類型；内嵌型别求出傳回值類型；traits技術解決傳回值類型和偏特化traits技術解決原生指針問題；疊代器的型别如下代碼所示：
template <class _Iterator>
/*Traits技術，萃取出類型的相關資訊*/
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技術我們可以獲得疊代器的相關類型的資訊iterator_traits<…>::…，下面給出Traits技術的相關源碼：
/*為使用者自行開發的疊代器提供友善，使用者自行開發的疊代器最後繼承該iterator class，以便使用Traits技術*/
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
#endif /* __STL_USE_NAMESPACES */
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _Iterator>
/*Traits技術，萃取出類型的相關資訊*/
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;
};
template <class _Tp>
/*針對原生指針Tp*生成的Traits偏特化版本*/
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp>
/*針對原生指針const Tp*生成的Traits偏特化版本*/
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& reference;
};
在疊代器中，為了能夠在編譯時确定函數調用，應用了函數重載。因為五種疊代器操作能力是不同的，例如random acess iterator是操作能力最強的，可以在O(1)時間操作指定位置，而這個用其他的疊代器可能需要O(n)。是以為了提高效率，使用疊代器類型最比對的算法函數去調用：
1、首先通過traits技術獲得疊代器類型iterator_category；
2、在函數調用時生成相應疊代器類型的臨時對象作為實參傳遞，編譯器就會調用相應的重載函數。
為了重載函數識别，SGI STL有對應的5種疊代器辨別類：繼承是為了可以使用傳遞調用，當不存在某種疊代器類型比對時編譯器會依據繼承層次向上查找進行傳遞。
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 {};
例如下面是advance()函數的調用，針對不同的疊代器類型，對函數進行重載：
/*函數重載，使疊代器能在編譯時期就确定調用哪個函數*/
template <class _InputIter, class _Distance>
/*疊代器類型為input_iterator_tag的函數定義*/
inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
while (__n--) ++__i;
}
template <class _BidirectionalIterator, class _Distance>
/*疊代器類型為bidirectional_iterator_tag的函數定義*/
inline void __advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag) {
__STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
if (__n >= 0)
while (__n--) ++__i;
else
while (__n++) --__i;
}
template <class _RandomAccessIterator, class _Distance>
/*疊代器類型為random_access_iterator_tag的函數定義*/
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));
}
SGI STL疊代器完整源碼剖析
以下對整個源碼進行剖析，給出相應的注釋：
#ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H
#define __SGI_STL_INTERNAL_ITERATOR_BASE_H
// This file contains all of the general iterator-related utilities.
// The internal file stl_iterator.h contains predefined iterators,
// such as front_insert_iterator and istream_iterator.
#include <concept_checks.h>
__STL_BEGIN_NAMESPACE
/*五中疊代器類型*/
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 {};
// The base classes input_iterator, output_iterator, forward_iterator,
// bidirectional_iterator, and random_access_iterator are not part of
// the C++ standard. (They have been replaced by struct iterator.)
// They are included for backward compatibility with the HP STL.
/*五中疊代器類型的結構*/
template <class _Tp, class _Distance> struct input_iterator {
typedef input_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
struct output_iterator {
typedef output_iterator_tag iterator_category;
typedef void value_type;
typedef void difference_type;
typedef void pointer;
typedef void reference;
};
template <class _Tp, class _Distance> struct forward_iterator {
typedef forward_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp, class _Distance> struct bidirectional_iterator {
typedef bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp, class _Distance> struct random_access_iterator {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
#ifdef __STL_USE_NAMESPACES
/*為使用者自行開發的疊代器提供友善，使用者自行開發的疊代器最後繼承該iterator class，以便使用Traits技術*/
template <class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct iterator {
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
};
#endif /* __STL_USE_NAMESPACES */
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
template <class _Iterator>
/*Traits技術，萃取出類型的相關資訊*/
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;
};
template <class _Tp>
/*針對原生指針Tp*生成的Traits偏特化版本*/
struct iterator_traits<_Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef _Tp* pointer;
typedef _Tp& reference;
};
template <class _Tp>
/*針對原生指針const Tp*生成的Traits偏特化版本*/
struct iterator_traits<const _Tp*> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef ptrdiff_t difference_type;
typedef const _Tp* pointer;
typedef const _Tp& 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 typename iterator_traits<_Iter>::iterator_category _Category;
return _Category();
}
template <class _Iter>
/*求出疊代器的distance_type*/
inline typename iterator_traits<_Iter>::difference_type*
__distance_type(const _Iter&)
{
return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
}
template <class _Iter>
/*求出疊代器的value_type*/
inline typename iterator_traits<_Iter>::value_type*
__value_type(const _Iter&)
{
return static_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); }
#define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
#define __DISTANCE_TYPE(__i) __distance_type(__i)
#define __VALUE_TYPE(__i) __value_type(__i)
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
/*以下是求出偏特化版本的疊代器的各種類型*/
template <class _Tp, class _Distance>
inline input_iterator_tag
iterator_category(const input_iterator<_Tp, _Distance>&)
{ return input_iterator_tag(); }
inline output_iterator_tag iterator_category(const output_iterator&)
{ return output_iterator_tag(); }
template <class _Tp, class _Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<_Tp, _Distance>&)
{ return forward_iterator_tag(); }
template <class _Tp, class _Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
{ return bidirectional_iterator_tag(); }
template <class _Tp, class _Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<_Tp, _Distance>&)
{ return random_access_iterator_tag(); }
template <class _Tp>
inline random_access_iterator_tag iterator_category(const _Tp*)
{ return random_access_iterator_tag(); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
{ return (_Tp*)(0); }
template <class _Tp>
inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
template <class _Tp, class _Distance>
inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const bidirectional_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp, class _Distance>
inline _Distance*
distance_type(const random_access_iterator<_Tp, _Distance>&)
{
return (_Distance*)(0);
}
template <class _Tp>
inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
// Without partial specialization we can't use iterator_traits, so
// we must keep the old iterator query functions around.
#define __ITERATOR_CATEGORY(__i) iterator_category(__i)
#define __DISTANCE_TYPE(__i) distance_type(__i)
#define __VALUE_TYPE(__i) value_type(__i)
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
/*
*這是distance()函數，求出兩個疊代器之間的距離，為了在編譯期間确定調用的函數，
*這裡針對不同疊代器的類型進行的函數重載；
*/
template <class _InputIterator, class _Distance>
/*疊代器為input_iterator_tag的distance()函數版本*/
inline void __distance(_InputIterator __first, _InputIterator __last,
_Distance& __n, input_iterator_tag)
{
while (__first != __last) { ++__first; ++__n; }
}
template <class _RandomAccessIterator, class _Distance>
/*疊代器為random_access_iterator_tag的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>
/*對外接口的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
/*以下是偏特化版本的distance()函數*/
template <class _InputIterator>
inline typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) {
++__first; ++__n;
}
return __n;
}
template <class _RandomAccessIterator>
inline typename iterator_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 typename iterator_traits<_InputIterator>::iterator_category
_Category;
__STL_REQUIRES(_InputIterator, _InputIterator);
return __distance(__first, __last, _Category());
}
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
/*對advance()進行重載，重載的作用是為了疊代器在編譯時期就能确定調用哪種類型疊代器的函數*/
template <class _InputIter, class _Distance>
/*疊代器類型為input_iterator_tag的函數定義*/
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>
/*疊代器類型為bidirectional_iterator_tag的函數定義*/
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>
/*疊代器類型為random_access_iterator_tag的函數定義*/
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
#endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */
// Local Variables:
// mode:C++
// End:
3.7 SGI STL的__type_traits技術
前面介紹的Traits技術在STL中彌補了C++模闆的不足，但是在STL中，Traits技術隻是用來規範疊代器，對于疊代器之外的東西沒有加以規範。是以，SGI将該技術擴充到疊代器之外的東西，稱為__type_traits。iterator_traits是萃取疊代器的特性，而__type_traits是萃取型别的特性。
萃取的型别如下：
是否具備non-trivial default ctor?
是否具備non-trivial copy ctor?
是否具備non-trivial assignment operator?
是否具備non-trivial dtor?
是否為POD（plain old data）型别？
其中non-trivial意指非預設的相應函數，編譯器會為每個類構造以上四種預設的函數，如果沒有定義自己的，就會用編譯器預設函數，如果使用預設的函數，我們可以使用memcpy(),memmove(),malloc()等函數來加快速度，提高效率。
定義在SGI<type_traits.h>中__type_traits，提供了一種機制，針對不同型别的特性，在編譯時期完成函數派送決定。
template <class _Tp>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
/* Do not remove this member. It informs a compiler which
automatically specializes __type_traits that this
__type_traits template is special. It just makes sure that
things work if an implementation is using a template
called __type_traits for something unrelated. */
/* The following restrictions should be observed for the sake of
compilers which automatically produce type specific specializations
of this class:
- You may reorder the members below if you wish
- You may remove any of the members below if you wish
- You must not rename members without making the corresponding
name change in the compiler
- Members you add will be treated like regular members unless
you add the appropriate support in the compiler. */
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
其中傳回真假的“對象”是：
struct __true_type {
};
struct __false_type {
};
将bool, char, short, int, long, float, double等基本的資料類型及其相應的指針類型的這些特性都定義為__true_type，這意味着，這些對基本類型進行構造、析構、拷貝、指派等操作時，都是使用系統函數進行的。而除了這些類型之外的其他類型，除非使用者指定了它的這些特性為__true_type，預設都是 __false_type 的，不能直接調用系統函數來進行記憶體配置或指派等，而需要調用該類型的構造函數、拷貝構造函數等。下面是整個__type_traits源碼剖析：
#ifndef __TYPE_TRAITS_H
#define __TYPE_TRAITS_H
#ifndef __STL_CONFIG_H
#include <stl_config.h>
#endif
/*
This header file provides a framework for allowing compile time dispatch
based on type attributes. This is useful when writing template code.
For example, when making a copy of an array of an unknown type, it helps
to know if the type has a trivial copy constructor or not, to help decide
if a memcpy can be used.
The class template __type_traits provides a series of typedefs each of
which is either __true_type or __false_type. The argument to
__type_traits can be any type. The typedefs within this template will
attain their correct values by one of these means:
1. The general instantiation contain conservative values which work
for all types.
2. Specializations may be declared to make distinctions between types.
3. Some compilers (such as the Silicon Graphics N32 and N64 compilers)
will automatically provide the appropriate specializations for all
types.
EXAMPLE:
//Copy an array of elements which have non-trivial copy constructors
template <class T> void copy(T* source, T* destination, int n, __false_type);
//Copy an array of elements which have trivial copy constructors. Use memcpy.
template <class T> void copy(T* source, T* destination, int n, __true_type);
//Copy an array of any type by using the most efficient copy mechanism
template <class T> inline void copy(T* source,T* destination,int n) {
copy(source, destination, n,
typename __type_traits<T>::has_trivial_copy_constructor());
}
*/
/*定義兩個傳回對象*/
struct __true_type {
};
struct __false_type {
};
template <class _Tp>
/*該結構能夠滿足傳回值隻有__true_type或者__false_type*/
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
/* Do not remove this member. It informs a compiler which
automatically specializes __type_traits that this
__type_traits template is special. It just makes sure that
things work if an implementation is using a template
called __type_traits for something unrelated. */
/* The following restrictions should be observed for the sake of
compilers which automatically produce type specific specializations
of this class:
- You may reorder the members below if you wish
- You may remove any of the members below if you wish
- You must not rename members without making the corresponding
name change in the compiler
- Members you add will be treated like regular members unless
you add the appropriate support in the compiler. */
typedef __false_type has_trivial_default_constructor;
typedef __false_type has_trivial_copy_constructor;
typedef __false_type has_trivial_assignment_operator;
typedef __false_type has_trivial_destructor;
typedef __false_type is_POD_type;
};
// Provide some specializations. This is harmless for compilers that
// have built-in __types_traits support, and essential for compilers
// that don't.
/*下面是針對特定類型的type_traits技術，例如：bool,char,short,int,long,float,double*/
#ifndef __STL_NO_BOOL
__STL_TEMPLATE_NULL struct __type_traits<bool> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#endif /* __STL_NO_BOOL */
__STL_TEMPLATE_NULL struct __type_traits<char> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<signed char> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned char> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#ifdef __STL_HAS_WCHAR_T
__STL_TEMPLATE_NULL struct __type_traits<wchar_t> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#endif /* __STL_HAS_WCHAR_T */
__STL_TEMPLATE_NULL struct __type_traits<short> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned short> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<int> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned int> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<long> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned long> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#ifdef __STL_LONG_LONG
__STL_TEMPLATE_NULL struct __type_traits<long long> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned long long> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#endif /* __STL_LONG_LONG */
__STL_TEMPLATE_NULL struct __type_traits<float> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<double> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<long double> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
/*以下是一個針對原生指針的偏特化版本*/
template <class _Tp>
struct __type_traits<_Tp*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
__STL_TEMPLATE_NULL struct __type_traits<char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<signed char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<unsigned char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<const char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<const signed char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
__STL_TEMPLATE_NULL struct __type_traits<const unsigned char*> {
typedef __true_type has_trivial_default_constructor;
typedef __true_type has_trivial_copy_constructor;
typedef __true_type has_trivial_assignment_operator;
typedef __true_type has_trivial_destructor;
typedef __true_type is_POD_type;
};
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
// The following could be written in terms of numeric_limits.
// We're doing it separately to reduce the number of dependencies.
template <class _Tp> struct _Is_integer {
typedef __false_type _Integral;
};
#ifndef __STL_NO_BOOL
__STL_TEMPLATE_NULL struct _Is_integer<bool> {
typedef __true_type _Integral;
};
#endif /* __STL_NO_BOOL */
__STL_TEMPLATE_NULL struct _Is_integer<char> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<signed char> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<unsigned char> {
typedef __true_type _Integral;
};
#ifdef __STL_HAS_WCHAR_T
__STL_TEMPLATE_NULL struct _Is_integer<wchar_t> {
typedef __true_type _Integral;
};
#endif /* __STL_HAS_WCHAR_T */
__STL_TEMPLATE_NULL struct _Is_integer<short> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<unsigned short> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<int> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<unsigned int> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<long> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<unsigned long> {
typedef __true_type _Integral;
};
#ifdef __STL_LONG_LONG
__STL_TEMPLATE_NULL struct _Is_integer<long long> {
typedef __true_type _Integral;
};
__STL_TEMPLATE_NULL struct _Is_integer<unsigned long long> {
typedef __true_type _Integral;
};
#endif /* __STL_LONG_LONG */
#endif /* __TYPE_TRAITS_H */
// Local Variables:
// mode:C++
// End:
總結
1. Traits程式設計技法對疊代器加以規範，獲得了對象的類型相關資訊，進而使得算法可以通過類型資訊來優化效率。
2. 使用重載函數來解決if-else條件在編譯時期和運作時期的不同步，使其能在編譯時期确認調用哪個函數。
3. SGI對traits進行擴充，使得所有類型都滿足traits程式設計規範，這樣SGI STL算法可以通過__type_traits擷取類型資訊後。
![STL源碼剖析 3、疊代器概念與traits程式設計技法疊代器Traits程式設計技法——STL源代碼門鑰iterator源代碼完整重列SGI STL的私房菜 __type_traits[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)