|
STL就是Standard Template Library,，標(biāo)準(zhǔn)模板庫(kù)。這可能是一個(gè)歷史上最令人興奮的工具的最無(wú)聊的術(shù)語(yǔ),。從根本上說(shuō),，STL是一些“容器”的集合，這些“容器”有list, vector,set,map等,，STL也是算法和其它一些組件的集合,。這里的“容器”和算法的集合指的是世界上很多聰明人很多年的杰作。是C＋＋標(biāo)準(zhǔn)庫(kù)的一個(gè)重要組成部分,，它由Stepanov and Lee等人最先開(kāi)發(fā),，它是與C＋＋幾乎同時(shí)開(kāi)始開(kāi)發(fā)的；一開(kāi)始STL選擇了Ada作為實(shí)現(xiàn)語(yǔ)言,，但Ada有點(diǎn)不爭(zhēng)氣,，最后他們選擇了C＋＋，C＋＋中已經(jīng)有了模板,。STL又被添加進(jìn)了C＋＋庫(kù),。1996年，惠普公司又免費(fèi)公開(kāi)了STL,，為STL的推廣做了很大的貢獻(xiàn),。STL提供了類(lèi)型安全、高效而易用特性的STL無(wú)疑是最值得C++程序員驕傲的部分,。每一個(gè)C＋＋程序員都應(yīng)該好好學(xué)習(xí)STL,。大體上包括container（容器）、algorithm（算法）和iterator（迭代器）,，容器和算法通過(guò)迭代器可以進(jìn)行無(wú)縫連接。
一,、基礎(chǔ)知識(shí) 1,、泛型技術(shù) 泛型技術(shù)的實(shí)現(xiàn)方法有多種,，比如模板，多態(tài)等,。模板是編譯時(shí)決定,，多態(tài)是運(yùn)行時(shí)決定，其他的比如RTTI也是運(yùn)行時(shí)確定,。多態(tài)是依靠虛表在運(yùn)行時(shí)查表實(shí)現(xiàn)的,。比如一個(gè)類(lèi)擁有虛方法，那么這個(gè)類(lèi)的實(shí)例的內(nèi)存起始地址就是虛表地址,，可以把內(nèi)存起始地址強(qiáng)制轉(zhuǎn)換成int*,，取得虛表，然后(int*)*(int*)取得虛表里的第一個(gè)函數(shù)的內(nèi)存地址,，然后強(qiáng)制轉(zhuǎn)換成函數(shù)類(lèi)型,，即可調(diào)用來(lái)驗(yàn)證虛表機(jī)制。 泛型編程（generic programming,，以下直接以GP稱(chēng)呼）是一種全新的程序設(shè)計(jì)思想,，和OO，OB,，PO這些為人所熟知的程序設(shè)計(jì)想法不同的是GP抽象度更高,，基于GP設(shè)計(jì)的組件之間偶合度底，沒(méi)有繼承關(guān)系,，所以其組件間的互交性和擴(kuò)展性都非常高,。我們都知道，任何算法都是作用在一種特定的數(shù)據(jù)結(jié)構(gòu)上的,，最簡(jiǎn)單的例子就是快速排序算法最根本的實(shí)現(xiàn)條件就是所排序的對(duì)象是存貯在數(shù)組里面,，因?yàn)榭焖倥判蚓褪且驗(yàn)橐玫綌?shù)組的隨機(jī)存儲(chǔ)特性，即可以在單位時(shí)間內(nèi)交換遠(yuǎn)距離的對(duì)象,，而不只是相臨的兩個(gè)對(duì)象,，而如果用聯(lián)表去存儲(chǔ)對(duì)象，由于在聯(lián)表中取得對(duì)象的時(shí)間是線性的即O[n],，這樣將使快速排序失去其快速的特點(diǎn),。也就是說(shuō)，我們?cè)谠O(shè)計(jì)一種算法的時(shí)候,，我們總是先要考慮其應(yīng)用的數(shù)據(jù)結(jié)構(gòu),，比如數(shù)組查找，聯(lián)表查找,，樹(shù)查找,，圖查找其核心都是查找，但因?yàn)樽饔玫臄?shù)據(jù)結(jié)構(gòu)不同將有多種不同的表現(xiàn)形式,。數(shù)據(jù)結(jié)構(gòu)和算法之間這樣密切的關(guān)系一直是我們以前的認(rèn)識(shí),。泛型設(shè)計(jì)的根本思想就是想把算法和其作用的數(shù)據(jù)結(jié)構(gòu)分離,，也就是說(shuō)，我們?cè)O(shè)計(jì)算法的時(shí)候并不去考慮我們?cè)O(shè)計(jì)的算法將作用于何種數(shù)據(jù)結(jié)構(gòu)之上,。泛型設(shè)計(jì)的理想狀態(tài)是一個(gè)查找算法將可以作用于數(shù)組,，聯(lián)表，樹(shù),，圖等各種數(shù)據(jù)結(jié)構(gòu)之上,，變成一個(gè)通用的，泛型的算法,。 2,、四種類(lèi)型轉(zhuǎn)換操作符 static_cast 將一個(gè)值以符合邏輯的方式轉(zhuǎn)換。應(yīng)用到類(lèi)的指針上,，意思是說(shuō)它允許子類(lèi)類(lèi)型的指針轉(zhuǎn)換為父類(lèi)類(lèi)型的指針（這是一個(gè)有效的隱式轉(zhuǎn)換）,，同時(shí)，也能夠執(zhí)行相反動(dòng)作：轉(zhuǎn)換父類(lèi)為它的子類(lèi),。 例如：float x; Count<<static_cast<int>(x);//把x作為整型值輸出
dynamic_cast 將多態(tài)類(lèi)型向下轉(zhuǎn)換為其實(shí)際靜態(tài)類(lèi)型,。只用于對(duì)象的指針和引用。當(dāng)用于多態(tài)類(lèi)型時(shí),，它允許任意的隱式類(lèi)型轉(zhuǎn)換以及相反過(guò)程,。dynamic_cast會(huì)檢查操作是否有效。也就是說(shuō),，它會(huì)檢查轉(zhuǎn)換是否會(huì)返回一個(gè)被請(qǐng)求的有效的完整對(duì)象,。檢測(cè)在運(yùn)行時(shí)進(jìn)行。如果被轉(zhuǎn)換的指針不是一個(gè)被請(qǐng)求的有效完整的對(duì)象指針,，返回值為NULL. 例如：class Car; class Cabriolet:public Car{ … }; class Limousline:public Car{ … }; void f(Car *cp) { Cabriolet *p = dynamic_cast< Cabriolet > cp; }
reinterpret_cast 轉(zhuǎn)換一個(gè)指針為其它類(lèi)型的指針,。它也允許從一個(gè)指針轉(zhuǎn)換為整數(shù)類(lèi)型。反之亦然,。這個(gè)操作符能夠在非相關(guān)的類(lèi)型之間轉(zhuǎn)換,。操作結(jié)果只是簡(jiǎn)單的從一個(gè)指針到別的指針的值的二進(jìn)制拷貝。在類(lèi)型之間指向的內(nèi)容不做任何類(lèi)型的檢查和轉(zhuǎn)換,。 例如： class A {};
const_cast一般用于強(qiáng)制消除對(duì)象的常量性,。 例如： class C {};
3,、explicit修飾的構(gòu)造函數(shù)不能擔(dān)任轉(zhuǎn)換函數(shù),。在很多情況下，隱式轉(zhuǎn)換是有意的,，并且是正當(dāng)?shù)?。但有時(shí)我們不希望進(jìn)行這種自動(dòng)的轉(zhuǎn)換。 例如：為了避免這樣的隱式轉(zhuǎn)換,，應(yīng)該象下面這樣顯式聲明該帶單一參數(shù)的構(gòu)造函數(shù)： class String {
4,、命名空間namespace 解決在使用不同模塊和程序庫(kù)時(shí)，出現(xiàn)名稱(chēng)沖突問(wèn)題,。 5,、C++標(biāo)準(zhǔn)程序庫(kù)中的通用工具。由類(lèi)和函數(shù)構(gòu)成,。這些工具包括： 數(shù)種通用類(lèi)型 一些重要的C函數(shù) 數(shù)值極值
二,、STL六大組件 容器（Container） 算法（Algorithm） 迭代器（Iterator） 仿函數(shù)（Function object） 適配器（Adaptor） 空間配置器（allocator） 1、容器 作為STL的最主要組成部分－－容器,，分為向量（vector）,，雙端隊(duì)列(deque)，表(list),，隊(duì)列（queue）,，堆棧(stack)，集合(set),，多重集合(multiset),，映射(map)，多重映射(multimap),。
STL容器能力表：
2、算法 算法部分主要由頭文件<algorithm>,，<numeric>和<functional>組成,。< algorithm>是所有STL頭文件中最大的一個(gè)，它是由一大堆模版函數(shù)組成的,，可以認(rèn)為每個(gè)函數(shù)在很大程度上都是獨(dú)立的,，其中常用到的功能范 圍涉及到比較、交換,、查找,、遍歷操作、復(fù)制,、修改,、移除、反轉(zhuǎn),、排序,、合并等等。<numeric>體積很小,，只包括幾個(gè)在序列上面進(jìn)行簡(jiǎn)單數(shù)學(xué)運(yùn)算的模板函數(shù),，包括加法和乘法在序列上的一些操作。<functional>中則定義了一些模板類(lèi),，用以聲明函數(shù)對(duì)象,。 STL的算法也是非常優(yōu)秀的，它們大部分都是類(lèi)屬的,，基本上都用到了C＋＋的模板來(lái)實(shí)現(xiàn),，這樣，很多相似的函數(shù)就不用自己寫(xiě)了,，只要用函數(shù)模板就可以了,。 我們使用算法的時(shí)候，要針對(duì)不同的容器,，比如：對(duì)集合的查找,，最好不要用通用函數(shù)find（），它對(duì)集合使用的時(shí)候，性能非常的差,，最好用集合自帶的find（）函數(shù),，它針對(duì)了集合進(jìn)行了優(yōu)化，性能非常的高,。
3,、迭代器 它的具體實(shí)現(xiàn)在<itertator>中，我們完全可以不管迭代器類(lèi)是怎么實(shí)現(xiàn)的,，大多數(shù)的時(shí)候,，把它理解為指針是沒(méi)有問(wèn)題的（指針是迭代器的一個(gè)特例，它也屬于迭代器）,，但是，決不能完全這么做,。
4,、仿函數(shù) 仿函數(shù)，又或叫做函數(shù)對(duì)象,，是STL六大組件之一,；仿函數(shù)雖然小，但卻極大的拓展了算法的功能,，幾乎所有的算法都有仿函數(shù)版本,。例如，查找算法find_if就是對(duì)find算法的擴(kuò)展,，標(biāo)準(zhǔn)的查找是兩個(gè)元素相等就找到了,，但是什么是相等在不同情況下卻需要不同的定義，如地址相等,，地址和郵編都相等,，雖然這些相等的定義在變，但算法本身卻不需要改變,，這都多虧了仿函數(shù),。仿函數(shù)(functor)又稱(chēng)之為函數(shù)對(duì)象（function object），其實(shí)就是重載了()操作符的struct,，沒(méi)有什么特別的地方,。 如以下代碼定義了一個(gè)二元判斷式functor： struct IntLess 為什么要使用仿函數(shù)呢？ 1).仿函數(shù)比一般的函數(shù)靈活,。 2).仿函數(shù)有類(lèi)型識(shí)別,，可以作為模板參數(shù)。 3).執(zhí)行速度上仿函數(shù)比函數(shù)和指針要更快的,。 怎么使用仿函數(shù),？ 除了在STL里，別的地方你很少會(huì)看到仿函數(shù)的身影。而在STL里仿函數(shù)最常用的就是作為函數(shù)的參數(shù),，或者模板的參數(shù),。 在STL里有自己預(yù)定義的仿函數(shù)，比如所有的運(yùn)算符,，=,，-，*,，,、比如'<'號(hào)的仿函數(shù)是less template<class _Ty> 從上面的定義可以看出，less從binary_function<...>繼承來(lái)的,，那么binary_function又是什么的,？ template<class _Arg1, class _Arg2, class _Result> 其實(shí)binary_function只是做一些類(lèi)型聲明而已，別的什么也沒(méi)做,，但是在STL里為什么要做這些呢,？如果你要閱讀過(guò)STL的源碼，你就會(huì)發(fā)現(xiàn),，這樣的用法很多,，其實(shí)沒(méi)有別的目的，就是為了方便,，安全,，可復(fù)用性等。但是既然STL里面內(nèi)定如此了,，所以作為程序員你必須要遵循這個(gè)規(guī)則,否則就別想安全的使用STL,。 比如我們自己定一個(gè)仿函數(shù)?？梢赃@樣： template <typename type1,typename type2> } 我們看這一行： inline bool operator()(type1 t1,type2 t2) const//這里的const不能少 與binary_function(二元函數(shù))相對(duì)的是unary_function(一元函數(shù)),其用法同binary_function struct unary_function { 注：仿函數(shù)就是重載()的class,，并且重載函數(shù)要為const的,，如果要自定義仿函數(shù)，并且用于STL接配器,，那么一定要從binary_function或者,，unary_function繼承,。
5、適配器 適配器是用來(lái)修改其他組件接口的STL組件,，是帶有一個(gè)參數(shù)的類(lèi)模板（這個(gè)參數(shù)是操作的值的數(shù)據(jù)類(lèi)型）,。STL定義了3種形式的適配器：容器適配器，迭代器適配器,，函數(shù)適配器,。 容器適配器：包括棧（stack）、隊(duì)列(queue),、優(yōu)先(priority_queue),。使用容器適配器，stack就可以被實(shí)現(xiàn)為基本容器類(lèi)型（vector,dequeue,list）的適配,?？梢园?/SPAN>stack看作是某種特殊的vctor,deque或者list容器，只是其操作仍然受到stack本身屬性的限制,。queue和priority_queue與之類(lèi)似,。容器適配器的接口更為簡(jiǎn)單，只是受限比一般容器要多,。 迭代器適配器：修改為某些基本容器定義的迭代器的接口的一種STL組件。反向迭代器和插入迭代器都屬于迭代器適配器,，迭代器適配器擴(kuò)展了迭代器的功能,。 函數(shù)適配器：通過(guò)轉(zhuǎn)換或者修改其他函數(shù)對(duì)象使其功能得到擴(kuò)展。這一類(lèi)適配器有否定器（相當(dāng)于"非"操作）,、綁定器,、函數(shù)指針適配器。函數(shù)對(duì)象適配器的作用就是使函數(shù)轉(zhuǎn)化為函數(shù)對(duì)象,，或是將多參數(shù)的函數(shù)對(duì)象轉(zhuǎn)化為少參數(shù)的函數(shù)對(duì)象,。 例如： 在STL程序里，有的算法需要一個(gè)一元函數(shù)作參數(shù),，就可以用一個(gè)適配器把一個(gè)二元函數(shù)和一個(gè)數(shù)值,，綁在一起作為一個(gè)一元函數(shù)傳給算法。
6、空間配置器 STL的內(nèi)存配置器在我們的實(shí)際應(yīng)用中幾乎不用涉及，但它卻在STL的各種容器背后默默做了大量的工作，STL內(nèi)存配置器為容器分配并管理內(nèi)存。統(tǒng)一的內(nèi)存管理使得STL庫(kù)的可用性、可移植行,、以及效率都有了很大的提升,。 SGI-STL的空間配置器有2種,，一種僅僅對(duì)c語(yǔ)言的malloc和free進(jìn)行了簡(jiǎn)單的封裝,，而另一個(gè)設(shè)計(jì)到小塊內(nèi)存的管理等，運(yùn)用了內(nèi)存池技術(shù)等。在SGI-STL中默認(rèn)的空間配置器是第二級(jí)的配置器。 SGI使用時(shí)std::alloc作為默認(rèn)的配置器,。 A）．a(chǎn)lloc把內(nèi)存配置和對(duì)象構(gòu)造的操作分開(kāi),，分別由alloc::allocate()和::construct()負(fù)責(zé),，同樣內(nèi)存釋放和對(duì)象析夠操作也被分開(kāi)分別由alloc::deallocate()和::destroy()負(fù)責(zé),。這樣可以保證高效，因?yàn)閷?duì)于內(nèi)存分配釋放和構(gòu)造析夠可以根據(jù)具體類(lèi)型(type traits)進(jìn)行優(yōu)化,。比如一些類(lèi)型可以直接使用高效的memset來(lái)初始化或者忽略一些析構(gòu)函數(shù),。對(duì)于內(nèi)存分配alloc也提供了2級(jí)分配器來(lái)應(yīng)對(duì)不同情況的內(nèi)存分配。 B）．第一級(jí)配置器直接使用malloc()和free()來(lái)分配和釋放內(nèi)存,。第二級(jí)視情況采用不同的策略：當(dāng)需求內(nèi)存超過(guò)128bytes的時(shí)候,，視為足夠大，便調(diào)用第一級(jí)配置器,；當(dāng)需求內(nèi)存小于等于128bytes的時(shí)候便采用比較復(fù)雜的memeory pool的方式管理內(nèi)存,。 C）．無(wú)論allocal被定義為第一級(jí)配置器還是第二級(jí)，SGI還為它包裝一個(gè)接口,，使得配置的接口能夠符合標(biāo)準(zhǔn)即把配置單位從bytes轉(zhuǎn)到了元素的大?。?/SPAN> template<class T, class Alloc> class simple_alloc { public: 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* p) { Alloc::deallocate(p, sizeof(T)); } }
d）．內(nèi)存的基本處理工具,，它們均具有commt or rollback能力。 template<class InputIterator, class ForwardIterator> ForwardIterator uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);
template<class ForwardIterator, class T> void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);
template<class ForwardIterator, class Size, class T> ForwardIterator uninitialized_fill_n(ForwardIterator first, ForwardIterator last, const T& x)
三,、具體容器,、算法 1、所有容器都提供了一個(gè)默認(rèn)的構(gòu)造函數(shù),，一個(gè)拷貝構(gòu)造函數(shù),。 例如： list<int> l; .... vector<int> ivector(l.begin(),l.end());
int array[]={1,2,3,4}; .... set<int> iset(array,array+sizeof(array)/sizeof(array[0]));
2、與大小相關(guān)的函數(shù) size(),empty(),max_size() 3,、返回迭代器的函數(shù) begin(),end(),rbegin(),rend() 4,、比較操作 ==,!=,<,>,>=....
Vector詳解： capacity(),返回vector能夠容納的元素個(gè)數(shù)。 size(),返回vector內(nèi)現(xiàn)有元素的個(gè)數(shù),。 賦值操作： c1=c2; 把c2的全部元素指派給c1 c.assign(n,elem);復(fù)制n個(gè)elem,，指派給c c.assign(beg,end);將區(qū)間beg，end內(nèi)的元素指派給c c1.swap(c2);將c1,c2元素互換 swap(c1,c2);同上 元素存取 c.at(index); c[index]; c.front();返回第一個(gè)元素 c.back();
插入和刪除： c.insert(pos.elem); c.insert(pos,n.elem); 插入n個(gè)elem c.insert(pos,beg,end); 在pos出插入beg,，end區(qū)間內(nèi)的所有元素,。 c.push_back(elem); c.pop_back(); c.erase(pos); 刪除pos上的元素，返回下一個(gè)元素 c.erase(beg,end); c.resize(num);將元素?cái)?shù)量改為num,，如果size變大了,，多出來(lái)的新元素都要一default方式構(gòu)建。 c.resize(num,elem);將元素?cái)?shù)量改為num,，如果size變大了,，多出來(lái)的新元素是elem的副本。 c.clear();刪除所有,。
vector的reserve和resize reserve只分配空間,，而不創(chuàng)建對(duì)象，size()不變,。而resize分配空間而且用空對(duì)象填充. reserve是容器預(yù)留空間,，但并不真正創(chuàng)建元素對(duì)象，在創(chuàng)建對(duì)象之前,，不能引用容器內(nèi)的元素,，因此當(dāng)加入新的元素時(shí)，需要用push_back()/insert()函數(shù),。 resize是改變?nèi)萜鞯拇笮?，并且?chuàng)建對(duì)象，因此,，調(diào)用這個(gè)函數(shù)之后,，就可以引用容器內(nèi)的對(duì)象了，因此當(dāng)加入新的元素時(shí),，用operator[]操作符,，或者用迭代器來(lái)引用元素對(duì)象,。 再者，兩個(gè)函數(shù)的形式是有區(qū)別的,，reserve函數(shù)之后一個(gè)參數(shù),，即需要預(yù)留的容器的空間；resize函數(shù)可以有兩個(gè)參數(shù),，第一個(gè)參數(shù)是容器新的大小,，第二個(gè)參數(shù)是要加入容器中的新元素，如果這個(gè)參數(shù)被省略,，那么就調(diào)用元素對(duì)象的默認(rèn)構(gòu)造函數(shù),。 vector有而deque無(wú)的：capacity(), reserve(); deque有而vector無(wú)的：push_front(elem), pop_front(); push_back(elem), pop_back(); STL提供的另兩種容器queue、stack,，其實(shí)都只不過(guò)是一種adaptor,，它們簡(jiǎn)單地修飾deque的界面而成為另外的容器類(lèi)型
List詳解： for_each (.begin(), .end(), “函數(shù)”); count (.begin(), .end(), 100, jishuqi); 返回對(duì)象等于100的個(gè)數(shù)jishuqi值。 count_if() 帶一個(gè)函數(shù)對(duì)象的參數(shù)(上面“100”的這個(gè)參數(shù)),。函數(shù)對(duì)象是一個(gè)至少帶有一個(gè)operator()方法的類(lèi),。這個(gè)類(lèi)可以更復(fù)雜。 find(*.begin().*end(),“要找的東西”),； 如果沒(méi)有找到指出的對(duì)象,，就會(huì)返回*.end()的值，要是找到了就返回一個(gè)指著找到的對(duì)象的iterator fine_if(),；與count_if()類(lèi)似,，是find的更強(qiáng)大版本。 STL通用算法search()用來(lái)搜索一個(gè)容器,，但是是搜索一個(gè)元素串,，不象find()和find_if() 只搜索單個(gè)的元素。 search算法在一個(gè)序列中找另一個(gè)序列的第一次出現(xiàn)的位置,。 search(A.begin(), A.end(), B.begin(), B.end()); 在A中找B這個(gè)序列的第一次出現(xiàn),。 要排序一個(gè)list，我們要用list的成員函數(shù)sort(),，而不是通用算法sort()。 list容器有它自己的sort算法,，這是因?yàn)橥ㄓ盟惴▋H能為那些提供隨機(jī)存取里面元素 的容器排序,。 list的成員函數(shù)push_front()和push_back()分別把元素加入到list的前面和后面。你可以使用insert() 把對(duì)象插入到list中的任何地方,。 insert()可以加入一個(gè)對(duì)象,，一個(gè)對(duì)象的若干份拷貝，或者一個(gè)范圍以?xún)?nèi)的對(duì)象,。 list成員函數(shù)pop_front()刪掉list中的第一個(gè)元素,，pop_back()刪掉最后一個(gè)元素,。函數(shù)erase()刪掉由一個(gè)iterator指出的元素。還有另一個(gè)erase()函數(shù)可以刪掉一個(gè)范圍的元素,。 list的成員函數(shù)remove()用來(lái)從list中刪除元素,。 *.remove("要?jiǎng)h除的對(duì)象"); 通用算法remove()使用和list的成員函數(shù)不同的方式工作。一般情況下不改變?nèi)萜鞯拇笮 ? remove(*.begin(),*.end(),"要?jiǎng)h除的對(duì)象"); 使用STL通用算法stable_partition()和list成員函數(shù)splice()來(lái)劃分一個(gè)list,。 stable_partition()是一個(gè)有趣的函數(shù),。它重新排列元素，使得滿足指定條件的元素排在不滿足條件的元素前面,。它維持著兩組元素的順序關(guān)系,。 splice 把另一個(gè)list中的元素結(jié)合到一個(gè)list中。它從源list中刪除元素,。
Set Map詳解： STL map和set的使用雖不復(fù)雜,，但也有一些不易理解的地方，如： 為何map和set的插入刪除效率比用其他序列容器高,？ 為何每次insert之后,，以前保存的iterator不會(huì)失效？ 為何map和set不能像vector一樣有個(gè)reserve函數(shù)來(lái)預(yù)分配數(shù)據(jù),？ 當(dāng)數(shù)據(jù)元素增多時(shí)（10000到20000個(gè)比較）,，map和set的插入和搜索速度變化如何？ C++ STL中標(biāo)準(zhǔn)關(guān)聯(lián)容器set, multiset, map, multimap內(nèi)部采用的就是一種非常高效的平衡檢索二叉樹(shù)：紅黑樹(shù),，也成為RB樹(shù)(Red-Black Tree),。RB樹(shù)的統(tǒng)計(jì)性能要好于一般的平衡二叉樹(shù)(AVL-樹(shù)). 為何map和set的插入刪除效率比用其他序列容器高？ 大部分人說(shuō),，很簡(jiǎn)單,，因?yàn)閷?duì)于關(guān)聯(lián)容器來(lái)說(shuō)，不需要做內(nèi)存拷貝和內(nèi)存移動(dòng),。說(shuō)對(duì)了,，確實(shí)如此。map和set容器內(nèi)所有元素都是以節(jié)點(diǎn)的方式來(lái)存儲(chǔ),，其節(jié)點(diǎn)結(jié)構(gòu)和鏈表差不多,，指向父節(jié)點(diǎn)和子節(jié)點(diǎn)。這里的一切操作就是指針換來(lái)?yè)Q去,，和內(nèi)存移動(dòng)沒(méi)有關(guān)系,。 為何每次insert之后，以前保存的iterator不會(huì)失效,？(同解) 為何map和set不能像vector一樣有個(gè)reserve函數(shù)來(lái)預(yù)分配數(shù)據(jù),？ 究其原理來(lái)說(shuō)時(shí)，引起它的原因在于在map和set內(nèi)部存儲(chǔ)的已經(jīng)不是元素本身了，而是包含元素的節(jié)點(diǎn),。 其實(shí)你就記住一點(diǎn),，在map和set內(nèi)面的分配器已經(jīng)發(fā)生了變化，reserve方法你就不要奢望了,。 當(dāng)數(shù)據(jù)元素增多時(shí)（10000和20000個(gè)比較）,，map和set的插入和搜索速度變化如何？ 如果你知道log2的關(guān)系你應(yīng)該就徹底了解這個(gè)答案,。在map和set中查找是使用二分查找,，也就是說(shuō)，如果有16個(gè)元素,，最多需要比較4次就能找到結(jié)果,，有32個(gè)元素，最多比較5次,。那么有10000個(gè)呢,？最多比較的次數(shù)為log10000，最多為14次,，如果是20000個(gè)元素呢,？最多不過(guò)15次。
泛型算法： 所有算法的前兩個(gè)參數(shù)都是一對(duì)iterators：[first,，last),，用來(lái)指出容器內(nèi)一個(gè)范圍內(nèi)的元素。 每個(gè)算法的聲明中,，都表現(xiàn)出它所需要的最低層次的iterator類(lèi)型,。
常用算法： accumulate() 元素累加 adjacent_difference() 相鄰元素的差額 adjacent_find() 搜尋相鄰的重復(fù)元素 binary_search() 二元搜尋 copy() 復(fù)制 copy_backward() 逆向復(fù)制 count() 計(jì)數(shù) count_if() 在特定條件下計(jì)數(shù) equal() 判斷相等與否 equal_range() 判斷相等與否（傳回一個(gè)上下限區(qū)間范圍） fill() 改填元素值 fill_n() 改填元素值，n 次 find() 搜尋 find_if() 在特定條件下搜尋 find_end() 搜尋某個(gè)子序列的最后一次出現(xiàn)地點(diǎn) find_first_of() 搜尋某些元素的首次出現(xiàn)地點(diǎn) for_each() 對(duì)范圍內(nèi)的每一個(gè)元素施行某動(dòng)作 generate() 以指定動(dòng)作的運(yùn)算結(jié)果充填特定范圍內(nèi)的元素 generate_n() 以指定動(dòng)作的運(yùn)算結(jié)果充填 n 個(gè)元素內(nèi)容 includes() 涵蓋於 inner_product() 內(nèi)積 inplace_merge() 合并并取代（覆寫(xiě)） iter_swap() 元素互換 lexicographical_compare() 以字典排列方式做比較 lower_bound() 下限 max() 最大值 max_element() 最大值所在位置 min() 最小值 min_element() 最小值所在位置 merge() 合并兩個(gè)序列 mismatch() 找出不吻合點(diǎn) next_permutation() 獲得下一個(gè)排列組合 泛型演算法（Generic Algorithms）與 Function Obje4 cts nth_element() 重新安排序列中第n個(gè)元素的左右兩端 partial_sort() 局部排序 partial_sort_copy() 局部排序并復(fù)制到它處 partial_sum() 局部總和 partition() 切割 prev_permutation() 獲得前一個(gè)排列組合 random_shuffle() 隨機(jī)重排 remove() 移除某種元素（但不刪除） remove_copy() 移除某種元素并將結(jié)果復(fù)制到另一個(gè) container remove_if() 有條件地移除某種元素 remove_copy_if() 有條件地移除某種元素并將結(jié)果復(fù)制到另一個(gè) container replace() 取代某種元素 replace_copy() 取代某種元素,，并將結(jié)果復(fù)制到另一個(gè) container replace_if() 有條件地取代 replace_copy_if() 有條件地取代,，并將結(jié)果復(fù)制到另一個(gè) container reverse() 顛倒元素次序 reverse_copy() 顛倒元素次序并將結(jié)果復(fù)制到另一個(gè) container rotate() 旋轉(zhuǎn) rotate_copy() 旋轉(zhuǎn)，并將結(jié)果復(fù)制到另一個(gè) container search() 搜尋某個(gè)子序列 search_n() 搜尋「連續(xù)發(fā)生 n 次」的子序列 set_difference() 差集 set_intersection() 交集 set_symmetric_difference() 對(duì)稱(chēng)差集 set_union() 聯(lián)集 sort() 排序 stable_partition() 切割并保持元素相對(duì)次序 stable_sort() 排序并保持等值元素的相對(duì)次序 swap() 置換（對(duì)調(diào)） swap_range() 置換（指定范圍） transform() 以?xún)蓚€(gè)序列為基礎(chǔ),，交互作用產(chǎn)生第三個(gè)序列 unique() 將重復(fù)的元素摺疊縮編,，使成唯一 unique_copy() 將重復(fù)的元素摺疊縮編，使成唯一,，并復(fù)制到他處 upper_bound() 上限
四,、注意細(xì)節(jié)： 1、auto_ptr 不能用new[]所生成的array作為初值,，因?yàn)獒尫艃?nèi)存時(shí)用的是delete,，而不是delete[] 2、就搜尋速度而言,，hash table通常比二叉樹(shù)還要快5~10倍。hash table不是C++標(biāo)準(zhǔn)程序庫(kù)的一員,。 3,、迭代器使用過(guò)程中優(yōu)先選用前置式遞增操作符（++iter）而不是選擇后置式遞增操作符（iter++）,。 3、迭代器三個(gè)輔助函數(shù)：advance(),distance(),iter_swap(),。 advance()可令迭代器前進(jìn) distance()可處理迭代器之間的距離,。 iter_swap()可交換兩個(gè)迭代器所指內(nèi)容。 4,、hasp函數(shù) makeheap(),、push_heap()、pop_heap(),、sort_heap() 5,、’/0’在string之中并不具有特殊意義，但是在一般C形式的string中卻用來(lái)標(biāo)記字符串結(jié)束,。在string中,，字符 ‘/0’和其他字符的地位完全相同。string中有三個(gè)函數(shù)可以將字符串內(nèi)容轉(zhuǎn)換成字符數(shù)組或C形式的string,。 data() 以字符數(shù)組的形式返回字符串內(nèi)容,。但末未追加’/0’字符，返回類(lèi)型并非有效的C形式string,。 c_str() 以C形式返回字符串內(nèi)容（在末尾端添加’/0’字符）,。 copy() 將字符串內(nèi)容復(fù)制到“調(diào)用者提供的字符數(shù)組”中，不添加’/0’字符,。 6,、容器中用empty來(lái)代替檢查size是否為0；當(dāng)使用new得到指針的容器時(shí),，切記在容器銷(xiāo)毀前delete那些指針,；千萬(wàn)不要把auto_ptr放入容器中。 7,、盡量使用vector和string來(lái)代替動(dòng)態(tài)申請(qǐng)的數(shù)組,；避免使用vector<bool>，vector<bool>有兩個(gè)問(wèn)題．第一,，它不是一個(gè)真正STL容器,，第二，它并不保存bool類(lèi)型,。 8,、迭代器使用過(guò)程中，盡量使用iterator代替const_iterator,，reverse_iterator和const_reverse_iterator,；使用distance和advance把const_iterators轉(zhuǎn)化成iterators。 typedef deque<int> IntDeque; // 和以前一樣 typedef IntDeque::iterator Iter; typedef IntDeque::const_iterator ConstIter; IntDeque d; ConstIter ci; ... // 讓ci指向d Iter i(d.begin()); // 初始化i為d.begin() advance(i, distance(i, ci)); // 調(diào)整i，指向ci位置 9,、避免對(duì)set和multiset的鍵值進(jìn)行修改,。 10、永遠(yuǎn)讓比較函數(shù)對(duì)相同元素返回false,。 11,、排序選擇： 1）如果你需要在vector,、string,、deque或數(shù)組上進(jìn)行完全排序，你可以使用sort或stable_sort,。 2）如果你有一個(gè)vector,、string,、deque或數(shù)組，你只需要排序前n個(gè)元素,，應(yīng)該用partial_sort,。 3）如果你有一個(gè)vector、string,、deque或數(shù)組,，你需要鑒別出第n個(gè)元素或你需要鑒別出最前的n個(gè)元素，而不用知道它們的順序,，nth_element是你應(yīng)該注意和調(diào)用的,。 4）如果你需要把標(biāo)準(zhǔn)序列容器的元素或數(shù)組分隔為滿足和不滿足某個(gè)標(biāo)準(zhǔn)，你大概就要找partition或stable_partition,。 5）如果你的數(shù)據(jù)是在list中,，你可以直接使用partition和stable_partition，你可以使用list的sort來(lái)代替sort和stable_sort,。如果你需要partial_sort或nth_element提供的效果,，你就必須間接完成這個(gè)任務(wù)。 Set內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次,，Multisets內(nèi)可包含多個(gè)數(shù)值相同的元素。 Map內(nèi)的相同數(shù)值的元素只能出現(xiàn)一次,，Multimap內(nèi)可包含多個(gè)數(shù)值相同的元素,。內(nèi)部由二叉樹(shù)實(shí)現(xiàn)，便于查找,。 17,、string 與 數(shù)字之間的轉(zhuǎn)換,，轉(zhuǎn)換的方法有很多種，一般使用stringstream來(lái)實(shí)現(xiàn)轉(zhuǎn)換,。比如： #include <iostream> #include <sstream> #include <string> using namespace std; int main() { int i=0; string temp; stringstream s; //string轉(zhuǎn)換為數(shù)字 temp = “1234”; s<<temp; s>>i; cout<<i<<endl;
//數(shù)字轉(zhuǎn)換為string i=256; s<<i; temp = s.str(); cout<<temp<<end;
system("pause"); return 0; }
18,、對(duì)于自定義的結(jié)構(gòu)體，放入容器中,，最好不要對(duì)容器進(jìn)行內(nèi)存初始化（不要調(diào)用memset,zeromemory函數(shù)）,，否則如果結(jié)構(gòu)體中有指針類(lèi)型的變量時(shí)，就會(huì)出現(xiàn)問(wèn)題,。
19,、Vector的函數(shù)泄漏問(wèn)題 定義了一個(gè) struct temp { char name[256]; int i; } Vector<temp> vect; 當(dāng)對(duì)這個(gè)vect執(zhí)行pushback一些temp的結(jié)構(gòu)體后，執(zhí)行clear這樣是否會(huì)內(nèi)存泄露,？可以釋放掉temp結(jié)構(gòu)體中的name內(nèi)存嗎,？ 解決方法： 不行，clear只是把那些元素全部刪除掉,，并不是釋放內(nèi)存,。再者，你這樣的定義容器是不需要釋放內(nèi)存的,，如果你這樣定義,，std::vector <temp> *pVec。就需要了,。先pVec->clear()再 pVec->swap( (std::vector <temp>)(*pVec) ),。就能實(shí)現(xiàn)內(nèi)存的釋放。
20,、stl之map erase方法的正確使用 正確的使用方法： 或者 2). erase() 成員函數(shù)返回下一個(gè)元素的迭代器
推薦書(shū)籍： 《C++標(biāo)準(zhǔn)程序庫(kù)》本書(shū)將焦點(diǎn)放在標(biāo)準(zhǔn)模板庫(kù)（Standard Template Library）身上，檢驗(yàn)其中的容器（containers）,、迭代器（iterators）,、仿函數(shù)（functors）和算法（algorithms）。你還可以找到特殊容器,、字符串（strings）,、數(shù)值類(lèi)別,、國(guó)際化議題、IOStream,。每一個(gè)組件都有深刻的呈現(xiàn),，包括其介紹、設(shè)計(jì),、運(yùn)用實(shí)例,、細(xì)部解說(shuō)、陷阱,、意想不到的危險(xiǎn),，以及相關(guān)類(lèi)別和函數(shù)的確切標(biāo)記（signature）和定義。一份見(jiàn)解深刻的基礎(chǔ)概念介紹和一個(gè)程序庫(kù)綜合鳥(niǎo)瞰,，會(huì)對(duì)新手帶來(lái)快速的提升。 《泛型編程與STL》闡述了泛型程序設(shè)計(jì)的中心觀念:concepts,modeling, refinement,并為你展示這些觀念如何導(dǎo)出 STL 的基礎(chǔ)概念:iterators, containers, function objects.循此路線,你可以把 STL 想象為一個(gè)由 concepts(而非明確之 functions 或 classes)組成的 library.你將學(xué)習(xí)其正式結(jié)構(gòu)并因此獲得其潛在威力之完整優(yōu)勢(shì). 《Effective STL》闡述了如何有效地使用STL（Standard Template Library, 標(biāo)準(zhǔn)模板庫(kù)）進(jìn)行編程,。書(shū)中講述了如何將STL組件組合在一起,，從而利用庫(kù)的設(shè)計(jì)。這些內(nèi)容會(huì)幫助你針對(duì)簡(jiǎn)單的問(wèn)題開(kāi)發(fā)出簡(jiǎn)單,、直接的解決方案,，并且針對(duì)復(fù)雜的問(wèn)題開(kāi)發(fā)出精致的解決方案。書(shū)中還描述了常見(jiàn)的STL使用錯(cuò)誤,，并告訴你如何避免這些錯(cuò)誤,。 《STL源碼剖析》了解源碼，看到vector的實(shí)現(xiàn),、list的實(shí)現(xiàn),、heap的實(shí)現(xiàn)、deque的實(shí)現(xiàn),、RB-tree的實(shí)現(xiàn),、hash-table的實(shí)現(xiàn)、set/map 的實(shí)現(xiàn),；你將看到各種算法（排序,、搜尋、排列組合,、數(shù)據(jù)移動(dòng)與復(fù)制…）的實(shí)現(xiàn),；你甚至將看到底層的memory pool 和高階抽象的traits 機(jī)制的實(shí)現(xiàn)。 |
||||||||||||||||||||||||||||||||||||||||||||||||
|
|
來(lái)自： fisher60 > 《STL學(xué)習(xí)》
