為了提高效率,實(shí)際上vector 并不是隨每一個(gè)元素的插入而增長(zhǎng)自己,而是當(dāng)vector 需
要增長(zhǎng)自身時(shí),它實(shí)際分配的空間比當(dāng)前所需的空間要多一些.。也就是說它分配了一些額
外的內(nèi)存容量或者說它預(yù)留了這些存儲(chǔ)區(qū)分配的額外容量的確切數(shù)目由具體實(shí)現(xiàn)定義，
這個(gè)策略使容器的增長(zhǎng)效率更高——因此
實(shí)際上對(duì)于小的對(duì)象vector 在實(shí)踐中比list
效率更高
讓我們來看一看在C++標(biāo)準(zhǔn)庫的Rogue Wave 實(shí)現(xiàn)版本下的一些例子但是首先
我們要弄清楚容器的容量和長(zhǎng)度
size 之間的區(qū)別。
容量是指在容器下一次需要增長(zhǎng)自己之前能夠被加入到容器中的元素的總數(shù)，容量只與
連續(xù)存儲(chǔ)的容器相關(guān)，例如vector deque 或string ，list 不要求容量。為了知道一個(gè)容器的
容量我們調(diào)用它的
capacity()操作而長(zhǎng)度size 是指容器當(dāng)前擁有元素的個(gè)數(shù)為了獲
得容器的當(dāng)前長(zhǎng)度我們調(diào)用它的size()操作例。
我在VC++.net上試驗(yàn)的代碼，可以看出他的增長(zhǎng)方式
?? FILE *file=freopen("1.txt","w",stdout);
?? vector<int> vec;
?? cout<<"capacity"<<vec.capacity()<<"size"<<vec.size()<<endl;
?? for(int i=0;i<100;i++)
?? {
????? vec.push_back(i);
?? cout<<"capacity"<<vec.capacity()<<"size"<<vec.size()<<endl;
?? }
結(jié)果如下：
capacity0size0
capacity1size1
capacity2size2
capacity3size3
capacity4size4
capacity6size5
capacity6size6
capacity9size7
capacity9size8
capacity9size9
capacity13size10
capacity13size11
capacity13size12
capacity13size13
capacity19size14
capacity19size15
capacity19size16
capacity19size17
capacity19size18
capacity19size19
capacity28size20
capacity28size21
capacity28size22
capacity28size23
capacity28size24
capacity28size25
capacity28size26
capacity28size27
capacity28size28
capacity42size29
capacity42size30
capacity42size31
capacity42size32
capacity42size33
capacity42size34
capacity42size35
capacity42size36
capacity42size37
capacity42size38
capacity42size39
capacity42size40
capacity42size41
capacity42size42
capacity63size43
capacity63size44
capacity63size45
capacity63size46
capacity63size47
capacity63size48
capacity63size49
capacity63size50
capacity63size51
capacity63size52
capacity63size53
capacity63size54
capacity63size55
capacity63size56
capacity63size57
capacity63size58
capacity63size59
capacity63size60
capacity63size61
capacity63size62
capacity63size63
capacity94size64
capacity94size65
capacity94size66
capacity94size67
capacity94size68
capacity94size69
capacity94size70
capacity94size71
capacity94size72
capacity94size73
capacity94size74
capacity94size75
capacity94size76
capacity94size77
capacity94size78
capacity94size79
capacity94size80
capacity94size81
capacity94size82
capacity94size83
capacity94size84
capacity94size85
capacity94size86
capacity94size87
capacity94size88
capacity94size89
capacity94size90
capacity94size91
capacity94size92
capacity94size93
capacity94size94
capacity141size95
capacity141size96
capacity141size97
capacity141size98
capacity141size99
capacity141size100
對(duì)于小的數(shù)據(jù)類型vector 的性能要比list 好得多，而對(duì)于大型的數(shù)據(jù)類型則相反list 的性能要好得多，區(qū)別是由于vector 需要重新增長(zhǎng)以及拷貝元素。
無論是list 還是vector ，對(duì)于已定義拷貝構(gòu)造函數(shù)的類來說插入這樣的類的元素都需要調(diào)用拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)（用該類型的一個(gè)對(duì)象初始化該類型的另一個(gè)對(duì)象）
這正說明了在簡(jiǎn)單類和string 的鏈表之間插入代價(jià)的區(qū)別：簡(jiǎn)單類對(duì)象和大型簡(jiǎn)單類對(duì)象通過按位拷貝插入一個(gè)對(duì)象的所有位被拷貝到第二個(gè)對(duì)象的位中，而string 類對(duì)象和大型復(fù)雜類對(duì)象通過調(diào)用拷貝構(gòu)造函數(shù)來插入。
另外隨著每次重新分配內(nèi)存，vector 必須為每個(gè)元素調(diào)用拷貝構(gòu)造函數(shù)，而且在釋放原來的內(nèi)存時(shí)它要為每個(gè)元素調(diào)用其相關(guān)類型的析構(gòu)函數(shù)。vector 的動(dòng)態(tài)自我增長(zhǎng)越頻繁，元素插入的開銷就越大。
當(dāng)然，一種解決方案是，當(dāng)vector 的開銷變得非常大時(shí)把vector 轉(zhuǎn)換成list ；另一種經(jīng)
常使用的方案是通過指針間接存儲(chǔ)復(fù)雜的類對(duì)象。