1、STL就是Standard Template Library，標準模板庫。這可能是一個歷史上最令人興奮的工具的最無聊的術(shù)語。從根本上說，STL是一些“容器”的集合，這些“容器”有l(wèi)ist, vector,set,map等，STL也是算法和其它一些組件的集合。這里的“容器”和算法的集合指的是世界上很多聰慧人很多年的杰作。是C標準庫的一個重要組成部分，它由Stepanov and Lee等人最先開發(fā)，它是與C幾乎同時開頭開發(fā)的；一開頭STL選擇了Ada作為實現(xiàn)語言，但Ada有點不爭氣，最后他們選擇了C，C中已經(jīng)有了模板。STL又被添加進了C庫。1996年，惠普公司又免費公開了STL，為STL的推廣

2、做了很大的貢獻。STL供應(yīng)了類型平安、高效而易用特性的STL無疑是最值得C+程序員高傲的部分。每一個C程序員都應(yīng)該好好學(xué)習(xí)STL。大體上包括container（容器）、algorithm（算法）和iterator（迭代器），容器和算法通過迭代器可以進行無縫連接。 一、基礎(chǔ)知識1、泛型技術(shù)泛型技術(shù)的實現(xiàn)方法有多種，比如模板，多態(tài)等。模板是編譯時決定，多態(tài)是運行時決定，其他的比如RTTI也是運行時確定。多態(tài)是依靠虛表在運行時查表實現(xiàn)的。比如一個類擁有虛方法，那么這個類的實例的內(nèi)存起始地址就是虛表地址，可以把內(nèi)存起始地址強制轉(zhuǎn)換成int*，取得虛表，然后(int*)*(int*)取得虛表里的第一個函

3、數(shù)的內(nèi)存地址，然后強制轉(zhuǎn)換成函數(shù)類型，即可調(diào)用來驗證虛表機制。泛型編程（generic programming，以下直接以GP稱呼）是一種全新的程序設(shè)計思想，和OO，OB，PO這些為人所熟知的程序設(shè)計想法不同的是GP抽象度更高，基于GP設(shè)計的組件之間偶合度底，沒有繼承關(guān)系，所以其組件間的互交性和擴展性都特別高。我們都知道，任何算法都是作用在一種特定的數(shù)據(jù)結(jié)構(gòu)上的，最簡潔的例子就是快速排序算法最根本的實現(xiàn)條件就是所排序的對象是存貯在數(shù)組里面，由于快速排序就是由于要用到數(shù)組的隨機存儲特性，即可以在單位時間內(nèi)交換遠距離的對象，而不只是相臨的兩個對象，而如果用聯(lián)表去存儲對象，由于在聯(lián)表中取得對象的時間

4、是線性的即On，這樣將使快速排序失去其快速的特點。也就是說，我們在設(shè)計一種算法的時候，我們總是先要考慮其應(yīng)用的數(shù)據(jù)結(jié)構(gòu)，比如數(shù)組查找，聯(lián)表查找，樹查找，圖查找其核心都是查找，但由于作用的數(shù)據(jù)結(jié)構(gòu)不同將有多種不同的表現(xiàn)形式。數(shù)據(jù)結(jié)構(gòu)和算法之間這樣親密的關(guān)系始終是我們以前的生疏。泛型設(shè)計的根本思想就是想把算法和其作用的數(shù)據(jù)結(jié)構(gòu)分離，也就是說，我們設(shè)計算法的時候并不去考慮我們設(shè)計的算法將作用于何種數(shù)據(jù)結(jié)構(gòu)之上。泛型設(shè)計的抱負狀態(tài)是一個查找算法將可以作用于數(shù)組，聯(lián)表，樹，圖等各種數(shù)據(jù)結(jié)構(gòu)之上，變成一個通用的，泛型的算法。2、四種類型轉(zhuǎn)換操作符static_cast 將一個值以符合規(guī)律的方式轉(zhuǎn)換。應(yīng)用到

5、類的指針上，意思是說它允許子類類型的指針轉(zhuǎn)換為父類類型的指針（這是一個有效的隱式轉(zhuǎn)換），同時，也能夠執(zhí)行相反動作：轉(zhuǎn)換父類為它的子類。例如：float x; Countstatic_cast(x);/把x作為整型值輸出 dynamic_cast 將多態(tài)類型向下轉(zhuǎn)換為其實際靜態(tài)類型。只用于對象的指針和引用。當(dāng)用于多態(tài)類型時，它允許任意的隱式類型轉(zhuǎn)換以及相反過程。dynamic_cast會檢查操作是否有效。也就是說，它會檢查轉(zhuǎn)換是否會返回一個被懇求的有效的完整對象。檢測在運行時進行。如果被轉(zhuǎn)換的指針不是一個被懇求的有效完整的對象指針，返回值為NULL. 例如：class Car; class Ca

