容器的優(yōu)缺點及各種容器介紹

StandardTemplateLanguage提供了三個最基本的容器：vector,list,dequevector,deque,list區(qū)另1」vector表示一段連續(xù)的內(nèi)存區(qū)域每個元素被順序存儲在這段內(nèi)存中對vector的隨機訪問比如先訪問元素5然后訪問15然后再訪問7等等效率很高，因為每次訪問離vector起始處的位移都是固定的。但是在任意位置而不是在vector末尾插人元素則效率很低，因為它需要把待插入元素右邊的每個元素都拷貝一遍。類似地刪除任意一個而不是vector的最后一個元素效率同樣很低。因為待刪除元素右邊的每個元素都必須被復(fù)制一遍這種代價對于大型的復(fù)雜的類對象來說尤其大。deque一個deque也表示一段連續(xù)的內(nèi)存區(qū)域但是與vector不同的是它支持高效地在其首部插入和刪除元素它通過兩級數(shù)組結(jié)構(gòu)來實現(xiàn)一級表示實際的容器第二級指向容器的首和尾listList表示非連續(xù)的內(nèi)存區(qū)域并通過一對指向首尾元素的指針雙向鏈接起來從而允許向前和向后兩個方向進(jìn)行遍歷在list的任意位置插入和刪除元素的效率都很高指針必須被重新賦值但是不需要用拷貝元素來實現(xiàn)移動另一方面它對隨機訪問的支持并不好，訪問一個元素需要遍歷中間的元素另外每個元素還有兩個指針的額外空間開銷下面是選擇順序容器類型的一些準(zhǔn)則如果我們需要隨機訪問一個容器則vector要比list好得多。如果我們已知要存儲元素的個數(shù)則vector又是一個比list好的選擇。如果我們需要的不只是在容器兩端插入和刪除元素則list顯然要比vector好除非我們需要在容器首部插入和刪除元素否則vector要比deque好vector向量相當(dāng)于一個數(shù)組在內(nèi)存中分配一塊連續(xù)的內(nèi)存空間進(jìn)行存儲。支持不指定vector大小的存儲。STL內(nèi)部實現(xiàn)時，首先分配一個非常大的內(nèi)存空間預(yù)備進(jìn)行存儲，即capacituy()函數(shù)返回的大小，當(dāng)超過此分配的空間時再整體重新放分配一塊內(nèi)存存儲，這給人以vector可以不指定vector即一個連續(xù)內(nèi)存的大小的感覺。通常此默認(rèn)的內(nèi)存分配能完成大部分情況下的存儲。優(yōu)點：(1)不指定一塊內(nèi)存大小的數(shù)組的連續(xù)存儲，即可以像數(shù)組一樣操作，但可以對此數(shù)組進(jìn)行動態(tài)操作。通常體現(xiàn)在push_back()pop_back()(2)隨機訪問方便，即支持［］操作符和vector.at()⑶節(jié)省空間。缺點：(1)在內(nèi)部進(jìn)行插入刪除操作效率低。只能在vector的最后進(jìn)行push和pop，不能在vector的頭進(jìn)行push和pop。當(dāng)動態(tài)添加的數(shù)據(jù)超過vector默認(rèn)分配的大小時要進(jìn)行整體的重新分配、拷貝與釋放list雙向鏈表每一個結(jié)點都包括一個信息快Info、一個前驅(qū)指針Pre、一個后驅(qū)指針Post?？梢圆环峙浔仨毜膬?nèi)存大小方便的進(jìn)行添加和刪除操作。使用的是非連續(xù)的內(nèi)存空間進(jìn)行存儲。優(yōu)點：(1)不使用連續(xù)內(nèi)存完成動態(tài)操作。(2)在內(nèi)部方便的進(jìn)行插入和刪除操作⑶可在兩端進(jìn)行push、pop缺點:(1)不能進(jìn)行內(nèi)部的隨機訪問，即不支持［］操作符和vector.at()(2)相對于verctor占用內(nèi)存多deque雙端隊列double-endqueuedeque是在功能上合并了vector和list。優(yōu)點：(1)隨機訪問方便，即支持［］操作符和vector.at()(2)在內(nèi)部方便的進(jìn)行插入和刪除操作⑶可在兩端進(jìn)行push、pop缺點：(1)占用內(nèi)存多使用區(qū)別：1如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector2如果你需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list3如果你需要隨即存取，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用dequevector和built-in數(shù)組類似，它擁有一段連續(xù)的內(nèi)存空間，并且起始地址不變，因此它能非常好的支持隨即存取，即［］操作符，但由于它的內(nèi)存空間是連續(xù)的，所以在中間進(jìn)行插入和刪除會造成內(nèi)存塊的拷貝，另外，當(dāng)該數(shù)組后的內(nèi)存空間不夠時，需要重新申請一塊足夠大的內(nèi)存并進(jìn)行內(nèi)存的拷貝。這些都大大影響了vector的效率。list就是數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表（根據(jù)sgistl源代碼），因此它的內(nèi)存空間可以是不連續(xù)的，通過指針來進(jìn)行數(shù)據(jù)的訪問，這個特點使得它的隨即存取變的非常沒有效率,因此它沒有提供［］操作符的重載。但由于鏈表的特點，它可以以很好的效率支持任意地方的刪除和插入。deque是一個double-endedqueue，它的具體實現(xiàn)不太清楚，但知道它具有以下兩個特點：它支持［］操作符，也就是支持隨即存取，并且和vector的效率相差無幾，它支持在兩端的操作：push_back,push_front,pop_back,pop_front等，并且在兩端操作上與list的效率也差不多。因此在實際使用時，如何選擇這三個容器中哪一個，應(yīng)根據(jù)你的需要而定，一般應(yīng)遵循下面的原則：1、 如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector2、 如果你需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list3、 如果你需要隨即存取，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用deque。Vector：C++容器模板中的大哥大，就像是一個加強版的隊列，之所以這樣說,是因為它不但有隊列形式的索引，還能動態(tài)的添加擴充。特點：把被包含的對象以數(shù)組的形式存儲，支持索引形式的訪問（這種訪問速度奇快無比）。但由此也產(chǎn)生了一個問題，由于數(shù)據(jù)存儲形式的固定化，你如果想在他中間部位insert對象的話，搞不好會讓你吃盡頭。因為他在分配空間的時候,可是成塊分配的連續(xù)空間Deque:英文"double-ended-queue”。名如其人，這是C++有序容器中聞名遐邇的雙向隊列。他在設(shè)計之初，就為從兩端添加和刪除元素做了特殊的優(yōu)化。同樣也支持隨即訪問，也有類似vector的［］操作符，但不要因此就把他和vector混為一潭。特點：從本質(zhì)上講，他在分配內(nèi)存的時候，使用了MAP的結(jié)構(gòu)和方法。化整為零，分配了許多小的連續(xù)空間，因此，從deque兩端添加、刪除元素是十分方便的。最重要的一點：如果在不知道內(nèi)存具體需求的時候，使用deque絕對是比vector好的。List：模板中的雙向鏈表。設(shè)計他的目的可能就是為了在容器中間插入、刪除吧，所以有得比有失，他的隨機訪問速度可不敢恭維。而且沒有［］操作。特點：隨機的插入、刪除元素，在速度上占有明顯的優(yōu)勢。并且，由于內(nèi)存分配不連續(xù)，他對插入的要求也十分的低。所以在使用大對象的時候，這可是一個不錯的選擇?！皏ector和deque的區(qū)別主要在于他們底層的實現(xiàn)不同，特別是在插入和刪除操作的實現(xiàn)機制不同。對于vector來說，不管其大小是多少，在頭部插入的效率總是比在尾部插入的效率低。在尾部插入將耗費固定的時間。在頭部進(jìn)行插入時，耗費的時間與vector的大小成正比,vector越大，耗費的時間越多。例如，在一個大小為1000的vector頭部插入一個元素，與在一個大小為10的vector頭部插入一個元素相比，將耗費100倍的時間。刪除操作的情形也與插入類似。因此，vector適合于插入和刪除操作都在尾部進(jìn)行的情況。deque和vector不同，不管進(jìn)行的插入還是刪除操作，也不管這些操作時在頭部還是尾部進(jìn)行，算法的效率是固定的。例如：不管deque的大小是10，100，還是lOOO.deque在頭部和尾部插入刪除的時間是一樣的。因此要在對于兩端進(jìn)行插入或者刪除操作時。deque要優(yōu)于vector0STL中：string、vector、list、deque、set、map的區(qū)另U博客分類：C/C++在STL中基本容器有：string、vector、list、deque、set、mapset和map都是無序的保存元素，只能通過它提供的接口對里面的元素進(jìn)行訪問set:集合，用來判斷某一個元素是不是在一個組里面，使用的比較少map:映射，相當(dāng)于字典，把一個值映射成另一個值，如果想創(chuàng)建字典的話使用它好了string、vector、list、deque、set是有序容器stringstring是basic_stringvchar＞的實現(xiàn)，在內(nèi)存中是連續(xù)存放的.為了提高效率，都會有保留內(nèi)存，如strings="abed",這時s使用的空間可能就是255,當(dāng)string再次往s里面添加內(nèi)容時不會再次分配內(nèi)存■直到內(nèi)容＞255時才會再次申請內(nèi)存，因此提高了它的性能.當(dāng)內(nèi)容＞255時,string會先分配一個新內(nèi)存，然后再把內(nèi)容復(fù)制過去,再復(fù)制先前的內(nèi)容.對string的操作，如果是添加到最后時,一般不需要分配內(nèi)存，所以性能最快；如果是對中間或是開始部分操作,如往那里添加元素或是刪除元素,或是代替元素，這時需要進(jìn)行內(nèi)存復(fù)制，性能會降低.如果刪除元素,string—般不會釋放它已經(jīng)分配的內(nèi)存，為了是下次使用時可以更高效.由于string會有預(yù)保留內(nèi)存，所以如果大量使用的話，會有內(nèi)存浪費,這點需要考慮■還有就是刪除元素時不釋放過多的內(nèi)存,這也要考慮.string中內(nèi)存是在堆中分配的，所以串的長度可以很大，而char[]是在棧中分配的，長度受到可使用的最大棧長度限制.如果對知道要使用的字符串的最大長度,那么可以使用普通的char[],實現(xiàn)而不必使用string.string用在串長度不可知的情況或是變化很大的情況.如果string已經(jīng)經(jīng)歷了多次添加刪除，現(xiàn)在的尺寸比最大的尺寸要小很多,想減少string使用的大小，可以使用：strings="abcdefg";stringy(s);//因為再次分配內(nèi)存時,y只會分配與s中內(nèi)容大一點的內(nèi)存，所以浪費不會很大s.swap(y);//減少s使用的內(nèi)存如果內(nèi)存夠多的話就不用考慮這個了capacity是查看現(xiàn)在使用內(nèi)存的函數(shù)大家可以試試看string分配一個一串后的capacity返回值，還有其它操作后的返回值vectorvector就是動態(tài)數(shù)組■它也是在堆中分配內(nèi)存,元素連續(xù)存放，有保留內(nèi)存，如果減少大小后內(nèi)存也不會釋放■如果新值〉當(dāng)前大小時才會再分配內(nèi)存對最后元素操作最快(在后面添加刪除最快),此時一般不需要移動內(nèi)存，只有保留內(nèi)存不夠時才需要對中間和開始處進(jìn)行添加刪除元素操作需要移動內(nèi)存，如果你的元素是結(jié)構(gòu)或是類,那么移動的同時還會進(jìn)行構(gòu)造和析構(gòu)操作，所以性能不高(最好將結(jié)構(gòu)或類的指針放入vector中，而不是結(jié)構(gòu)或類本身，這樣可以避免移動時的構(gòu)造與析構(gòu))。訪問方面，對任何元素的訪問都是0(1),也就是是常數(shù)的，所以vector常用來保存需要經(jīng)常進(jìn)行隨機訪問的內(nèi)容，并且不需要經(jīng)常對中間元素進(jìn)行添加刪除操作.相比較可以看到vector的屬性與string差不多，同樣可以使用capacity看當(dāng)前保留的內(nèi)存,使用swap來減少它使用的內(nèi)存.總結(jié)需要經(jīng)常隨機訪問請用vector3.listlist就是鏈表,元素也是在堆中存放，每個元素都是放在一塊內(nèi)存中l(wèi)ist沒有空間預(yù)留習(xí)慣,所以每分配一個元素都會從內(nèi)存中分配,每刪除一個元素都會釋放它占用的內(nèi)存,這與上面不同，可要看好了list在哪里添加刪除元素性能都很高，不需要移動內(nèi)存，當(dāng)然也不需要對每個元素都進(jìn)行構(gòu)造與析構(gòu)了，所以常用來做隨機操作容器.但是訪問list里面的元素時就開始和最后訪問最快訪問其它元素都是O(n)，所以如果需要經(jīng)常隨機訪問的話，還是使用其它的好總結(jié)如果你喜歡經(jīng)常添加刪除大對象的話，那么請使用list要保存的對象不大，構(gòu)造與析構(gòu)操作不復(fù)雜,那么可以使用vector代替list＜指針〉完全是性能最低的做法,這種情況下還是使用vectorv指針〉好,因為指針沒有構(gòu)造與析構(gòu)，也不占用很大內(nèi)存deque雙端隊列，也是在堆中保存內(nèi)容的.它的保存形式如下：[堆1][堆2][堆3]每個堆保存好幾個元素,然后堆和堆之間有指針指向，看起來像是list和vector的結(jié)合品，不過確實也是如此deque可以讓你在前面快速地添加刪除元素，或是在后面快速地添加刪除元素，然后還可以有比較高的隨機訪問速度vector是可以快速地在最后添加刪除元素，并可以快速地訪問任意元素list是可以快速地在所有地方添加刪除元素,但是只能快速地訪問最開始與最后的元素deque在開始和最后添加元素都一樣快，并提供了隨機訪問方法，像vector一樣使用□訪問任意元素，但是隨機訪問速度比不上vector快，因為它要內(nèi)部處理堆跳轉(zhuǎn)deque也有保留空間.另外，由于deque不要求連續(xù)空間，所以可以保存的元素比vector更大，這點也要注意一下■還有就是在前面和后面添加元素時都不需要移動其它塊的元素，所以性能也很高STL入門--vectorlistdeque區(qū)別stl的內(nèi)容很多，本文就實際中比較常用的和初學(xué)時應(yīng)該注意的方面進(jìn)行介紹任何一門高級計算機語言，都需要有一定的類庫或者函數(shù)庫的支持。C++的標(biāo)準(zhǔn)庫(c++standardlibrary)，在1998年成為國際標(biāo)準(zhǔn)。在這個標(biāo)準(zhǔn)庫中，包含了一個很重要的組成部分，也就是這篇文章的主題所在---標(biāo)準(zhǔn)模板庫STL(standardtemplatelibrary)。為了在標(biāo)準(zhǔn)庫中加入這個部分，C++的標(biāo)準(zhǔn)甚至推遲了出爐的日期，可見它在整個標(biāo)準(zhǔn)庫中的重要地位。在標(biāo)準(zhǔn)中只是規(guī)定了stl庫的實現(xiàn)規(guī)范，任何人都可以根據(jù)這個規(guī)范實現(xiàn)出stl庫，所以現(xiàn)在的stl庫有很多版本，他們的實現(xiàn)方法也不完全相同。一、 工作環(huán)境由于STL是98年標(biāo)準(zhǔn)的產(chǎn)物，所以早先的C++編譯器(比如tc3.0)是無法編譯運行使用了STL庫的程序的。當(dāng)然，現(xiàn)在流行的C++編譯器或開發(fā)環(huán)境都提供了對它的支持，比如visualC++和C++builder,g++等等。所以，stl自然的可以應(yīng)用到所有的用標(biāo)準(zhǔn)C++開發(fā)的程序中去。二、 第一個使用了STL程序〃一個對數(shù)組進(jìn)行快速排序的程序#includeviostream>#includevalgorithm>usingnamespacestd;intmain(){inta[10]={3,4,7,10,3,2,1,5,6,7};inti=0;sort(a,a+10);for(;iv10;i++){cout<<a[i]<<”“<<endl;}}這么短的快速排序程序可能以前沒有見過吧：)，既沒有比較大小，也沒有元素交換，就完成了工作?，F(xiàn)在提出另一個問題，要對事先不知道個數(shù)的元素進(jìn)行排序，看看使用STL的解決方案。#includevvector>#includevalgorithm>#includeviostream>usingnamespacestd;intmain(){vectorvint>vec;intn;cin>>n;while(n--){intx;cin>>x;vec.push_back(x);}sort(vec.begin(),vec.end());}vector，暫且把他看成一個類似數(shù)組的東西，過會我們會詳細(xì)地講解他的用法。從上面兩個例子，我們可以看到stl最常用的兩大類組件：容器和算法。容器，顧名思義是用來存放數(shù)據(jù)的，就如同第二個例子里的vector。算法，當(dāng)然是用來對數(shù)據(jù)進(jìn)行操作的啦，第一個例子里的sort()就是stl里很多算法的一個。三、 容器類模板介紹在stl中，使用頻率最高的容器類模板有三個vector,list,deque1.vector模板的常用使用方法vector容器的性質(zhì)類似于數(shù)組，他的元素排列方式和C++的內(nèi)建數(shù)組一樣，在內(nèi)存中順序排列。聲明：vectorvstring>vec;//一個空的vector容器vectorvint>vec(10)//一個有10個int元素的容器vectorvfloat>vec(10,0.5)//—個有10個float元素的容器，并且他們得值都是0.5使用：⑴push_back()、pop_back()和size()方法,這是對vector操作的兩個常用方法。Push_back()用于將一個元素插入vector的尾部，而pop_back()則將最后一個元素刪除。就要用到size()返回整型值，表示vector里有多少元素。例如：vectorvint>vec;vec.push_back(4);vec.push_back(5);vec.pop_back();〃此時vec中有一個元素4ints=vec.size();//s的值是1對于事先不知道大小的vector,我們通常都用push_back(),將元素送入容器中，比如開頭第二個例子。(2)[]運算符，前面說了，vector的性質(zhì)類似于數(shù)組，所以他支持[]運算符，使得對數(shù)組的運算方法完全適用于vector。也就是說，vector有和數(shù)組一樣的“下標(biāo)”概念。vectorvint>vec(100,5);〃有100個元素且元素值都為5的vectorfor(intj=0;jv100;j++)vec[j]=vec[j]+1;〃通過下標(biāo)遍歷這個vector⑶指向vector內(nèi)元素的指針vector<T1>::iterator這種指針實際上是一種智能指針，它實際上也是一個模板，但是重載了指針的常用運算符，比如++，--。它定義在vector頭文件中。與vector<T1>::iterator相關(guān)的方法有：begin()：用來獲得一個指向vector第一個元素的指針end()：用來獲得一個指向vector最后一個元素之后的那個位置的指針，注意不是指向最后一個元素。erase(vector<T1>::iterator)：用來刪除作為參數(shù)所傳入的那個iterator所指向的那個元素。舉一個使用iterator來遍歷vector的例子vectorvint>vec(100,-1);vectorvint>::iteratoriter;for(iter=vec.begin();iter!=vec.end();iter++){// }for(iter=vec.end()-1;iter!=vec.begin()_1;iter--){// }2.list模板簡介list，是一個鏈表類的容器，它的元素在內(nèi)存中不是順序排列的，而是通過指針鏈接的，這一點使它和vector有了本質(zhì)的區(qū)別。常用方法：(1)push_back(),pop_back(),push_front(),pop_front()，前兩個方法和vector中的兩個同名方法作用相同，而push_front()用來從list的前端插入一個元素，pop_front()用來刪除list的第一個元素。(2)list不支持□-下標(biāo)運算符，所以對其中的元素進(jìn)行存取遍歷只能通過指針了。指向Iist所存元素的指針是list<T1>::iterator，和vector<T1>::iterator一樣，它也支持++，--運算符。begin()：用來獲得一個指向Iist第一個元素的指針end()：用來獲得一個指向list最后一個元素之后的那個位置的指針，注意不是指向最后一個元素。erase(Iist<T1>::iterator):用來刪除作為參數(shù)所傳入的那個iterator所指向的那個兀素。舉一個使用iterator來遍歷list的例子listvstring>stringList;list<string>::iteratoriter;for(iter=stringList.begin();iter!=stringList.end();iter++){// }for(iter=stringList.e