【文档说明】面向对象的程序设计方法第六讲STL剖析与高效编程课件.ppt，共(54)页，575.986 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44867.html

以下为本文档部分文字说明：

面向对象的程序设计方法第六讲STL剖析与高效编程课件内容提要1、抽象容器剖析(string,vector,list,deque,hash_map)2、泛型算法剖析：以sort()为例，类型参数化，容器参数化，操作参数化，

函数对象，适配器3、模板与泛型算法编程4、STL高效编程规则5、Boost库简介1.1std::stringtypedefbasic_string<char>string;template<classChar

Type,classTraits=char_traits<CharType>,classAllocator=allocator<CharType>>classbasic_string//参数CharTypeTheda

tatypeofasinglecharactertobestoredinthestring.TheStandardC++Libraryprovidestwospecializationsofthistemplateclass,withthetypedefinitionsstring,forelem

entsoftypechar,andwstring,forelementsoftypewchar_t.TraitsVariousimportantpropertiesoftheCharTypeelementsinaba

sic_stringspecializationaredescribedbytheclassTraits.AllocatorThetypethatrepresentsthestoredallocatorobjectthaten

capsulatesdetailsaboutthestring'sallocationanddeallocationofmemory.Thedefaultvalueisallocator<Type>.缺省字符属性char_traitstemplate<classCharType>struct

char_traits;char_traits<char>可以帮助转换char_traits<char>::char_typech1='x';char_traits<char>::char_typech2='y';//Converti

ngfromchar_typetoint_typechar_traits<char>::int_typeint1,int2,int3;int1=char_traits<char>::to_int_type(ch1);int2=char

_traits<char>::to_int_type(ch2);cout<<"Thechar_typesandcorrespondingint_typesare:"<<"\nch1="<<ch1<<"correspondingtoint1="<<int1<<"."<<"\nc

h2="<<ch2<<"correspondingtoint1="<<int2<<"."Thechar_typesandcorrespondingint_typesare:ch1=xcorrespondingtoint1=120.ch2=ycorrespondin

gtoint1=121basic_string在实现过程(append,insert…)中调用char_traits<char>的静态成员static_Elem*__cdeclcopy(_Elem*_First1,const

_Elem*_First2,size_t_Count){//copy[_First1,_First1+_Count)to[_First2,...)return(::wmemcpy(_First1,_First2,_Coun

t));}static_Elem*__cdeclmove(_Elem*_First1,const_Elem*_First2,size_t_Count){//copy[_First1,_First1+_Count)to[_First2,...)return(:

:wmemmove(_First1,_First2,_Count));}static_Elem*__cdeclassign(_Elem*_First,size_t_Count,_Elem_Ch){//assign_Count*_Chto[_First,...)return(::wmem

set(_First,_Ch,_Count));}……char_traits最终调用重载函数inlinechar*wmemcpy(char*_S1,constchar*_S2,size_t_N)；inlinechar*wmemmove(c

har*_S1,constchar_t*_S2,size_t_N)；inlinechar*wmemset(char*_S,char_t_C,size_t_N)；inlinewchar_t*wmemcpy(wchar_t*_S1,const

wchar_t*_S2,size_t_N)；inlinewchar_t*wmemmove(wchar_t*_S1,constwchar_t*_S2,size_t_N)；inlinewchar_t*wmemset(wchar_t*_S,wchar_t_C,size_t_N)；缺省内存分配

器template<classType>classallocator内存分配器：allocatorvoidstring::Copy(size_type_Newsize,size_type_Oldlen){//copy_Oldlenelementstonewl

yallocatedbuffer…_Elem*_Ptr;_TRY_BEGIN_Ptr=_Mybase::_Alval.allocate(_Newres+1);//callnew_CATCH_ALL_Newres=_N

ewsize;//allocationfailed,undoroundupandretry_TRY_BEGIN_Ptr=_Mybase::_Alval.allocate(_Newres+1);//callnew…_CATCH_ALL_Tidy(true);//failed

again,discardstorageandreraise_RERAISE;_CATCH_END_CATCH_ENDif(0<_Oldlen)_Traits::copy(_Ptr,_Myptr(),_Oldlen);//copyexistingelements…_Bx._P

tr=_Ptr;_Myres=_Newres;}string真正的数据union_Bxty{//storageforsmallbufferorpointertolargerone_Elem_Buf[_BUF_SIZE];

_Elem*_Ptr;}_Bx;size_type_Mysize;//currentlengthofstringsize_type_Myres;//currentstoragereservedforstringMyres:存储量，可以使用开始设定，否则缺省_Elem*_Myptr(){/

/determinecurrentpointertobufferformutablestringreturn(_BUF_SIZE<=_Myres?_Bx._Ptr:_Bx._Buf);}1.2std::vectorte