6、briolet:public Car ; class Limousline:public Car ; void f(Car *cp) Cabriolet *p = dynamic_cast cp; reinterpret_cast 轉(zhuǎn)換一個指針為其它類型的指針。它也允許從一個指針轉(zhuǎn)換為整數(shù)類型。反之亦然。這個操作符能夠在非相關(guān)的類型之間轉(zhuǎn)換。操作結(jié)果只是簡潔的從一個指針到別的指針的值的二進制拷貝。在類型之間指向的內(nèi)容不做任何類型的檢查和轉(zhuǎn)換。例如：class A ;class B ;A * a = new A;B * b = reinterpret_cast(a); const_cast一般用

7、于強制消除對象的常量性。例如：class C ;const C *a = new C;C *b = const_cast(a);其它三種操作符是不能修改一個對象的常量性的。 3、explicit修飾的構(gòu)造函數(shù)不能擔(dān)當(dāng)轉(zhuǎn)換函數(shù)。在很多情況下，隱式轉(zhuǎn)換是有意的，并且是正當(dāng)?shù)摹５袝r我們不盼望進行這種自動的轉(zhuǎn)換。例如：為了避開這樣的隱式轉(zhuǎn)換，應(yīng)該象下面這樣顯式聲明該帶單一參數(shù)的構(gòu)造函數(shù)：class String int size;char *p;/.public: / 不要隱式轉(zhuǎn)換 explicit String (int sz); String (const char *s, int size n

8、 = 0); / 隱式轉(zhuǎn)換;void f () String s(10); s = 100; / 現(xiàn)在編譯時出錯；需要顯式轉(zhuǎn)換： s = String(100); / 好；顯式轉(zhuǎn)換 s = st; / 好；此時允許隱式轉(zhuǎn)換 4、命名空間namespace 解決在使用不同模塊和程序庫時，消失名稱沖突問題。5、C+標準程序庫中的通用工具。由類和函數(shù)構(gòu)成。這些工具包括： 數(shù)種通用類型 一些重要的C函數(shù) 數(shù)值極值 二、STL六大組件容器（Container）算法（Algorithm）迭代器（Iterator）仿函數(shù)（Function object）適配器（Adaptor）空間配置器（allocator

9、）1、容器作為STL的最主要組成部分容器，分為向量（vector），雙端隊列(deque)，表(list)，隊列（queue），堆棧(stack)，集合(set)，多重集合(multiset)，映射(map)，多重映射(multimap)。容器特性所在頭文件向量vector可以用常數(shù)時間訪問和修改任意元素，在序列尾部進行插入和刪除時，具有常數(shù)時間簡單度，對任意項的插入和刪除就有的時間簡單度與到末尾的距離成正比，尤其對向量頭的添加和刪除的代價是驚人的高的雙端隊列deque基本上與向量相同，唯一的不同是，其在序列頭部插入和刪除操作也具有常量時間簡單度表list對任意元素的訪問與對兩端的距離成正比，

10、但對某個位置上插入和刪除一個項的花費為常數(shù)時間。隊列queue插入只可以在尾部進行，刪除、檢索和修改只允許從頭部進行。依據(jù)先進先出的原則。堆棧stack堆棧是項的有限序列，并滿足序列中被刪除、檢索和修改的項只能是最近插入序列的項。即依據(jù)后進先出的原則集合set由節(jié)點組成的紅黑樹，每個節(jié)點都包含著一個元素，節(jié)點之間以某種作用于元素對的謂詞排列，沒有兩個不同的元素能夠擁有相同的次序，具有快速查找的功能。但是它是以犧牲插入刪除操作的效率為代價的多重集合multiset和集合基本相同，但可以支持重復(fù)元素具有快速查找能力映射map由鍵，值對組成的集合，以某種作用于鍵對上的謂詞排列。具有快速查找能力多重集

11、合multimap比起映射，一個鍵可以對應(yīng)多了值。具有快速查找能力STL容器能力表： 2、算法算法部分主要由頭文件，和組成。是全部STL頭文件中最大的一個，它是由一大堆模版函數(shù)組成的，可以認為每個函數(shù)在很大程度上都是獨立的，其中常用到的功能范 圍涉及到比較、交換、查找、遍歷操作、復(fù)制、修改、移除、反轉(zhuǎn)、排序、合并等等。體積很小，只包括幾個在序列上面進行簡潔數(shù)學(xué)運算的模板函數(shù)，包括加法和乘法在序列上的一些操作。中則定義了一些模板類，用以聲明函數(shù)對象。STL的算法也是特別優(yōu)秀的，它們大部分都是類屬的，基本上都用到了C的模板來實現(xiàn)，這樣，很多相像的函數(shù)就不用自己寫了，只要用函數(shù)模板就可以了。我們使用

