第9章 順序容器

第9章是第3章的擴(kuò)展挚躯。

9.1 順序容器概述

forward_list和array是新c++標(biāo)準(zhǔn)增加的類型箩兽。

list和forward_list這兩個(gè)容器與vector、deque和array相比章喉，額外內(nèi)存開銷很大汗贫。

forward_list

其設(shè)計(jì)目標(biāo)是達(dá)到與最好的手寫的單向鏈表相當(dāng)?shù)男阅苌碜Ｋ运鼪]有size操作，因?yàn)楸４婊蛴?jì)算大小就會(huì)比手寫鏈表多出額外的開銷落包。

array

與內(nèi)置數(shù)組相比部蛇，array更安全、更易用咐蝇。新標(biāo)準(zhǔn)庫(kù)的容器比舊版本的快得多涯鲁。

現(xiàn)代C++程序應(yīng)該使用標(biāo)準(zhǔn)庫(kù)容器而不是更原始的數(shù)據(jù)結(jié)構(gòu)，如內(nèi)置數(shù)組有序。

確定使用哪種順序容器

從P293可以看到抹腿，vector是最推薦的。array好像根本沒提到旭寿。警绩。。

當(dāng)程序既需要隨機(jī)訪問元素盅称，又需要在容器中間位置插入元素肩祥，那使用哪種就取決于在list或forward_list中訪問元素與vector或deque中插入/刪除元素的相對(duì)性能。一般來說缩膝，應(yīng)用中占主導(dǎo)地位的操作決定了容器類型的操作混狠。

9.2 容器庫(kù)概覽

某些操作是容器共有的，某些則只適用于一小部分容器疾层。

容器都定義在一個(gè)同名的頭文件中檀蹋。

容器均定義為模板類，對(duì)大多數(shù)容器（并非所有）云芦，需要提供額外信息來生成。

容器操作

9.2.1 迭代器

迭代器支持的操作在P96拄踪。算術(shù)運(yùn)算在P99蝇恶，這些運(yùn)算只能應(yīng)用于string、vector惶桐、deque和array的迭代器撮弧，即list什么的它們的迭代器不能用+,-,>,<之類的算術(shù)運(yùn)算符潘懊。

迭代器范圍

迭代器范圍由一對(duì)迭代器表示。end用來指向尾后元素贿衍，[begin,end)被稱為左閉合區(qū)間授舟。

對(duì)于迭代器范圍的要求：

• 指向同一容器中的元素，或是容器最后一個(gè)元素之后的位置
• end不在begin之前

9.2.2 容器類型成員

size_type贸辈、difference_type释树、iterator、const_iterator擎淤、value_type奢啥、reference、const_reference揉燃。最后三個(gè)類型介紹在后面的章節(jié)扫尺，它們?cè)?strong>泛型編程中非常有用。

9.2.3 begin和end成員

begin和end有多個(gè)版本：帶r的版本返回反向迭代器炊汤，以c開頭的版本返回const迭代器正驻。

不以c開頭的都是被重載過的，即實(shí)際上含有兩個(gè)名為begin的成員抢腐。當(dāng)一個(gè)非常量對(duì)象調(diào)用這些變量時(shí)姑曙，返回的是iterator；只有在對(duì)一個(gè)const對(duì)象調(diào)用時(shí)迈倍，才會(huì)返回const_iterator伤靠。

9.2.4 容器定義和初始化

將一個(gè)容器初始化為另一個(gè)容器的拷貝

有兩種方法：

• 直接拷貝整個(gè)容器
• 拷貝由一個(gè)迭代器對(duì)指定的元素范圍

當(dāng)為 直接拷貝整個(gè)容器 時(shí)，容器類型及元素類型都必須相同啼染。

當(dāng)為拷貝由一個(gè)迭代器對(duì)指定的元素范圍時(shí)宴合，就不要求容器類型相同了，只要其元素類型能夠成功轉(zhuǎn)換即可迹鹅。如：

vector<const char*> articles = {"a","an","the"};
vector<string> words(articles);  //錯(cuò)誤
forward_list<string> words(articles.begin(), articles.end())  //正確：可將const char*元素轉(zhuǎn)為string

