幫助整合-手冊1stl本文列出幾個基本STLmap和STLset問題通過解答這些

STLmapSTLsetSTL關(guān)聯(lián)容器UNIX/LINUXmap,set選擇問map,setSTLSTLmap等關(guān)聯(lián)容STLmapset#mapset#為何每次insert之后，以前保存的iterator不會失效#mapsetvectorreserve#，mapSTL的底層數(shù)據(jù)結(jié)構(gòu)。C++STLvector,string,list等方STLvector封裝數(shù)組，list封裝了鏈表，mapset封裝了二叉樹等，在封裝這些數(shù)據(jù)結(jié)構(gòu)的時候，STL讓用戶在STL使用過程中，并不會感到陌生。C++STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set,multiset,map,multimap內(nèi)部采用的就是一種非常高效的平衡二叉樹(有些書籍根據(jù)作者，Adelson-Velskii和Landis，將其稱為AVL-樹)，所以被STL選擇作為了關(guān)聯(lián)容器的內(nèi)部結(jié)構(gòu)。本文并不會介紹詳細(xì)AVLRB樹的實(shí)現(xiàn)以及他們的優(yōu)劣，關(guān)于RB樹的詳細(xì)實(shí)現(xiàn)參看樹:理論與實(shí)現(xiàn)(理論篇)。本文針對開始mapset的底層數(shù)據(jù)結(jié)構(gòu)。map和set實(shí)如此。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多，指向父節(jié)點(diǎn)節(jié)點(diǎn)。結(jié)構(gòu)圖可能如下：A/ /\/\DEFGOK為何每次insert之后，以前保存的iterator不會失，看見了上面答案的解釋，你應(yīng)該已經(jīng)可以很容易解釋這個問題。iterator這里就相當(dāng)于指向失效了)vectorpush_back在尾部插入也是如此。因?yàn)闉榱吮ＷC內(nèi)部數(shù)據(jù)的連續(xù)存放，iterator指向的那塊內(nèi)存在刪除和內(nèi)存已有的數(shù)據(jù)元素到新的內(nèi)存，最后把需要插入的元素放到最后，那么以前的內(nèi)存find等算法在一起使用的時候，牢記這個原則：不要使iterator。，map和set不能像vectorreserve我以前也這么問，究其原理來說時，引起它的原因在于在map和set內(nèi)部的已經(jīng)不是元素本身了，而是包含元素的節(jié)點(diǎn)。也就是說map的Alloc并不是map<Key,Compare,Alloc>的時候從參數(shù)中傳入的Alloc。例如：map<int,int,less<int>,Alloc<int>>intmap;intmapallocatorAlloc<int>,Alloc，具體轉(zhuǎn)換STLAllocatormapset內(nèi)面的分配器已經(jīng)發(fā)生了變化，reserve方法你就不要奢望了。，maplog2mapset中查找是使用二分查找，16432510000log100001420000151次，多1/14的搜索時間而已。你明白這個道理后，就可以安心往里面放入元素了。map和setWinter還要提的就是它們和一個c和linux平臺下，都有一個庫叫isc，里面就提供類似于以下的函數(shù)voidtree_init(voidvoid*tree_srch(void**tree,int(*compare)(),voidvoidtree_add(void**tree,int(*compare)(),void*data,void(*del_uar)());inttree_delete(void**tree,int(*compare)(),void*data,void(*del_uar)());inttree_trav(void**tree,int(*trav_uar)());voidtree_mung(void**tree,voidSTLmapSTLmap中使用了許多模板什么new會存在，而STL采用自己的Allocator分配內(nèi)存，以內(nèi)存池的方式來