12、算法的時候，要針對不同的容器，比如：對集合的查找，最好不要用通用函數(shù)find（），它對集合使用的時候，性能特別的差，最好用集合自帶的find（）函數(shù)，它針對了集合進行了優(yōu)化，性能特別的高。 3、迭代器它的簡略實現(xiàn)在中，我們完全可以不管迭代器類是怎么實現(xiàn)的，大多數(shù)的時候，把它理解為指針是沒有問題的（指針是迭代器的一個特例，它也屬于迭代器），但是，決不能完全這么做。迭代器功能輸入迭代器Input iterator向前讀Reads forwardistream輸出迭代器Output iterator向前寫Writes forwardostream,inserter前向迭代器Forward itera

13、tor向前讀寫Read and Writes forward 雙向迭代器Bidirectional iterator向前向后讀寫Read and Writes forward andbackwardlist,set,multiset,map,multimap隨機迭代器Random access iterator隨機讀寫Read and Write with randomaccessvector,deque,array,string 4、仿函數(shù)仿函數(shù)，又或叫做函數(shù)對象，是STL六大組件之一；仿函數(shù)雖然小，但卻極大的拓展了算法的功能，幾乎全部的算法都有仿函數(shù)版本。例如，查找算法find_if就是對

14、find算法的擴展，標準的查找是兩個元素相等就找到了，但是什么是相等在不憐憫況下卻需要不同的定義，如地址相等，地址和郵編都相等，雖然這些相等的定義在變，但算法本身卻不需要轉(zhuǎn)變，這都多虧了仿函數(shù)。仿函數(shù)(functor)又稱之為函數(shù)對象（function object），其實就是重載了()操作符的struct，沒有什么特別的地方。如以下代碼定義了一個二元推斷式functor：struct IntLessbool operator()(int left, int right) const return (left right);為什么要使用仿函數(shù)呢？1).仿函數(shù)比一般的函數(shù)敏捷。2).仿函數(shù)有類型

15、識別，可以作為模板參數(shù)。3).執(zhí)行速度上仿函數(shù)比函數(shù)和指針要更快的。怎么使用仿函數(shù)？除了在STL里，別的地方你很少會看到仿函數(shù)的身影。而在STL里仿函數(shù)最常用的就是作為函數(shù)的參數(shù)，或者模板的參數(shù)。在STL里有自己預(yù)定義的仿函數(shù)，比如全部的運算符，=，-，*，、比如號的仿函數(shù)是lesstemplatestruct less : public binary_function / functor for operator bool operator()(const _Ty& _Left, const _Ty& _Right) const / apply operator to operands re

16、turn (_Left _Right); ;從上面的定義可以看出，less從binary_function繼承來的，那么binary_function又是什么的？templatestruct binary_function / base class for binary functions typedef _Arg1 first_argument_type; typedef _Arg2 second_argument_type; typedef _Result result_type;其實binary_function只是做一些類型聲明而已，別的什么也沒做，但是在STL里為什么要做這些呢？如果

