STL源碼剖析——迭代器 · STL源碼剖析

### 前言 ? 在STL的思想中，容器和算法是彼此獨立設計的，再通過某種方式使它們連接；而迭代器是使算法獨立于使用的容器類型，即迭代器是連接算法和容器的方法。由于迭代器是一種行為類似指針的對象，也就說迭代器是一種廣義指針，即迭代器對解除引用操作（operator*）和訪問成員操作（operator->）進行重載。然而要對這兩個操作符進行重載，對容器內部對象的數據類型和存儲結構有所了解，于是在 STL 中迭代器的最終實現都是由容器本身來實現的，每種容器都有自己的迭代器實現。本文介紹的不是針對某種特定的容器。在迭代器的設計中，一個最重要的編程技巧那就是Traits技術了，有關[《Traits編程技術》](http://blog.csdn.net/chenhanzhun/article/details/39230529)在前面博文中已經介紹了。 ### 迭代器 ### 迭代器的分類 ?在SGI STL中根據讀寫和訪問方式，在源碼中迭代器大致可分為五類： 1. 輸入迭代器input_iterator：只讀，且只能一次讀操作，支持操作：++p,p++,!=,==,=*p,p->； 1. 輸出迭代器output_iterator：只寫，且只能一次寫操作，支持操作：++p,p++； 1. 正向迭代器forward_iterator：可多次讀寫，支持輸入輸出迭代器的所有操作； 1. 雙向迭代器bidirectional_iterator：支持正向迭代器的所有操作，且支持操作：--p,--p； 1. 隨機訪問迭代器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; }; ~~~ ### 迭代器的型別與traits技巧 ? 在STL的算法設計中需要迭代器的型別，根據不同要求和不同型別，有不同的技巧解決；如：使用模板參數推導機制推導出局部變量類型；內嵌型別求出返回值類型；traits技術解決返回值類型和偏特化traits技術解決原生指針問題；這些都在前面博文[《Traits編程技術》](http://blog.csdn.net/chenhanzhun/article/details/39230529)介紹。迭代器的型別如下代碼所示： ~~~ 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； 1. 在函數調用時生成相應迭代器類型的臨時對象作為實參傳遞，編譯器就會調用相應的重載函數。 ? 為了重載函數識別，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: ~~~ ### SGI STL的__type_traits技術 ? 前面介紹的Traits技術在STL中彌補了C++模板的不足，但是在STL中，Traits技術只是用來規范迭代器，對于迭代器之外的東西沒有加以規范。因此，SGI將該技術擴展到迭代器之外的東西，稱為__type_traits。iterator_traits是萃取迭代器的特性，而__type_traits是萃取型別的特性。萃取的型別如下： 1. 是否具備non-trivial default ctor? 1. 是否具備non-trivial copy ctor? 1. 是否具備non-trivial assignment operator? 1. 是否具備non-trivial dtor? 1. 是否為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編程技法對迭代器加以規范，獲得了對象的類型相關信息，從而使得算法可以通過類型信息來優化效率。 1. 使用重載函數來解決if-else條件在編譯時期和運行時期的不同步，使其能在編譯時期確認調用哪個函數。 1. SGI對traits進行擴展，使得所有類型都滿足traits編程規范，這樣SGI STL算法可以通過__type_traits獲取類型信息后。參考文獻： [【1】](http://www.cnblogs.com/HappyAngel/archive/2011/04/19/2021413.html)，[【2】](http://ibillxia.github.io/blog/2014/06/21/stl-source-insight-2-iterators-and-traits/)，[【3】](http://www.xuebuyuan.com/1591997.html)