mplate<class_Ty,class_Alloc>class_Vector_val{//baseclassforvectortoholdallocator_Alvalprotected:_Vector_val(_Alloc_Al=_Alloc()):_Alval(_Al){//constr

uctallocatorfrom_Al}typedeftypename_Alloc::templaterebind<_Ty>::other_Alty;_Alty_Alval;//allocatorobjectforv

alues};//TEMPLATECLASSvectortemplate<class_Ty,class_Ax=allocator<_Ty>>classvector:public_Vector_val<_Ty,_Ax>{//varying

sizearrayofvaluespublic:…pointer_Myfirst;//pointertobeginningofarraypointer_Mylast;//pointertocurrentendofsequencepointer_My

end;//pointertoendofarray};push_back也是通过insert(end(),val)实现内存连续allocator::allocate(n)insertvoid_Insert_n(iterator_Where,size_type_Count,const_

Ty&_Val){//insert_Count*_Valat_Where_Ty_Tmp=_Val;//incase_Valisinsequencesize_type_Capacity=capacity();if(_Count==0);elseif(max_size()

-size()<_Count)_Xlen();//resulttoolongelseif(_Capacity<size()+_Count){//notenoughroom,reallocate_Capacity=max_size()-_C

apacity/2<_Capacity?0:_Capacity+_Capacity/2;//trytogrowby50%if(_Capacity<size()+_Count)_Capacity=size()+_Count;pointer_Newve

c=this->_Alval.allocate(_Capacity);pointer_Ptr=_Newvec;_TRY_BEGIN_Ptr=_Ucopy(_Myfirst,_ITER_BASE(_Where)

,_Newvec);//copyprefix_Ptr=_Ufill(_Ptr,_Count,_Tmp);//addnewstuff_Ucopy(_ITER_BASE(_Where),_Mylast,_Ptr);//copysuffi

x_CATCH_ALL_Destroy(_Newvec,_Ptr);this->_Alval.deallocate(_Newvec,_Capacity);_RERAISE;_CATCH_END_Count+=size();insertif(_Myfirst!=0){//destroyanddeal

locateoldarray_Destroy(_Myfirst,_Mylast);this->_Alval.deallocate(_Myfirst,_Myend-_Myfirst);}_Myend=_Newvec+_Capacity;_Mylast=_Newvec+_Count;_M

yfirst=_Newvec;}elseif((size_type)(_Mylast-_ITER_BASE(_Where))<_Count){//newstuffspillsoffend_Ucopy(_ITER_BASE(_W

here),_Mylast,_ITER_BASE(_Where)+_Count);//copysuffix_TRY_BEGIN_Ufill(_Mylast,_Count-(_Mylast-_ITER_BASE(

_Where)),_Tmp);//insertnewstuffoffend_CATCH_ALL_Destroy(_ITER_BASE(_Where)+_Count,_Mylast+_Count);_RERAISE;_CATCH_E

ND_Mylast+=_Count;fill(_ITER_BASE(_Where),_Mylast-_Count,_Tmp);//insertuptooldend}else{//newstuffcanallbeassignedpointer_Oldend=_Mylast;_Mylas

t=_Ucopy(_Oldend-_Count,_Oldend,_Mylast);//copysuffixcopy_backward(_ITER_BASE(_Where),_Oldend-_Count,_Oldend);//copyholefill(_ITER_BASE(_W

here),_ITER_BASE(_Where)+_Count,_Tmp);//insertintohole}}Std::vector::iteratorclassconst_iterator:public_Ranit<_