列表初始化

與順序容器大小相關(guān)的構(gòu)造函數(shù)

接受一個(gè)容器大小和一個(gè)（可選的）元素初始值卦洽，這個(gè)可選的前提是這個(gè)元素類型有默認(rèn)構(gòu)造函數(shù)，否則必須制定一個(gè)顯式的元素初始值斜棚。

標(biāo)準(zhǔn)庫(kù)array具有固定大小

定義一個(gè)array時(shí)阀蒂，除了指定元素類型，還要指定容器大小弟蚀。如：array<int, 42> 蚤霞。array的構(gòu)造函數(shù)無法接受大小參數(shù)，因?yàn)橐呀?jīng)在前面定義了义钉。大小是類型的一部分Ｃ列濉！

與其他容器不同断医，一個(gè)默認(rèn)構(gòu)造的array是非空的：包含了與其大小一樣多的元素滞乙，且這些元素都被默認(rèn)初始化（與內(nèi)置數(shù)組一樣）奏纪。

array可以進(jìn)行拷貝或?qū)ο筚x值操作，而內(nèi)置數(shù)組不行斩启。

9.2.5 賦值和swap

assign不適用于關(guān)聯(lián)容器和array。

使用assign（順序容器）

賦值運(yùn)算符要求左右兩邊的運(yùn)算對(duì)象具有相同的類型垄琐。而assign允許從一個(gè)不同但相容的類型賦值边酒，如將vector中一段char*值賦予一個(gè)list中的string。

使用swap

除array外狸窘，交換兩個(gè)容器內(nèi)容的操作保證會(huì)很快--元素本身并未交換墩朦，swap只是交換了兩個(gè)容器的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。除array外翻擒，swap不對(duì)任何元素進(jìn)行拷貝氓涣、刪除或者插入操作，因此可保證在常數(shù)時(shí)間內(nèi)完成陋气。

元素不會(huì)被移動(dòng)劳吠，意味著指向容器的迭代器、指針和引用在swap之后都不會(huì)失效巩趁，仍指向swap操作之前所指向的那些元素痒玩。與其他容器不同，對(duì)一個(gè)string調(diào)用swap會(huì)導(dǎo)致它們失效议慰。如假定iter在swap之前指向svec1[3]的string蠢古，swap之后它指向svec2[3]的元素。

統(tǒng)一使用非成員版本的swap是一個(gè)好習(xí)慣别凹。

9.26 容器大小操作

forward_list支持max_size和empty便瑟，但不支持size。

9.27 關(guān)系運(yùn)算符

每個(gè)容器類型都支持相等運(yùn)算符番川；除了無序關(guān)聯(lián)容器外的所有容器都支持關(guān)系運(yùn)算符（>、>=脊框、<颁督、<=）。

關(guān)系運(yùn)算符左右的對(duì)象必須滿足容器類型相同浇雹、元素類型相同的條件沉御。vector<double>和vector<int>都不能比較

vector<int> v1 = {1,3,5,7,9,12};
vector<int> v2 = {1,3,9};
vector<int> v3 = {1,3,5,7};
v1 < v2 //true; v1和v2在元素[2]處不同：v1[2]小于等于v2[2]
v1 < v3 //false; v3元素?cái)?shù)目更少

容器的關(guān)系運(yùn)算符使用元素的關(guān)系運(yùn)算符完成比較

9.3 順序容器操作

順序容器和關(guān)聯(lián)容器的不同之處在于兩者組織元素的方式。

容器元素是拷貝昭灵，而不是對(duì)象本身吠裆，與提供值的對(duì)象之間沒有任何關(guān)聯(lián)伐谈。

9.3.1 向順序容器添加元素

使用push_back

除array和forward_list都支持push_back。

使用push_front

list试疙、forward_list和deque容器支持诵棵。插入元素到頭部。

在容器中的特定位置添加元素

push_back

插入范圍內(nèi)元素

若傳遞給insert一對(duì)迭代器祝旷，它們不能指向添加元素的目標(biāo)容器履澳。

使用insert的返回值