17、你要閱讀過STL的源碼，你就會發(fā)現(xiàn)，這樣的用法很多，其實沒有別的目的，就是為了便利，平安，可復(fù)用性等。但是既然STL里面內(nèi)定如此了，所以作為程序員你必必要遵循這個規(guī)章,否則就別想平安的使用STL。比如我們自己定一個仿函數(shù)?？梢赃@樣：template class func_equal :public binary_function inline bool operator()(type1 t1,type2 t2) const/這里的const不能少 return t1 = t2;/當(dāng)然這里要overload= 我們看這一行： inline bool operator()(type1 t1,typ

18、e2 t2) const/這里的const不能少inline是聲明為內(nèi)聯(lián)函數(shù)，我想這里應(yīng)該不用多說什么什么了，關(guān)鍵是為什么要聲明為const的？要想找到緣由還是看源碼，加入如果我們這里寫一行代碼，find_if(s.begin(),s.end(),bind2nd(func_equal(),temp),在bind2nd函數(shù)里面的參數(shù)是const類型的，const類型的對象，只能訪問cosnt修飾的函數(shù)！與binary_function(二元函數(shù))相對的是unary_function(一元函數(shù)),其用法同binary_functionstruct unary_function typedef _A

19、 argument_type; typedef _R result_type; ;注：仿函數(shù)就是重載()的class，并且重載函數(shù)要為const的，如果要自定義仿函數(shù)，并且用于STL接配器，那么肯定要從binary_function或者，unary_function繼承。 5、適配器適配器是用來修改其他組件接口的STL組件，是帶有一個參數(shù)的類模板（這個參數(shù)是操作的值的數(shù)據(jù)類型）。STL定義了3種形式的適配器：容器適配器，迭代器適配器，函數(shù)適配器。容器適配器：包括棧（stack）、隊列(queue)、優(yōu)先(priority_queue)。使用容器適配器，stack就可以被實現(xiàn)為基本容器類型（ve

20、ctor,dequeue,list）的適配。可以把stack看作是某種特別的vctor,deque或者list容器，只是其操作仍然受到stack本身屬性的限制。queue和priority_queue與之類似。容器適配器的接口更為簡潔，只是受限比一般容器要多。迭代器適配器：修改為某些基本容器定義的迭代器的接口的一種STL組件。反向迭代器和插入迭代器都屬于迭代器適配器，迭代器適配器擴展了迭代器的功能。函數(shù)適配器：通過轉(zhuǎn)換或者修改其他函數(shù)對象使其功能得到擴展。這一類適配器有否定器（相當(dāng)于非操作）、綁定器、函數(shù)指針適配器。函數(shù)對象適配器的作用就是使函數(shù)轉(zhuǎn)化為函數(shù)對象，或是將多參數(shù)的函數(shù)對象轉(zhuǎn)化為少參

21、數(shù)的函數(shù)對象。例如：在STL程序里，有的算法需要一個一元函數(shù)作參數(shù)，就可以用一個適配器把一個二元函數(shù)和一個數(shù)值，綁在一起作為一個一元函數(shù)傳給算法。 例如： find_if(coll.begin(), coll.end(), bind2nd(greater (), 42); 這句話就是找coll中第一個大于42的元素。 greater ()，其實就是號，是一個2元函數(shù) bind2nd的兩個參數(shù)，要求一個是2元函數(shù)，一個是數(shù)值，結(jié)果是一個1元函數(shù)。bind2nd就是個函數(shù)適配器。 6、空間配置器STL的內(nèi)存配置器在我們的實際應(yīng)用中幾乎不用涉及，但它卻在STL的各種容器背后悄悄做了大量的工作，STL

22、內(nèi)存配置器為容器安排并管理內(nèi)存。統(tǒng)一的內(nèi)存管理使得STL庫的可用性、可移植行、以及效率都有了很大的提升。SGI-STL的空間配置器有2種，一種僅僅對c語言的malloc和free進行了簡潔的封裝，而另一個設(shè)計到小塊內(nèi)存的管理等，運用了內(nèi)存池技術(shù)等。在SGI-STL中默認的空間配置器是其次級的配置器。SGI使用時std:alloc作為默認的配置器。A）alloc把內(nèi)存配置和對象構(gòu)造的操作分開，分別由alloc:allocate()和:construct()負責(zé)，同樣內(nèi)存釋放和對象析夠操作也被分開分別由alloc:deallocate()和:destroy()負責(zé)。這樣可以保證高效，由于對于內(nèi)存安

23、排釋放和構(gòu)造析夠可以依據(jù)簡略類型(type traits)進行優(yōu)化。比如一些類型可以直接使用高效的memset來初始化或者忽視一些析構(gòu)函數(shù)。對于內(nèi)存安排alloc也供應(yīng)了2級安排器來應(yīng)對不憐憫況的內(nèi)存安排。B）第一級配置器直接使用malloc()和free()來安排和釋放內(nèi)存。其次級視情況接受不同的策略：當(dāng)需求內(nèi)存超過128bytes的時候，視為足夠大，便調(diào)用第一級配置器；當(dāng)需求內(nèi)存小于等于128bytes的時候便接受比較簡單的memeory pool的方式管理內(nèi)存。C）無論allocal被定義為第一級配置器還是其次級，SGI還為它包裝一個接口，使得配置的接口能夠符合標準即把配置單位從byte

24、s轉(zhuǎn)到了元素的大?。?templateclass simple_allocpublic: static T* allocate(size_t n) return 0 = n ? 0 : (T*)Alloc:allocate(n * sizeof(T); static T* allocate(void) return (T*) Alloc:allocate(sizeof(T); static void deallocate(T* p, size_t n) if (0 != n) Alloc:deallocate(p, n * sizeof(T); static void deallocate(T

25、* p) Alloc:deallocate(p, sizeof(T); d）內(nèi)存的基本處理工具，它們均具有commt or rollback能力。templateForwardIteratoruninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result); templatevoid uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x); templateForwardIteratoruninit

26、ialized_fill_n(ForwardIterator first, ForwardIterator last, const T& x) 三、簡略容器、算法1、全部容器都供應(yīng)了一個默認的構(gòu)造函數(shù)，一個拷貝構(gòu)造函數(shù)。例如：list l;.vector ivector(l.begin(),l.end(); int array=1,2,3,4;.set iset(array,array+sizeof(array)/sizeof(array0); 2、與大小相關(guān)的函數(shù)size(),empty(),max_size()3、返回迭代器的函數(shù)begin(),end(),rbegin(),rend()4

27、、比較操作=,!=,=. Vector詳解：capacity(),返回vector能夠容納的元素個數(shù)。size(),返回vector內(nèi)現(xiàn)有元素的個數(shù)。賦值操作：c1=c2; 把c2的全部元素指派給c1c.assign(n,elem);復(fù)制n個elem，指派給cc.assign(beg,end);將區(qū)間beg，end內(nèi)的元素指派給cc1.s);將c1,c2元素互換s);同上元素存取c.at(index);cindex;c.front();返回第一個元素c.back(); 插入和刪除：c.insert(pos.elem);c.insert(pos,n.elem); 插入n個elemc.insert

28、(pos,beg,end); 在pos出插入beg，end區(qū)間內(nèi)的全部元素。c.push_back(elem);c.pop_back();c.erase(pos); 刪除pos上的元素，返回下一個元素c.erase(beg,end);c.resize(num);將元素數(shù)量改為num，如果size變大了，多出來的新元素都要一default方式構(gòu)建。c.resize(num,elem);將元素數(shù)量改為num，如果size變大了，多出來的新元素是elem的副本。c.clear();刪除全部。 vector的reserve和resizereserve只安排空間，而不創(chuàng)建對象，size()不變。而res

29、ize安排空間而且用空對象填充.reserve是容器預(yù)留空間，但并不真正創(chuàng)建元素對象，在創(chuàng)建對象之前，不能引用容器內(nèi)的元素，因此當(dāng)加入新的元素時，需要用push_back()/insert()函數(shù)。resize是轉(zhuǎn)變?nèi)萜鞯拇笮。⑶覄?chuàng)建對象，因此，調(diào)用這個函數(shù)之后，就可以引用容器內(nèi)的對象了，因此當(dāng)加入新的元素時，用operator操作符，或者用迭代器來引用元素對象。再者，兩個函數(shù)的形式是有區(qū)分的，reserve函數(shù)之后一個參數(shù)，即需要預(yù)留的容器的空間；resize函數(shù)可以有兩個參數(shù)，第一個參數(shù)是容器新的大小，其次個參數(shù)是要加入容器中的新元素，如果這個參數(shù)被省略，那么就調(diào)用元素對象的默認構(gòu)造函數(shù)

30、。vector有而deque無的：capacity(), reserve();deque有而vector無的：push_front(elem), pop_front(); push_back(elem), pop_back();STL供應(yīng)的另兩種容器queue、stack，其實都只不過是一種adaptor，它們簡潔地修飾deque的界面而成為另外的容器類型 List詳解：for_each (.begin(), .end(), “函數(shù)”);count (.begin(), .end(), 100, jishuqi);返回對象等于100的個數(shù)jishuqi值。count_if() 帶一個函數(shù)對象的

31、參數(shù)(上面“100”的這個參數(shù))。函數(shù)對象是一個至少帶有一個operator()方法的類。這個類可以更簡單。find(*.begin().*end(),“要找的東西”)；如果沒有找到指出的對象，就會返回*.end()的值，要是找到了就返回一個指著找到的對象的iteratorfine_if()；與count_if()類似，是find的更強大版本。STL通用算法search()用來搜尋一個容器，但是是搜尋一個元素串，不象find()和find_if() 只搜尋單個的元素。search算法在一個序列中找另一個序列的第一次消失的位置。search(A.begin(), A.end(), B.begin

32、(), B.end();在A中找B這個序列的第一次消失。要排序一個list，我們要用list的成員函數(shù)sort()，而不是通用算法sort()。list容器有它自己的sort算法，這是由于通用算法僅能為那些供應(yīng)隨機存取里面元素 的容器排序。list的成員函數(shù)push_front()和push_back()分別把元素加入到list的前面和后面。你可以使用insert() 把對象插入到list中的任何地方。insert()可以加入一個對象，一個對象的若干份拷貝，或者一個范圍以內(nèi)的對象。list成員函數(shù)pop_front()刪掉list中的第一個元素，pop_back()刪掉最后一個元素。函數(shù)era

33、se()刪掉由一個iterator指出的元素。還有另一個erase()函數(shù)可以刪掉一個范圍的元素。list的成員函數(shù)remove()用來從list中刪除元素。*.remove(要刪除的對象);通用算法remove()使用和list的成員函數(shù)不同的方式工作。一般情況下不轉(zhuǎn)變?nèi)萜鞯拇笮?。remove(*.begin(),*.end(),要刪除的對象);使用STL通用算法stable_partition()和list成員函數(shù)splice()來劃分一個list。stable_partition()是一個有味的函數(shù)。它重新排列元素，使得滿足指定條件的元素排在不滿足條件的元素前面。它維持著兩組元素的挨次關(guān)

34、系。splice 把另一個list中的元素結(jié)合到一個list中。它從源list中刪除元素。 Set Map詳解：STL map和set的使用雖不簡單，但也有一些不易理解的地方，如：為何map和set的插入刪除效率比用其他序列容器高？為何每次insert之后，以前保存的iterator不會失效？為何map和set不能像vector一樣有個reserve函數(shù)來預(yù)安排數(shù)據(jù)？當(dāng)數(shù)據(jù)元素增多時（10000到20000個比較），map和set的插入和搜尋速度變化如何？C+ STL中標準關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部接受的就是一種特別高效的平衡檢索二叉樹：紅黑樹，也成為

35、RB樹(Red-Black Tree)。RB樹的統(tǒng)計性能要好于一般的平衡二叉樹(AVL-樹).為何map和set的插入刪除效率比用其他序列容器高？大部分人說，很簡潔，由于對于關(guān)聯(lián)容器來說，不需要做內(nèi)存拷貝和內(nèi)存移動。說對了，確實如此。map和set容器內(nèi)全部元素都是以節(jié)點的方式來存儲，其節(jié)點結(jié)構(gòu)和鏈表差不多，指向父節(jié)點和子節(jié)點。這里的一切操作就是指針換來換去，和內(nèi)存移動沒有關(guān)系。為何每次insert之后，以前保存的iterator不會失效？(同解)為何map和set不能像vector一樣有個reserve函數(shù)來預(yù)安排數(shù)據(jù)？究其原理來說時，引起它的緣由在于在map和set內(nèi)部存儲的已經(jīng)不是元素本

36、身了，而是包含元素的節(jié)點。其實你就記住一點，在map和set內(nèi)面的安排器已經(jīng)發(fā)生了變化，reserve方法你就不要奢望了。當(dāng)數(shù)據(jù)元素增多時（10000和20000個比較），map和set的插入和搜尋速度變化如何？如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個答案。在map和set中查找是使用二分查找，也就是說，如果有16個元素，最多需要比較4次就能找到結(jié)果，有32個元素，最多比較5次。那么有10000個呢？最多比較的次數(shù)為log10000，最多為14次，如果是20000個元素呢？最多不過15次。 泛型算法：全部算法的前兩個參數(shù)都是一對iterators：first，last)，用來指出容器內(nèi)一個

37、范圍內(nèi)的元素。每個算法的聲明中，都表現(xiàn)出它所需要的最低層次的iterator類型。 常用算法：accumulate() 元素累加adjacent_difference() 相鄰元素的差額adjacent_find() 搜尋相鄰的重復(fù)元素binary_search() 二元搜尋copy() 復(fù)制copy_backward() 逆向復(fù)制count() 計數(shù)count_if() 在特定條件下計數(shù)equal() 推斷相等與否equal_range() 推斷相等與否（傳回一個上下限區(qū)間范圍）fill() 改填元素值fill_n() 改填元素值，n 次find() 搜尋find_if() 在特定條件下搜尋

38、find_end() 搜尋某個子序列的最后一次消失地點find_first_of() 搜尋某些元素的首次消失地點for_each() 對范圍內(nèi)的每一個元素施行某動作generate() 以指定動作的運算結(jié)果充填特定范圍內(nèi)的元素generate_n() 以指定動作的運算結(jié)果充填 n 個元素內(nèi)容includes() 涵蓋於inner_product() 內(nèi)積inplace_merge() 合并并取代（覆寫）iter_swap() 元素互換lexicographical_compare() 以字典排列方式做比較lower_bound() 下限max() 最大值max_element() 最大值所在位

39、置min() 最小值min_element() 最小值所在位置merge() 合并兩個序列mismatch() 找出不吻合點next_permutation() 獲得下一個排列組合泛型演算法（Generic Algorithms）與 Function Obje4 ctsnth_element() 重新支配序列中第n個元素的左右兩端partial_sort() 局部排序partial_sort_copy() 局部排序并復(fù)制到它處partial_sum() 局部總和partition() 切割prev_permutation() 獲得前一個排列組合random_shuffle() 隨機重排remo

40、ve() 移除某種元素（但不刪除）remove_copy() 移除某種元素并將結(jié)果復(fù)制到另一個 containerremove_if() 有條件地移除某種元素remove_copy_if() 有條件地移除某種元素并將結(jié)果復(fù)制到另一個 containerreplace() 取代某種元素replace_copy() 取代某種元素，并將結(jié)果復(fù)制到另一個 containerreplace_if() 有條件地取代replace_copy_if() 有條件地取代，并將結(jié)果復(fù)制到另一個 containerreverse() 顛倒元素次序reverse_copy() 顛倒元素次序并將結(jié)果復(fù)制到另一個 cont

41、ainerrotate() 旋轉(zhuǎn)rotate_copy() 旋轉(zhuǎn)，并將結(jié)果復(fù)制到另一個 containersearch() 搜尋某個子序列search_n() 搜尋連續(xù)發(fā)生 n 次的子序列set_difference() 差集set_intersection() 交集set_symmetric_difference() 對稱差集set_union() 聯(lián)集sort() 排序stable_partition() 切割并保持元素相對次序stable_sort() 排序并保持等值元素的相對次序swap() 置換（對調(diào)）s() 置換（指定范圍）transform() 以兩個序列為基礎(chǔ)，交互作用產(chǎn)生第三

42、個序列unique() 將重復(fù)的元素摺疊縮編，使成唯一unique_copy() 將重復(fù)的元素摺疊縮編，使成唯一，并復(fù)制到他處upper_bound() 上限 四、注意細節(jié)：1、auto_ptr 不能用new所生成的array作為初值，由于釋放內(nèi)存時用的是delete，而不是delete2、就搜尋速度而言，hash table通常比二叉樹還要快510倍。hash table不是C+標準程序庫的一員。3、迭代器使用過程中優(yōu)先選用前置式遞增操作符（+iter）而不是選擇后置式遞增操作符（iter+）。3、迭代器三個幫助函數(shù)：advance(),distance(),iter_swap()。 adv

43、ance()可令迭代器前進 distance()可處理迭代器之間的距離。 iter_swap()可交換兩個迭代器所指內(nèi)容。4、hasp函數(shù) makeheap()、push_heap()、pop_heap()、sort_heap()5、/0在string之中并不具有特別意義，但是在一般C形式的string中卻用來標記字符串結(jié)束。在string中，字符 /0和其他字符的地位完全相同。string中有三個函數(shù)可以將字符串內(nèi)容轉(zhuǎn)換成字符數(shù)組或C形式的string。data() 以字符數(shù)組的形式返回字符串內(nèi)容。但末未追加/0字符，返回類型并非有效的C形式string。c_str() 以C形式返回字符串內(nèi)

44、容（在末尾端添加/0字符）。copy() 將字符串內(nèi)容復(fù)制到“調(diào)用者供應(yīng)的字符數(shù)組”中，不添加/0字符。6、容器中用empty來代替檢查size是否為0；當(dāng)使用new得到指針的容器時，切記在容器銷毀前delete那些指針；千萬不要把auto_ptr放入容器中。7、盡量使用vector和string來代替動態(tài)申請的數(shù)組；避開使用vector，vector有兩個問題第一，它不是一個真正STL容器，其次，它并不保存bool類型。8、迭代器使用過程中，盡量使用iterator代替const_iterator，reverse_iterator和const_reverse_iterator；使用dista

45、nce和advance把const_iterators轉(zhuǎn)化成iterators。typedef deque IntDeque; / 和以前一樣typedef IntDeque:iterator Iter;typedef IntDeque:const_iterator ConstIter;IntDeque d;ConstIter ci;. / 讓ci指向dIter i(d.begin(); / 初始化i為d.begin()advance(i, distance(i, ci); / 調(diào)整i，指向ci位置9、避開對set和multiset的鍵值進行修改。10、永久讓比較函數(shù)對相同元素返回false。

46、11、排序選擇：1）如果你需要在vector、string、deque或數(shù)組上進行完全排序，你可以使用sort或stable_sort。2）如果你有一個vector、string、deque或數(shù)組，你只需要排序前n個元素，應(yīng)該用partial_sort。3）如果你有一個vector、string、deque或數(shù)組，你需要鑒別出第n個元素或你需要鑒別出最前的n個元素，而不用知道它們的挨次，nth_element是你應(yīng)該注意和調(diào)用的。4）如果你需要把標準序列容器的元素或數(shù)組分隔為滿足和不滿足某個標準，你也許就要找partition或stable_partition。5）如果你的數(shù)據(jù)是在list中，

47、你可以直接使用partition和stable_partition，你可以使用list的sort來代替sort和stable_sort。如果你需要partial_sort或nth_element供應(yīng)的效果，你就必須間接完成這個任務(wù)。12、如果你真的想刪除東西的話就在類似remove的算法后接上erase。remove從一個容器中remove元素不會轉(zhuǎn)變?nèi)萜髦性氐膫€數(shù)，erase是真正刪除東西。13、提防在指針的容器上使用類似remove的算法，在調(diào)用類似remove的算法前手動刪除和廢棄指針。14、盡量用成員函數(shù)代替同名的算法，有些容器擁有和STL算法同名的成員函數(shù)。關(guān)聯(lián)容器供應(yīng)了count

48、、find、lower_bound、upper_bound和equal_range，而list供應(yīng)了remove、remove_if、unique、sort、merge和reverse。大多數(shù)情況下，你應(yīng)該用成員函數(shù)代替算法。這樣做有兩個理由。首先，成員函數(shù)更快。其次，比起算法來，它們與容器結(jié)合得更好（尤其是關(guān)聯(lián)容器）。那是由于同名的算法和成員函數(shù)通常并不是是一樣的。15、容器中使用自定義的結(jié)構(gòu)體時，如果用到拷貝與賦值，結(jié)構(gòu)體需要重載operator=符號；比較容器分成相等與不等，相等時重載operator=符號，不等時重載operator符號。比如set、map、multiset、multi

49、map、priority_queue等容器類要求重載operator符號。16、Map/Multimap，Sets/Multisets都不能用push_back,push_front,由于它是自動排序的。Set內(nèi)的相同數(shù)值的元素只能消失一次，Multisets內(nèi)可包含多個數(shù)值相同的元素。Map內(nèi)的相同數(shù)值的元素只能消失一次，Multimap內(nèi)可包含多個數(shù)值相同的元素。內(nèi)部由二叉樹實現(xiàn)，便于查找。17、string 與 數(shù)字之間的轉(zhuǎn)換，轉(zhuǎn)換的方法有很多種，一般使用stringstream來實現(xiàn)轉(zhuǎn)換。比如：#include #include #include using namespace std

50、; int main() int i=0; string temp; stringstream s; /string轉(zhuǎn)換為數(shù)字 temp = “1234”; si; coutiendl; /數(shù)字轉(zhuǎn)換為string i=256; si; temp = s.str(); couttempend; system(pause); return 0; 18、對于自定義的結(jié)構(gòu)體，放入容器中，最好不要對容器進行內(nèi)存初始化（不要調(diào)用memset,zeromemory函數(shù)），否則如果結(jié)構(gòu)體中有指針類型的變量時，就會消失問題。 19、Vector的函數(shù)泄漏問題定義了一個struct temp char name2

51、56; int i;Vector vect;當(dāng)對這個vect執(zhí)行pushback一些temp的結(jié)構(gòu)體后，執(zhí)行clear這樣是否會內(nèi)存泄露？可以釋放掉temp結(jié)構(gòu)體中的name內(nèi)存嗎？解決方法：不行，clear只是把那些元素全部刪除掉，并不是釋放內(nèi)存。再者，你這樣的定義容器是不需要釋放內(nèi)存的，如果你這樣定義，std:vector *pVec。就需要了。先pVec-clear()再 pVec-swap( (std:vector )(*pVec) )。就能實現(xiàn)內(nèi)存的釋放。 20、stl之map erase方法的正確使用STL的map表里有一個erase方法用來從一個map中刪除掉指令的一個節(jié)點，不存

52、在任何問題。如果刪除多一個節(jié)點時，需要使用正確的調(diào)用方法。比如下面的方法是有問題：for(ITER iter=mapTest.begin();iter!=mapTest.end();+iter)coutfirst:secondendl;mapTest.erase(iter);這是一種錯誤的寫法,會導(dǎo)致程序行為不行知.究其緣由是map 是關(guān)聯(lián)容器,對于關(guān)聯(lián)容器來說，如果某一個元素已經(jīng)被刪除，那么其對應(yīng)的迭代器就失效了，不應(yīng)該再被使用；否則會導(dǎo)致程序無定義的行為。正確的使用方法：1).使用刪除之前的迭代器定位下一個元素。STL建議的使用方式for(ITER iter=mapTest.begin();iter!=mapTest.end();)cou