Ty,_Dift,_Ctptr,const_reference>{//iteratorfornonmutablevectorpublic:const_referenceoperator*()const

{//returndesignatedobjectreturn(*_Myptr);}_Ctptroperator->()const{//returnpointertoclassobjectreturn

(&**this);}const_iteratoroperator++(int){//postincrementconst_iterator_Tmp=*this;++*this;return(_Tmp);}const_iterato

r&operator--(){//predecrement--_Myptr;return(*this);}……_Tptr_Myptr;//offsetofelementinvector};1.3std::list//T

EMPLATECLASS_List_nodtemplate<class_Ty,class_Alloc>class_List_nod{//baseclassfor_List_ptrtoholdallocator_Alnodprotected:st

ruct_Node;friendstruct_Node;typedeftypename_Alloc::templaterebind<_GENERIC_BASE>::other::pointer_Genpt

r;struct_Node{//listnode_Node(_Genptr_Nextarg,_Genptr_Prevarg,const_Ty&_Myvalarg):_Next(_Nextarg),_Prev(_Pre

varg),_Myval(_Myvalarg){//constructanodewithvalue}_Genptr_Next;//successornode,orfirstelementifhead_Genptr_Prev;//predecessornode,orlastelementifhea

d_Ty_Myval;//thestoredvalue,unusedifhead};_List_nod(_Alloc_Al):_Alnod(_Al){//constructallocatorfrom_Al}typename_Alloc::templaterebind<_

Node>::other_Alnod;//allocatorobjectfornodes};Std::list//TEMPLATECLASS_List_valtemplate<class_Ty,class_Alloc>class_Lis

t_val:public_List_ptr<_Ty,_Alloc>{//baseclassforlisttoholdallocator_Alvalprotected:typedeftypename_Alloc::templaterebind<_Ty>::other_Alty;_List_val

(_Alloc_Al=_Alloc()):_List_ptr<_Ty,_Alloc>(_Al),_Alval(_Al){//constructbase,andallocatorfrom_Al}_Alty_Alval;//

allocatorobjectforvaluesstoredinnodes};//TEMPLATECLASSlisttemplate<class_Ty,class_Ax=allocator<_Ty>>classlist:pu

blic_List_val<_Ty,_Ax>{//bidirectionallinkedlist…public:_Nodeptr_Myhead;//pointertoheadnodesize_type_Mysize;//numberofelements};Std::list:

:insertvoid_Insert(iterator_Where,const_Ty&_Val){//insert_Valat_Where_Nodeptr_Pnode=_Where._Mynode();_Nodeptr_Newnode=_B

uynode(_Pnode,_Prevnode(_Pnode),_Val);_Incsize(1);_Prevnode(_Pnode)=_Newnode;_Nextnode(_Prevnode(_Newnode))=_Newnode;}_Nodeptr_Buynode(_Nodeptr_N

ext,_Nodeptr_Prev,const_Ty&_Val){//allocateanodeandsetlinksandvalue_Nodeptr_Pnode=this->_Alnod.allocate(1);_TRY_B

EGINnew((void*)_Pnode)_Node(_Next,_Prev,_Val);_CATCH_ALLthis->_Alnod.deallocate(_Pnode,1);_RERAISE;_CATCH_E

NDreturn(_Pnode);}Std::list::iteratorclassconst_iterator:public_Bidit<_Ty,_Dift,_Ctptr,const_reference>{//iteratorfornon

mutablelistpublic:const_referenceoperator*()const{//returndesignatedvaluereturn(_Myval(_Ptr));}_Ctptroperator->()const{//retur

npointertoclassobjectreturn(&**this);}const_iterator&operator++(){//preincrement_Ptr=_Nextnode(_Ptr);return(*this);}const_ite

rator&operator--(){//predecrement_Ptr=_Prevnode(_Ptr);return(*this);}…protected:_Nodeptr_Ptr;//pointertonode};1.4st

d::deque//TEMPLATECLASS_Deque_maptemplate<class_Ty,class_Alloc>class_Deque_map{//ultimatebaseclassfordequetoholdallocator_Almapprotected:_Deque_ma

p(_Alloc_Al):_Almap(_Al){//constructallocatorfrom_Al}typedeftypename_Alloc::templaterebind<_Ty>::other::pointer_Tptr

;typename_Alloc::templaterebind<_Tptr>::other_Almap;//allocatorobjectformaps};//TEMPLATECLASS_Deque_valtemplate<class_Ty,class_Alloc>class_Deque_v

al:public_Deque_map<_Ty,_Alloc>{//baseclassfordequetoholdallocator_Alvalprotected:_Deque_val(_Alloc_Al=_Alloc()):_Deque_map<_Ty,_Alloc>(_Al),

_Alval(_Al){//constructallocatorandbasefrom_Al}typedeftypename_Alloc::templaterebind<_Ty>::other_Alty;_Alty_Alv

al;//allocatorobjectforstoredelements};//TEMPLATECLASSdequetemplate<class_Ty,class_Ax=allocator<_Ty>>classdeque:

public_Deque_val<_Ty,_Ax>{//circularqueueofpointerstoblockspublic:…iterator&operator++(){//preincrement++this->_Myoff;return(*this);}iteratorope

rator++(int){//postincrementiterator_Tmp=*this;++*this;return(_Tmp);}iterator&operator--(){//predecrement--this->_Myoff;return(*this);}……_Mapptr

_Map;//pointertoarrayofpointerstoblockssize_type_Mapsize;//sizeofmaparraysize_type_Myoff;//offsetofinitiale

lementsize_type_Mysize;//currentlengthofsequence};Deque::push_frontvoidpush_front(const_Ty&_Val){//in

sertelementatbeginningif(_Myoff%_DEQUESIZ==0&&_Mapsize<=(_Mysize+_DEQUESIZ)/_DEQUESIZ)_Growmap(1);size_type_Newoff=_Myoff!=0?_Myoff:_Mapsize*_D

EQUESIZ;size_type_Block=--_Newoff/_DEQUESIZ;if(_Map[_Block]==0)_Map[_Block]=this->_Alval.allocate(_DEQUESIZ);this->_Alval.construct

(_Map[_Block]+_Newoff%_DEQUESIZ,_Val);_Myoff=_Newoff;++_Mysize;}Push_backvoidpush_back(const_Ty&_Val){//inserteleme

ntatendif((_Myoff+_Mysize)%_DEQUESIZ==0&&_Mapsize<=(_Mysize+_DEQUESIZ)/_DEQUESIZ)_Growmap(1);size_type_Newoff=_Myoff+_Mysize;size_ty

pe_Block=_Newoff/_DEQUESIZ;if(_Mapsize<=_Block)_Block-=_Mapsize;if(_Map[_Block]==0)_Map[_Block]=this->_Alval.al

locate(_DEQUESIZ);this->_Alval.construct(_Map[_Block]+_Newoff%_DEQUESIZ,_Val);++_Mysize;}Growmapvoid_Gro

wmap(size_type_Count){//growmapby_Countpointersif(max_size()/_DEQUESIZ-_Mapsize<_Count)_Xlen();//resulttoolongsize_type_Inc=_Mapsize/2

;//trytogrowby50%if(_Inc<_DEQUEMAPSIZ)_Inc=_DEQUEMAPSIZ;if(_Count<_Inc&&_Mapsize<=max_size()/_DEQUESIZ-_Inc)_

Count=_Inc;size_type_Myboff=_Myoff/_DEQUESIZ;_Mapptr_Newmap=this->_Almap.allocate(_Mapsize+_Count);_Mapptr_Myptr=_Newmap+

_Myboff;_Myptr=_Uninitialized_copy(_Map+_Myboff,_Map+_Mapsize,_Myptr,this->_Almap);//copyinitialtoendif(_Myboff<=_Coun

t){//incrementgreaterthanoffsetofinitialblock_Myptr=_Uninitialized_copy(_Map,_Map+_Myboff,_Myptr,this->_Almap);//copyrestofold_Uninitialize

d_fill_n(_Myptr,_Count-_Myboff,(_Tptr)0,this->_Almap);//clearsuffixofnew_Uninitialized_fill_n(_Newmap,_Myboff,(_Tptr)0,this->_Alm

ap);//clearprefixofnew}else{//incrementnotgreaterthanoffsetofinitialblock_Uninitialized_copy(_Map,_Map+_Coun

t,_Myptr,this->_Almap);//copymoreold_Myptr=_Uninitialized_copy(_Map+_Count,_Map+_Myboff,_Newmap,this->_Alm

ap);//copyrestofold_Uninitialized_fill_n(_Myptr,_Count,(_Tptr)0,this->_Almap);//clearresttoinitialblock}_Destroy_range(_Map+_Myboff,_Map+_

Mapsize,this->_Almap);if(_Map)this->_Almap.deallocate(_Map,_Mapsize);//freestorageforold_Map=_Newmap;//pointatnew_Mapsi

ze+=_Count;}insertiteratorinsert(iterator_Where,const_Ty&_Val){//insert_Valat_Whereif(_Where==begin()){//insertatfrontp

ush_front(_Val);return(begin());}elseif(_Where==end()){//insertatbackpush_back(_Val);return(end()-1);}e

lse{//insertinsidesequenceiterator_Mid;size_type_Off=_Where-begin();_Ty_Tmp=_Val;//incase_Valisinseq

uenceif(_Off<_Mysize/2){//closertofront,pushtofrontthencopypush_front(front());_Mid=begin()+_Off;copy(begin()+2,_Mid+1,beg

in()+1);}else{//closertoback,pushtobackthencopypush_back(back());_Mid=begin()+_Off;copy_backward(_Mid,end()

-2,end()-1);}*_Mid=_Tmp;//storeinsertedvaluereturn(_Mid);}}1.5std::hash_map//TEMPLATECLASShash_maptemplate<class_Kty,c

lass_Ty,class_Tr=hash_compare<_Kty,_STDless<_Kty>>,class_Alloc=_STDallocator<_STDpair<const_Kty,_Ty>>>classhash_map:public_Hash<_Hmap_tr

aits<_Kty,_Ty,_Tr,_Alloc,false>>{//hashtableof{key,mapped}values,uniquekeys…};//TEMPLATECLASS_Hashtemplate<class

_Traits>class_Hash:public_Traits//traitsservesasbaseclass{//hashtable--listwithvectorofiteratorsforquickaccessPublic:…_Mylist_List;//thelistofeleme

nts,mustinitializebefore_Vec_Myvec_Vec;//thevectoroflistiterators};Hash_map::insert_Pairibinsert(const

value_type&_Val){//trytoinsertnodewithvalue_Valiterator_Plist,_Where;if(_Maxidx<=size()/bucket_size){//toodense,needtogrowhashtableif(_Vec.size()-

1<=_Maxidx){//tablefull,doubleitssize_Mask=((_Vec.size()-1)<<1)-1;_Vec.resize(_Mask+2,end());}elseif(_Mask<_Maxidx)_Mask=(_Mask<<1)+1;size_type

_Bucket=_Maxidx-(_Mask>>1)-1;for(_Plist=_Vec[_Bucket];_Plist!=_Vec[_Bucket+1];){//splitoldbucketsize_type_Newb

ucket=this->comp(this->_Kfn(*_Plist))&_Mask;if(_Newbucket==_Bucket)++_Plist;//leaveelementinoldbucketelse{//moveelementtonewbucketsize_type_I

dx;iterator_Pnext=_Plist;if(++_Pnext!=end()){//notatend,moveitfor(_Idx=_Bucket;_Plist==_Vec[_Idx];--_Idx){//updateenditerat

orsifmovingfirst_Vec[_Idx]=_Pnext;if(_Idx==0)break;}_List._Splice(end(),_List,_Plist,_Pnext,0);_Plist=--end();_Vec[_Maxidx+1]=end(

);}for(_Idx=_Maxidx;_Bucket<_Idx;--_Idx){//updateenditeratorsifnewbucketfilledif(_Vec[_Idx]!=end())break;_Vec[_Idx]=_Plist;}if(_Pnext==end())break;

else_Plist=_Pnext;}}++_Maxidx;//opennewbucketforhashlookup}size_type_Bucket=_Hashval(this->_Kfn(_Val));for(_Plist=_Vec[_Bucket+1];_Plist!=_Vec[_Buc

ket];)if(this->comp(this->_Kfn(_Val),this->_Kfn(*--_Plist)));//stilltoohighinbucketlistelseif(this->comp(this->_Kfn

(*_Plist),this->_Kfn(_Val))){//foundinsertionpoint,backuptoit++_Plist;break;}elseif(_Multi)break;//equivalent,insertonlyifmultielsereturn

(_Pairib(_Plist,false));//alreadypresent_Where=_List.insert(_Plist,_Val);//insertnewelementfor(;_Plist==_V

ec[_Bucket];--_Bucket){//updateenditeratorsifnewfirstbucketelement_Vec[_Bucket]=_Where;if(_Bucket==0)break;}return(

_Pairib(_Where,true));//returniteratorfornewelement}Hash_map::finditeratorfind(constkey_type&_Keyval){//findanelementinm

utablehashtablethatmatches_Keyvalreturn(lower_bound(_Keyval));}iteratorlower_bound(constkey_type&_Keyval){//findleftmos

tnotlessthan_Keyvalinmutablehashtablesize_type_Bucket=_Hashval(_Keyval);iterator_Where;for(_Where=_Vec[_B

ucket];_Where!=_Vec[_Bucket+1];++_Where)if(!this->comp(this->_Kfn(*_Where),_Keyval))return(this->comp(_Keyval,this->_Kfn(*_Where))?end():_Where);ret

urn(end());}2、泛型算法剖析以排序sort()为例整数数组排序（从小到大）：sort(intx[]);类型参数化数组排序：sort(Typex[]);容器参数化：sort(iteratorit1

,iteratorit2);从大到小，还是从小到大：sort(iteratorit1,iteratorit2,bool(*compare)());函数对象：sort(iteratorit1,iteratorit2,

less<type>);其他泛型算法：find_if(),count_if(),for_each(),…函数对象适配器3、模板与泛型算法编程4、STL高效编程规则Item1:尽量使用iterator取代const_iterator、reverse_ite

rator和const_reverse_iteratorSTL中的所有标准容器类都提供四种不同的迭代器类型。对于容器类container<T>而言，iterator的功用相当于T*，而const_iterator则相当于constT*（可能你也见到过Tconst*这样的写法

，它们具有相同的语义[2]）。累加一个iterator或者const_iterator可以由首至尾的遍历一个容器内的所有元素。reverse_iterator与const_reverse_iterator同样分

别对应于T*和constT*，所不同的是，累加reverse_iterator或者const_reverse_iterator所产生的是由容器的尾端开始的反向遍历。不同容器的insert和erase方法虽然可能具有截然不同

的返回类型，但它们的参数形式却大都与此类似。需要注意的是：这些方法仅接受iterator类型的参数，而不是const_iterator、reverse_iterator或者const_reverse_iterator。虽然容器类支持四种不同的迭代器

类型，但其中iterator似乎有更为广泛的应用四种不同的迭代器类型转换可以隐式的将iterator转换成const_iterator或者reverse_iterator，也可以隐式的将reverse_iterator转换成const_reverse_iterator。并，

reverse_iterator可以通过调用其base()成员函数转换为iterator。const_reverse_iterator也可以类似的通过base()转换成为const_iterator。•大多数ins

ert和erase方法要求使用iterator。如果你需要调用这些方法，你就必须使用iterator。•没有一条简单有效的途径可以将const_iterator转换成iterator，我们将会在原则二中讨论的技术并不普遍适用，而且效率不彰。

•从reverse_iterator转换而来的iterator在使用之前可能需要相应的调整，在原则三种我们会讨论何时需要调整以及调整的原因。Item2:使用distance和advance将const_iterator转换成iterator原则一

中指出容器类的部分方法仅接受iterator作为参数，而不是const_iterator。那么，如何在一个const_iterator指出的容器位置上插入新元素呢？换言之，如何通过一个const_iterator得到指向容器中相同位置的iterator呢？由于并不存在

从const_iterator到iterator之间的隐式转换，你必须自己找到一条转换的途径。嗨，我知道你在想什么！“每当无路可走的时候，就举起强制类型转换的大旗！”。在C++的世界里，强制类型转换似乎总是最后的杀手锏。老实说，这恐怕算不上什么好主意——真不知道你是

哪儿学来的。const_iterator转换成iteratortypedefdeque<int>IntDeque;//typedef,简化代码。typedefIntDeque::iteratorIter;typedefIntDeque

::const_iteratorConstIter;ConstIterci;//const_iteratorIteri(ci);//编译错误！//没有隐式转换途径！Iteri(const_cast<Iter>(ci));//编译错误！//转换不能成立！typedefdeque<in

t>IntDeque;typedefIntDeque::iteratorIter;typedefIntDeque::const_iteratorConstIter;IntDequed;ConstIterci;...//ci指向d。Iteri(d.begin());//指向d的起始位置。advan

ce(i,distance(i,ci));//调整i，指向ci位置。Item3:正确理解如何使用通过base()得到的iteratorvector<int>v;for(inti=0；i<5;++i){//插入1到5v.push_back(i);}vector<int>::reverse_

iteratorri=//使ri指向3find(v.rbegin(),v.rend(),3);vector<int>::iteratori(ri.base());//取得i.rbegin()与end()、rend()与begin()之间存在一个元素的偏移，并且

ri与i之间仍然保留了这种偏移。插入与删除不一样·如果要在一个reverse_iterator指出的位置上插入新元素，只需通过base()得到相应的iterator然后调用insert方法即可。对于insert操作而言，re

verse_iterator与通过其base()方法得到的iterator是完全等价的。·如果要删除一个reverse_iterator指向的元素，需要通过base()得到相应的iterator，并且删除此ite

rator所指向的前一位值的元素。对于erase操作而言，reverse_iterator与通过其base()方法得到的iterator并非完全等价。插入与删除只支持iteratorvector<in

t>v;...//插入1到5，同上vecot<int>::reverse_iteratorri=find(v.rbegin(),v.rend(),3);//ri指向3v.insert(ri.base(),99);vector<int>v;...//插入1

到5，同上vecot<int>::reverse_iteratorri=find(v.rbegin(),v.rend(),3);//ri指向3v.erase((++ri).base());Item4：如何将vector和str

ing的数据传给传统的API已经存在的传统C风格的API接受的是数组和char*指针，而不是vector和string对象。这样的API函数还将会存在很长时间，如果我们要高效使用STL的话，就必须和它们和平共处。可以：如果

你有一个vector对象v，而你需要得到一个指向v中数据的指针，以使得它可以被当作一个数组，只要使用&v[0]就可以了。对于string对象s，相应的咒语是简单的s.c_str()。vector<int>v;voiddoSomething(cons

tint*pInts,size_tnumInts);doSomething(&v[0],v.size());//有问题if(!v.empty()){doSomething(&v[0],v.size());}如果走错路了，你可能会碰到一些半吊子

的人物，他们会告诉你说可以用v.begin()代替&v[0]，因为（这些讨厌的家伙将会告诉你）begin返回指向vector内部的迭代器，而对于vector，其迭代器实际上是指针。那经常是正确的，但正如条款50所说，并不总

是如此，你不该依赖于此。begin的返回类型是iterator，而不是一个指针，当你需要一个指向vector内部数据的指针时绝不该使用begin。如果你基于某些原因决定键入v.begin()，就应该键入&*v.begin()，因为这将会产生和&v[0]相同的指针。由string到constc

har*类似从vector上获取指向内部数据的指针的方法，对string不是可靠的，因为（1）string中的数据并没有承诺被存储在连续内存中，（2）string的内部表示形式并没承诺以一个null字符结束。voiddoSomething(constchar*pStrin

g);象这样：doSomething(s.c_str());即使是字符串的长度为0，它都能工作。在那种情况下，c_str将返回一个指向null字符的指针。即使字符串内部自己内含null时，它同样能工作。但是，如果真的这样，doSomething很可能将第一个内含的null解释为字符串结

束。string对象不在意是否容纳了结束符，但基于char*的C风格API在意。API调用修改值在两种形式下，指针都被传递为指向const的指针。vector和string的数据只能传给只读取而不修改它的API。这到目前为止都是最安全的事情。对于string

，这也是唯一可做的，因为没有承诺说c_str产生的指针指在string数据的内部表示形式上；它可以返回一个指针指向数据的一个不可修改的拷贝，这个拷贝满足C风格API对格式的要求。对于vector，有更多一点点灵活性。如果你将v传给一个修改其元素的C风格API的话，典型情况都是没问题，

但被调用的函数绝不能试图改变vector中元素的个数。String则不能这样，可以这样：size_tfillString(char*pArray,size_tarraySize);vector<cha

r>vc(maxNumChars);//建立一个vector，//它的大小是maxNumCharssize_tcharsWritten=fillString(&vc[0],vc.size());//让fillString把数据写入vcstrings(vc.begin(),vc.be

gin()+charsWritten);//从vc通过范围构造函数Item5:永远让比较函数对相等的值返回falseset<int,less_equal<int>>s;//s以“<=”排序s.insert(1

0);//插入10现在尝试再插入一次10：s.insert(10);//由less_equal测试10A和10B是否等价!(10A<=10B)&&!(10B<=10A)哦，10A和10B都是10，因此，10A<=10B肯定为真。同样清楚的是，10B<=10

A。于是上述的表达式简化为!(true)&&!(true)即false&&false结果当然是false。于是插入第二个10！所以：让比较函数对相等的值返回falseItem6:STL泛型算法vs.手写的循环list<Widget>lw;...for(list<Widget>::ite

ratori=lw.begin();i!=lw.end();++i){i->redraw();}但是你也可以用for_each()泛型算法:for_each(lw.begin(),lw.end(),mem_fun_ref(&Widget::redraw));

调用泛型算法通常比手写的循环更优越。为什么？有三个理由:l效率：泛型算法通常比循环高效。l正确性:写循环时比调用泛型算法更容易产生错误。l可维护性:与相应的显式循环相比，泛型算法通常使代码更干净、更直观。Item7:尽量用成员函数代替同名的算法有些容器拥有和S

TL算法同名的成员函数。关联容器提供了count、find、lower_bound、upper_bound和equal_range，而list提供了remove、remove_if、unique、sort、merge和reverse。大多数情况下，你应该用成员函数代替算法。这样做有

两个理由。首先，成员函数更快。其次，比起算法来，它们与容器结合得更好（尤其是关联容器）。set<int>s;//建立set，放1,000,000个数据...//进去set<int>::iteratori=s.find(727);//使用f

ind成员函数if(i!=s.end())...set<int>::iteratori=find(s.begin(),s.end(),727);//使用find算法if(i!=s.end())...两种

情况的算法效率find成员函数运行花费对数时间，所以不管727是否存在于此set中，set::find只需执行不超过40次比较来查找它，而一般只需要大约20次。相反，find算法运行花费线性时间，所

以如果727不在此set中，它需要执行1,000,000次比较。即使727在此set中，也平均需要执行500,000次比较来找到它。效率得分如下：find成员：大约40（最坏的情况）至大约20（平均情况）

find算法：1,000,000（最坏的情况）至500,000（平均情况）尽量用成员函数代替同名的算法成员函数的行为和它们的算法兄弟的行为经常不相同。正如条款32所解释的，如果你真的想用算法函数从容器中清除对象的话，

调用remove、remove_if和unique算法后，必须紧接着调用erase函数；但容器成员函数的remove、remove_if和unique成员函数真的去掉了元素，后面不需要接着调用erase。还有，如在sort算法和list的sort成员函数间的一

个重要区别是前者不能用于list。作为单纯的双向迭代器，list的迭代器不能传给sort算法。merge算法和list的merge成员函数之间也同样存在巨大差异。这个算法被限制为不能修改源范围，但list::merge总是修改它的宿主

list。Item8:STL搜索算法的区别你要寻找什么，而且你有一个容器或者你有一个由迭代器划分出来的区间——你要找的东西就在里面。你要怎么完成搜索呢？你箭袋中的箭有这些：count、count_if、find、find_if、binary_search、lower

_bound,upper_bound和equal_range。面对着它们，你要怎么做出选择？无序区间如果你有一个无序区间，你的选择是count或着find。它们分别可以回答略微不同的问题，所以值得仔细去区分它们。count回答的

问题是：“是否存在这个值，如果有，那么存在几份拷贝？”而find回答的问题是：“是否存在，如果有，那么它在哪儿？”算法效率：线性时间复杂度if(count(lw.begin(),lw.end(),

w)!=0)...if(find(lw.begin(),lw.end(),w)!=lw.end()){count这个惯用方法编码起来比较简单。但是，当搜索成功时，它的效率比较低，因为当找到匹配的值后find就停止了，而count必须继续搜索，直到区间的结尾以寻找其他匹

配的值。已序空间对于已序区间，你有其他的选择，而且你应该明确的使用它们。count和find是线性时间的，但已序区间的搜索算法（binary_search、lower_bound、upper_bound和equ

al_range）是对数时间的。从无序区间迁移到已序区间导致了另一个迁移：从使用相等来判断是否两个值相同到使用等价[2]。那是因为count和find算法都用相等来搜索，而binary_search、lower_bound、upper_bound和equal_range则用等价。binary_

search：只能回答“它在吗？”vector<Widget>vw;//建立vector，放入数据，sort(vw.begin(),vw.end());//把数据排序Widgetw;//要找的值...if(binary_search(vw.begin()

,vw.end(),w)){。。。Lower_bound()当你用lower_bound来寻找一个值的时候，它返回一个迭代器，这个迭代器指向这个值的第一个拷贝（如果找到的话）或者到可以插入这个值的位置（如果没找到）。因此

lower_bound回答这个问题：“它在吗？如果是，第一个拷贝在哪里？如果不是，它将在哪里？”和find一样，你必须测试lower_bound的结果，来看看它是否指向你要寻找的值。但又不像find，你不能只是检测lower_bound的返回值是否等于end迭代器。取而代之的是，你必须检测l

ower_bound所标示出的对象是不是你需要的值。vector<Widget>::iteratori=lower_bound(vw.begin(),vw.end(),w);if(i!=vw.end()&&*i==w){/

/保证i指向一个对象；??lower_boundtemplate<classForwardIterator,classType>ForwardIteratorlower_bound(ForwardIteratorfirst,ForwardIterat

orlast,constType&value);template<classForwardIterator,classType,classCompare>ForwardIteratorlower_bound(ForwardI

teratorfirst,ForwardIteratorlast,constType&value,Comparecomp);lower_bound()返回一个iterator，它指向在[first,last)标记的有序序列中可以插入value而不会破坏容器顺序的

第一个位置。而这个位置标记了一个大于等于value的值。例如已知下列序列intia[]={12,15,17,19,20,22,23,26,29,35,40,51};用值21调用lower_bound()返回一个指向值22的iterator；用值22调用lower_bound(

)也返回一个指向值22的iterator第一个版本使用底层类型的小于操作符；第二个版，根据comp对元素进行排序和比较。upper_bound()upper_bound()返同一个iterator，它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器

顺序的最后一个位置。这个位置标记了一个大于value的值。例如已知序列intia[]={12,15,17,19,20,22,23,26,29,35,40,51};用值21调用upper_bound()返回一个指向值22的iterator，用值22调用up

per_bound()则返回一个指向值23的iterator。第一个版本使用底层类型的小于（等于）操作符；而第二个版本根据comp对元素进行排序和比较。equal_rangeequal_range返

回一对迭代器，第一个等于lower_bound返回的迭代器，第二个等于upper_bound返回的（也就是，等价于要搜索值区间的末迭代器的下一个）。因此，equal_range，返回了一对划分出了和你要搜索的值等价的区间的迭代器。一个名字很好的

算法，不是吗？对于equal_range的返回值，有两个重要的地方。第一，如果这两个迭代器相同，就意味着对象的区间是空的；这个只没有找到。这个结果是用equal_range来回答“它在吗？”这个问题的答案。你可以这么用：vector<Widget>vw;...sort(vw.begin()

,vw.end());typedefvector<Widget>::iteratorVWIter;//方便的typedeftypedefpair<VWIter,VWIter>VWIterPair;VWIterPairp=equal_r

ange(vw.begin(),vw.end(),w);if(p.first!=p.second){//如果equal_range不返回空的区间通过equal_range可以得到数目第二个要注意的是equal_range返回的东西是两个迭代器，对它们作d

istance就等于区间中对象的数目，也就是，等价于要寻找的值的对象。结果，equal_range不光完成了搜索已序区间的任务，而且完成了计数。比如说，要在vw中找到等价于w的Widget，然后打印出来有多少这样的Widge

t存在，你可以这么做：VWIterPairp=equal_range(vw.begin(),vw.end(),w);cout<<"Thereare"<<distance(p.first,p.second)<<"elementsinvwequivalenttow.

";小结搜索5、Boost库简介