在新標(biāo)準(zhǔn)下，接受元素個(gè)數(shù)或范圍的insert版本返回指向第一個(gè)新加入元素的迭代器怀跛。若范圍為空距贷，不插入任何元素，insert操作會(huì)將第一個(gè)參數(shù)返回吻谋。

list<string> lst;
auto iter = lst.begin();
while (cin >> word)
    iter = lst.insert(iter, word);  //等價(jià)于調(diào)用push_front

使用emplace操作

emplace忠蝗、emplace_front、emplace_back分別對(duì)應(yīng)insert漓拾、push_front和push_back阁最。

但emplace都是構(gòu)造而不是拷貝元素。emplace成員會(huì)使用傳遞的參數(shù)在容器管理的內(nèi)存空間中直接構(gòu)造元素晦攒。若參數(shù)為空闽撤，則調(diào)用元素的默認(rèn)構(gòu)造函數(shù)。

如：

//c為容器脯颜，保存Sales_data
//使用三個(gè)參數(shù)的Sales_data構(gòu)造函數(shù)
c.emplace_back("978-0590353403", 25, 15.99)
//錯(cuò)誤：沒有接受三個(gè)參數(shù)的push_back版本
c.push_back("978-0590353403", 25, 15.99)
//正確：創(chuàng)建一個(gè)臨時(shí)的Sales_data對(duì)象傳遞給push_back
c.push_back(Sales_data("978-0590353403", 25, 15.99))

如果要插入的對(duì)象還未定義哟旗，emplace的好處就體現(xiàn)出來了，第三種方法要?jiǎng)?chuàng)建臨時(shí)變量顯然沒那么高效栋操。

傳遞給emplace函數(shù)的參數(shù)必須和元素類型的構(gòu)造函數(shù)相匹配闸餐。

練習(xí)9.21 — 為何vector支持通過insert不斷在首位置插入元素，卻不支持push_front矾芙？

Milo Yip：因?yàn)?vector 的設(shè)計(jì)是為了 O(1) push_back()舍沙，對(duì)它來說 push_front() 的性能等同于 O(n) 的 insert()，所以就不提供 push_front() 避免誤用剔宪。 類似 vector 但能 O(1) push_front() 的是 deque拂铡。

---

陳碩：這正是 STL 接口（concept）的優(yōu)點(diǎn)，也是泛型編程優(yōu)于面向?qū)ο蟮姆矫妫好鞔_的時(shí)間復(fù)雜度葱绒，不提供看似高效實(shí)則低效的操作感帅，以免誤用（例如 list 就沒有 operator[]）。

反觀某些以 OO 風(fēng)格實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)庫(kù)地淀，例如 Java collections失球，哪怕是 LinkedList 也要實(shí)現(xiàn) List 接口的 get 方法，是線性時(shí)間帮毁。如果你面向接口編程实苞，對(duì)傳入的 List 調(diào)用 get 豺撑，而用戶傳給你一個(gè)鏈表，那就呵呵了黔牵，有可能 O(N) 算法變成 O(N^2)聪轿。全世界不知道有多少 CPU cycles 浪費(fèi)在了 LinkedList.get() 中。究其原因荧止，OO interface 只規(guī)定了功能屹电，沒有規(guī)定性能（復(fù)雜度），因此跃巡，OO 不適合描述數(shù)據(jù)結(jié)構(gòu)（ADT）危号。
最后，為了防止這種錯(cuò)誤素邪，究竟是不應(yīng)該面向接口編程外莲，還是 LinkedList 不應(yīng)該實(shí)現(xiàn) List 接口，又或者 List 接口不應(yīng)該包含 get() 呢兔朦？
Java LinkedList 的缺點(diǎn)不止這一點(diǎn)偷线，誰用誰知道。

9.3.2 訪問元素

使用front和back分別返回首元素和尾元素的引用沽甥。如果使用迭代器獲取尾元素的值声邦，就得*(c.end()--)，而用back就很方便摆舟。

在調(diào)用front和back之前要確保c非空俺附，否則操作的行為將是未定義的隙轻。

還有c[n]和c.at(n)都為返回下標(biāo)為n的元素的引用刘离。

9.3.3 刪除元素

9.3.4 特殊的forward_list操作

