STL容器-Traits與偏特化
Traits是STL中非常重要的一個(gè)技巧，主要是用來優(yōu)化性能粗井，在
STL空間配置器中有簡單介紹餐济，這里做一個(gè)更詳細(xì)的介紹；Traits主要有兩類：__type_traits和iterator_traits，對于構(gòu)造和析構(gòu)有著非常重要的作用螺捐，不過__type_traits就不是STL標(biāo)準(zhǔn)的東西了澜沟；前者負(fù)責(zé)處理萃取類型特性靖苇，后者負(fù)責(zé)萃取迭代器特性
__type_traits
__type_traits的意義主要是在構(gòu)造和析構(gòu)時(shí)決定急性怎么樣的操作埠忘，主要是為了優(yōu)化性能绰上；比如對于int這樣的類型來說，直接進(jìn)行內(nèi)存字節(jié)的操作即可，對于批量操作而言可以提升性能
__type_traits的定義
_STLP_TEMPLATE_NULL
struct __type_traits_aux<__false_type> {
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;
};
_STLP_TEMPLATE_NULL
struct __type_traits_aux<__true_type> {
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;
};
template <class _Tp>
struct __type_traits {
typedef __true_type this_dummy_member_must_be_first;
typedef __false_type has_trivial_default_constructor; //構(gòu)造函數(shù)是否有意義
typedef __false_type has_trivial_copy_constructor; //拷貝構(gòu)造函數(shù)是否有意義
typedef __false_type has_trivial_assignment_operator; //賦值運(yùn)算是否有意義
typedef __false_type has_trivial_destructor; //析構(gòu)函數(shù)是否有意義
typedef __false_type is_POD_type; //是否是pod類型
};
在type_traits.h中提供了一個(gè)默認(rèn)版本和兩個(gè)特定類型模板的實(shí)現(xiàn)，is_POD_type和has_trivial_assignment_operator在STL空間配置器-構(gòu)造析構(gòu)中有進(jìn)行說明，就以has_trivial_assignment_operator進(jìn)行進(jìn)一步的說明
has_trivial_assignment_operator
依舊以vector作為例子進(jìn)行說明，在進(jìn)行擴(kuò)容操作時(shí)通過has_trivial_assignment_operator判斷賦值運(yùn)算是否有意義，對于原聲的int類型之流的賦值運(yùn)算是沒有意義的，直接字節(jié)復(fù)制即可；不過即使賦值運(yùn)算有意義，這里調(diào)用的也不會是賦值運(yùn)算戴差，因?yàn)檫@是擴(kuò)容操作
-
插入元素時(shí)判斷賦值運(yùn)算是否有意義
void push_back(const _Tp& __x = _STLP_DEFAULT_CONSTRUCTED(_Tp)) { if (this->_M_finish != this->_M_end_of_storage._M_data) { _Copy_Construct(this->_M_finish, __x); ++this->_M_finish; } else { //擴(kuò)容時(shí)需要進(jìn)行內(nèi)容的復(fù)制纹磺，移動到新的地方 typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialCopy; _M_insert_overflow(this->_M_finish, __x, _TrivialCopy(), 1, true); } } -
在賦值操作有意義的情況下不能直接進(jìn)行字節(jié)操作了
void vector<_Tp, _Alloc>::_M_insert_overflow_aux(pointer __pos, const _Tp& __x, const __false_type& /*DO NOT USE!!*/, size_type __fill_len, bool __atend ) { typedef typename __type_traits<_Tp>::has_trivial_copy_constructor _TrivialUCopy; //這里是和移動構(gòu)造相關(guān)的讥珍，這里暫時(shí)不考慮這析氏义，_Movable視為__false_type即可 #if !defined (_STLP_NO_MOVE_SEMANTIC) typedef typename __move_traits<_Tp>::implemented _Movable; #endif size_type __len = _M_compute_next_size(__fill_len); //分配空間 pointer __new_start = this->_M_end_of_storage.allocate(__len, __len); pointer __new_finish = __new_start; _STLP_TRY { //復(fù)制數(shù)據(jù)到新的內(nèi)存中 __new_finish = _STLP_PRIV __uninitialized_move(this->_M_start, __pos, __new_start, _TrivialUCopy(), _Movable()); // ............. } template <class _InputIter, class _ForwardIter, class _TrivialUCpy> inline _ForwardIter __uninitialized_move(_InputIter __first, _InputIter __last, _ForwardIter __result, _TrivialUCpy __trivial_ucpy, const __false_type& /*_Movable*/) { return __ucopy_ptrs(__first, __last, __result, __trivial_ucpy); } -
拷貝構(gòu)造函數(shù)沒有意義的情況
template <class _InputIter, class _OutputIter> inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __true_type& /*TrivialUCopy*/) { // we know they all pointers, so this cast is OK // return (_OutputIter)__copy_trivial(&(*__first), &(*__last), &(*__result)); return (_OutputIter)__ucopy_trivial(__first, __last, __result); } inline void* __ucopy_trivial(const void* __first, const void* __last, void* __result) { //dums: this version can use memcpy (__copy_trivial can't) return (__last == __first) ? __result : ((char*)memcpy(__result, __first, ((const char*)__last - (const char*)__first))) + ((const char*)__last - (const char*)__first); }在賦值運(yùn)算沒有意義的時(shí)候可以直接進(jìn)行
memmove操作，因?yàn)橥ㄟ^內(nèi)存復(fù)制操作就可以移動到新的位置來使用筋岛；在拷貝構(gòu)造函數(shù)沒有意義的時(shí)候可以直接進(jìn)行memcpy操作柒傻，注意拷貝構(gòu)造函數(shù)沒有意義并不代表析構(gòu)函數(shù)沒有意義；賦值運(yùn)算和拷貝構(gòu)造的定義還是不一樣的 -
拷貝構(gòu)造函數(shù)有意義的情況
template <class _InputIter, class _OutputIter> inline _OutputIter __ucopy_ptrs(_InputIter __first, _InputIter __last, _OutputIter __result, const __false_type& /*TrivialUCopy*/) { return __ucopy(__first, __last, __result, random_access_iterator_tag(), (ptrdiff_t*)0); }在拷貝構(gòu)造函數(shù)有意義的情況下需要對所有數(shù)據(jù)分別執(zhí)行雌桑，但是這里有一個(gè)非常的問題就是怎么進(jìn)行遍歷操作，舉個(gè)栗子
for (_Distance __n = __last - __first; __n > 0; --__n) { _Param_Construct(&*__cur, *__first); ++__first; ++__cur; }這是一種常用的遍歷操作傲茄，但是
list類型就不支持這操作守呜，這就涉及到iterator_traits操作了
偏特化
對于內(nèi)置類型的特殊定義就是偏特化萍歉，內(nèi)置類型的這些traits就會被定義為__true_type
# define _STLP_DEFINE_TYPE_TRAITS_FOR(Type) \
_STLP_TEMPLATE_NULL struct __type_traits< Type > : __type_traits_aux<__true_type> {}; \
_STLP_TEMPLATE_NULL struct __type_traits< const Type > : __type_traits_aux<__true_type> {}; \
_STLP_TEMPLATE_NULL struct __type_traits< volatile Type > : __type_traits_aux<__true_type> {}; \
_STLP_TEMPLATE_NULL struct __type_traits< const volatile Type > : __type_traits_aux<__true_type> {}
# ifndef _STLP_NO_BOOL
_STLP_DEFINE_TYPE_TRAITS_FOR(bool);
iterator_traits
迭代器萃取器的意義
- 迭代器主要是容器和算法的中間介質(zhì)，
list和vector的迭代器支持的操作不一樣钧栖，對于算法而言同樣的算法內(nèi)部的寫法也可能不一樣啃奴，需要區(qū)分出不同的迭代器類型 - 在進(jìn)行查找操作時(shí)可能的需求就是最終返回迭代器的值，那就需要提供迭代器真正類型的定義；不是字符串，而是可以使用的符號定義
內(nèi)嵌型別
c++中是沒有運(yùn)行時(shí)獲取類型的方法的盏袄，唯一的方法就是typedef關(guān)鍵字到逊，但是迭代器是模板類需要為不同的類型提供不同的定義；這就用到了模板類內(nèi)嵌型別
#include <iostream>
using namespace std;
template<class T>
class TestA {
public:
typedef T value_type;
};
template<class T>
void func(T t) {
typename TestA<T>::value_type i = 1.3;
cout << i << endl;
}
int main() {
func(1.3);
return 0;
}
通過模板類加模板函數(shù)的方式就可以推導(dǎo)變量類型
iterator_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; // 被迭代類型的引用的類型
};
和__type_traits是具有很大不同的痊末，類型迭代器中定義的通常是_false_type和_true_type在運(yùn)行時(shí)通過不同的模板函數(shù)執(zhí)行不同的動作，實(shí)際上執(zhí)行的是if/else的判斷操作片吊；
template <class _Tp, class _Traits>
struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef typename _Traits::reference reference;
typedef typename _Traits::pointer pointer;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef value_type** _Map_pointer;
以上就是deque的迭代器定義
偏特化處理
在這里會存在一個(gè)問題就是
vector提供的是原生指針迭代器，而原生指針是無法進(jìn)行類似上面的操作的
template <class _Tp>
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;
};
STL中有為原生指針提供了針對指針的模板特殊實(shí)現(xiàn)
iterator_category
iterator_category就是用以規(guī)定一個(gè)迭代器支持的操作類型
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 {};
一共提供了5種類型的定義
-
所有迭代器均支持如下操作
p++ 后置自增迭代器 ++p 前置自增迭代器 TYPE(iter) 拷貝構(gòu)造所有迭代器均需要支持這兩種操作
-
input_iterator_tag*p 解引用讀取值 p->m 讀取元素成員 p1==p2 比較迭代器的是否相等 p1!=p1 比較迭代器的是否不等 -
output_iterator_tag*p=val 解引用賦值 -
forward_iterator_tagstruct forward_iterator_tag : public input_iterator_tag {}; 繼承于輸入迭代器 p1=p2 迭代器賦值 -
bidirectional_iterator_tagstruct bidirectional_iterator_tag : public forward_iterator_tag {}; --p 前置自減迭代器 p-- 后置自減迭代器 -
random_access_iterator_tagstruct random_access_iterator_tag : public bidirectional_iterator_tag {}; p+=i 將迭代器遞增i位 p-=i 將迭代器遞減i位 p+i 在p位加i位后的迭代器 p-i 在p位減i位后的迭代器 p[i] 返回p位元素偏離i位的元素引用 p1<p2 如果迭代器p的位置在p1前，返回true，否則返回false p1<=p2 p的位置在p1的前面或同一位置時(shí)返回true叨吮，否則返回false p1>p2 如果迭代器p的位置在p1后，返回true媚污，否則返回false p1>=p2 p的位置在p1的后面或同一位置時(shí)返回true朵锣，否則返回false p1-p2 返回迭代器之間的距離
vector/list的迭代器類型定義
-
vector提供的就是原聲指針，為random_access_iterator_tag類型汰聋，在偏特化中定義template <class _Tp> 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; }; -
list提供的時(shí)bidirectional_iterator_tag瞭郑，允許前后移動但不允許跳動struct _List_iterator_base { typedef size_t size_type; typedef ptrdiff_t difference_type; typedef bidirectional_iterator_tag iterator_category; _List_node_base* _M_node; _List_iterator_base(_List_node_base* __x) : _M_node(__x) {} void _M_incr() { _M_node = _M_node->_M_next; } void _M_decr() { _M_node = _M_node->_M_prev; } };
均符合偏特化的定義
uninitialized_copy的實(shí)現(xiàn)
_InputIter類型的復(fù)制函數(shù)
template <class _InputIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_InputIter __first, _InputIter __last,
_OutputIter __result, _Distance*) {
_OutputIter __cur = __result;
_STLP_TRY {
for ( ; __first != __last; ++__first, ++__cur)
_Param_Construct(&*__cur, *__first);
return __cur;
}
_STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __cur))
_STLP_RET_AFTER_THROW(__cur)
}
只能通過++運(yùn)算符移動
_RandomAccessIter的實(shí)現(xiàn)
template <class _RandomAccessIter, class _OutputIter, class _Distance>
inline _OutputIter __ucopy(_RandomAccessIter __first, _RandomAccessIter __last,
_OutputIter __result, const random_access_iterator_tag &, _Distance*) {
_OutputIter __cur = __result;
_STLP_TRY {
for (_Distance __n = __last - __first; __n > 0; --__n) {
_Param_Construct(&*__cur, *__first);
++__first;
++__cur;
}
return __cur;
}
_STLP_UNWIND(_STLP_STD::_Destroy_Range(__result, __cur))
_STLP_RET_AFTER_THROW(__cur)
}
可以通過減法來計(jì)算距離