9.3.5 改變?nèi)萜鞔笮?/p>

9.3.6 容器操作可能使迭代器失效

9.4 vector對(duì)象是如何增長(zhǎng)的

為支持快速隨機(jī)訪問粘优，vector將元素連續(xù)存儲(chǔ)。當(dāng)向vector添加元素時(shí)照宝，如果沒有空間容納新元素蛇受，容器就必須分配新的內(nèi)存空間來保存已有元素和新元素，將已有元素從舊位置移動(dòng)到新空間中再添加新元素厕鹃，釋放舊存儲(chǔ)空間兢仰。

這個(gè)過程是緩慢的，為了保證效率剂碴，當(dāng)超出容器空間時(shí)旨别，vector和string的實(shí)現(xiàn)通常會(huì)分配比新的空間需求大的內(nèi)存空間。（我的電腦編譯顯示是之前容量的一倍汗茄，這個(gè)新空間大小取決于不同的編譯器）。

resize成員函數(shù)只改變?nèi)萜髦性氐臄?shù)目铭若，而不是容器的容量洪碳。

容器的size是指它已經(jīng)保存的元素的數(shù)目递览；而capacity則是在不分配新的內(nèi)存空間的前提下它最多可以保存多少元素。

shrink_to_fit()是可以用來要求容器將超出當(dāng)前大小的多余內(nèi)存退回給系統(tǒng)瞳腌，調(diào)用它只是一個(gè)請(qǐng)求绞铃，標(biāo)準(zhǔn)庫(kù)并不保證退還內(nèi)存。

reserve(n) ：分配至少能容納n個(gè)元素的內(nèi)存空間嫂侍。

9.5 額外的string操作

9.5.1 構(gòu)造string的其他方法

substr操作

返回一個(gè)string懒鉴，它是原始string的一部分或全部的拷貝。

s.substr(pos, n)碎浇，n為長(zhǎng)度临谱。和上面的構(gòu)造string的方法道理是相同的。當(dāng)pos>s.size()時(shí)奴璃，拋出異常悉默。

9.5.2 改變string的其他方法

insert和eraser除了接受迭代器的版本，string還提供了接受下標(biāo)的版本苟穆。

s.insert(s.size(), 5, '!'); //在s末尾插入5個(gè)感嘆號(hào)

s.erase(s.size()-5 , 5); //從s刪除最后5個(gè)字符

append和replace函數(shù)

這是string類定義的兩個(gè)額外的成員函數(shù)抄课。

s.append(args) //將args追加到s。返回一個(gè)指向s的引用

s.replace(range,args) //刪除s中范圍range內(nèi)的字符鞭缭，替換為args指定的字符剖膳。返回一個(gè)指向s的引用。

s.assign(args) //將s中的字符替換為args指定的字符岭辣。返回一個(gè)指向s的引用

s.erase(pos,len) //刪除從位置pos開始的len個(gè)字符吱晒。若len省略，則刪除從pos至末尾的所有字符沦童。

s.insert(pos,args) //在pos之前插入args指定的字符仑濒。

9.5.3 string搜索操作

s.find(args) //查找s中args第一次出現(xiàn)的位置

s.rfind(args)  //查找s中args最后一次出現(xiàn)的位置

s.find_first_of(args)  //在s中查找args中任何一個(gè)字符第一次出現(xiàn)的位置

s.find_first_not_of(args)  //在s中查找args中任何一個(gè)字符最后一次出現(xiàn)的位置

s.find_last_of(args)  //在s中查找第一個(gè)不在args中的字符

s.find_last_nof_of(args)  //在s中查找最后一個(gè)不在args中的字符

args必須為以下形式：

c,pos  從s中位置pos開始查找字符c。pos默認(rèn)為0
s2,pos  從s中位置pos開始查找字符串s2偷遗。pos默認(rèn)為0
cp,pos  從s中位置pos開始查找指針cp指向的以空字符串結(jié)尾的C風(fēng)格字符串墩瞳。pos默認(rèn)為0
cp,pos,n  從s中位置pos開始查找指針cp指向的數(shù)組的前n個(gè)字符。pos和n無默認(rèn)值

pos可以用于指定在哪里開始搜索

逆向搜索

提供從右向左的搜索氏豌。就是rfind喉酌，find_last_of及find_last_not_of函數(shù)。

9.5.4 compare函數(shù)

與C標(biāo)準(zhǔn)庫(kù)的strcmp函數(shù)很相似。類似strcmp泪电，根據(jù)s是等于般妙、大于還是小于參數(shù)指定的字符串，s.compare返回0相速、正數(shù)或負(fù)數(shù)碟渺。

9.5.5 數(shù)值轉(zhuǎn)換

9.6 容器適配器

標(biāo)準(zhǔn)庫(kù)還定義了三個(gè)順序容器適配器：stack绒极、queue和priority_queue。

容器催束、迭代器和函數(shù)都有適配器集峦。

本質(zhì)上，一個(gè)適配器是一種機(jī)制抠刺，能使某種事物的行為看起來像另一個(gè)事物一樣塔淤。一個(gè)容器適配器接受一種已有的容器類型，使其行為看起來像一種不同的類型速妖。

定義一個(gè)適配器

每個(gè)適配器都定義兩個(gè)構(gòu)造函數(shù)：默認(rèn)構(gòu)造函數(shù)創(chuàng)建一個(gè)空對(duì)象高蜂，接受一個(gè)容器的構(gòu)造函數(shù)拷貝該容器來初始化適配器。

默認(rèn)情況下罕容，stack和queue是基于deque實(shí)現(xiàn)的备恤，priority_queue是在vector之上實(shí)現(xiàn)的。

stack<string, vector<string>> str_stk; //在vector上實(shí)現(xiàn)的空棧

stack<string, vector<string>> str_stk2(svec); //str_stk2是在vector上實(shí)現(xiàn)的锦秒，初始化時(shí)保存svec的拷貝

所有適配器都要求容器具有添加和刪除元素的能力露泊。因此，適配器不能構(gòu)造在array之上旅择。類似的惭笑，我們也不能用forward_list來構(gòu)造適配器，所有適配器都要求容器具有添加和刪除及訪問尾元素的能力生真。

舉例：

stack只要求push_back沉噩、pop_back、back操作柱蟀，所以它支持除array和forward_list之外的任何容器類型來轉(zhuǎn)換川蒙。

queue要求back、push_back长已、front畜眨、push_front昼牛，因此它可以構(gòu)造在list或deque之上，但不能基于vector康聂。

priority_queue除了front匾嘱、pop_back、push_back操作之外還要求隨機(jī)訪問能力早抠，因此可以構(gòu)造于vector或deque之上，但不能基于list撬讽。

棧適配器 - 默認(rèn)基于deque實(shí)現(xiàn)蕊连，也可以在list或vector之上實(shí)現(xiàn)。

s.pop()  //刪除棧頂元素

s.push(item)  //創(chuàng)建一個(gè)新元素壓入棧頂游昼，該元素通過拷貝或移動(dòng)item而來甘苍，或者

s.emplace(args)   //由args構(gòu)造

s.top() //返回棧頂元素，但不將元素彈出棧

隊(duì)列適配器

queue采用先進(jìn)先出（FIFO）的存儲(chǔ)和訪問策略烘豌。

queue默認(rèn)基于deque實(shí)現(xiàn)载庭，priority_queue默認(rèn)基于vector實(shí)現(xiàn)。
q.pop()  //返回queue的首元素或priortiy_queue的最高優(yōu)先級(jí)的元素廊佩，但不刪除此元素囚聚。
q.front()  //返回首元素或尾元素，但不刪除此元素标锄。
q.back()  //只適用于queue
q.top()  //只適用于priority_queue顽铸，返回最高優(yōu)先級(jí)元素，但不刪除料皇。
q.push(item)  
q.emplace(args)

priority_queue允許我們?yōu)殛?duì)列中的元素建立優(yōu)先級(jí)谓松。新加入的元素會(huì)排在所有優(yōu)先級(jí)比它低的已有元素之前。飯店按照客人預(yù)定時(shí)間而不是到來時(shí)間的早晚來為他們安排座位践剂，就是一個(gè)優(yōu)先隊(duì)列的例子鬼譬。