C++常見(jiàn)模板類的內(nèi)部實(shí)現(xiàn)以及特性總結(jié)

前言：面試官總是喜歡問(wèn)數(shù)據(jù)結(jié)構(gòu)的具體實(shí)現(xiàn)，所以今晚總結(jié)下，爭(zhēng)取下次不會(huì)再回答不出來(lái)！唉，悲劇的我~

1. vector

（1）實(shí)現(xiàn)方式：

vector內(nèi)部由數(shù)組實(shí)現(xiàn)，使用連續(xù)的內(nèi)存存儲(chǔ)，屬于順序存儲(chǔ)結(jié)構(gòu)。支持不指定vector大小的存儲(chǔ)。STL內(nèi)部實(shí)現(xiàn)時(shí)，首先分配一個(gè)非常大的內(nèi)存空間預(yù)備進(jìn)行存儲(chǔ)，即capacity()函數(shù)返回的大小，當(dāng)超過(guò)此分配的空間時(shí)再整體重新放分配一塊內(nèi)存存儲(chǔ)。通常此默認(rèn)的內(nèi)存分配能完成大部分情況下的存儲(chǔ)。

（2）優(yōu)點(diǎn)：

• 不需要指定內(nèi)存大小，即可以像數(shù)組一樣操作，但可以進(jìn)行動(dòng)態(tài)操作，如：push_back()，pop_back()，insert()等。
• 隨機(jī)訪問(wèn)方便,可以隨機(jī)訪問(wèn)vector內(nèi)任意一個(gè)元素，即支持[ ]操作符和vector.at()。
• 節(jié)省空間。

（3）缺點(diǎn)：

• 在內(nèi)部進(jìn)行插入刪除操作效率低，尤其是在頭部進(jìn)行插入。
• 只能在vector的最后進(jìn)行push和pop操作，不能在vector的頭進(jìn)行push和pop。
• 當(dāng)動(dòng)態(tài)添加的數(shù)據(jù)超過(guò)vector默認(rèn)分配的大小時(shí)要進(jìn)行整體的重新分配、拷貝與釋放。

2. list

（1）實(shí)現(xiàn)方式：

list內(nèi)部使用雙向鏈表實(shí)現(xiàn)，使用的是非連續(xù)的內(nèi)存空間進(jìn)行存儲(chǔ)，每一個(gè)結(jié)點(diǎn)都包括一個(gè)信息塊Info、一個(gè)前驅(qū)指針Pre、一個(gè)后驅(qū)指針Post?？梢圆环峙浔仨毜膬?nèi)存大小方便的進(jìn)行添加和刪除操作。

（2）優(yōu)點(diǎn)：

• 不使用連續(xù)內(nèi)存完成動(dòng)態(tài)操作。
• 在內(nèi)部進(jìn)行插入和刪除操作方便，不需要拷貝和移動(dòng)數(shù)據(jù)，只需要改變指針即可。
• 可在list的兩端進(jìn)行push、pop操作。

（3）缺點(diǎn)：

• 不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)，即不支持[ ]操作符和at()操作。
• 相對(duì)于verctor占用內(nèi)存多

3. deque

（1）實(shí)現(xiàn)方式：

deque基于雙端隊(duì)列來(lái)實(shí)現(xiàn)，內(nèi)部由一段一段（分塊）的連續(xù)空間構(gòu)成。vector是單向開(kāi)口的連續(xù)線性空間，deque則是一種雙向開(kāi)口的連續(xù)線性空間。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續(xù)空間，串接在整個(gè)deque的頭端或尾端。deque的最大任務(wù)，便是在這些分段的定量連續(xù)空間上，維護(hù)其整體連續(xù)的假象，并提供隨機(jī)存取的接口。

（2）優(yōu)點(diǎn)：

• deque在隊(duì)列的兩端放置元素和刪除元素是高效的，而向量vector只是在插入序列的末尾時(shí)操作才是高效的。
• deque沒(méi)有所謂的capacity觀念，因?yàn)樗莿?dòng)態(tài)地以分段連續(xù)空間組合而成，隨時(shí)可以增加一段新的空間并鏈接起來(lái)。
• deque容器支持對(duì)所有元素的隨機(jī)訪問(wèn)，即可以進(jìn)行[]和at()操作。

（3）缺點(diǎn)：

• 在deque容器的中間insert或erase元素效率比較低。
• deque內(nèi)部數(shù)據(jù)結(jié)構(gòu)比較復(fù)雜。

4. set和multiset

（1）實(shí)現(xiàn)方式：

set和multiset的內(nèi)部均使用一種非常高效的平衡檢索二叉樹(shù)：紅黑樹(shù)來(lái)實(shí)現(xiàn)。

（2）特性：

• set中每個(gè)元素必須是唯一的，不允許出現(xiàn)鍵值重復(fù)，內(nèi)部所有的元素都會(huì)被自動(dòng)按照升序來(lái)排序，每個(gè)元素的值不能用迭代器來(lái)改變，可以理解為一個(gè)集合?？梢赃M(jìn)行insert()，erase()，find()，count()，clean()等操作，注意set的count()只能返回0或者1。
• multiset和set的區(qū)別在于multiset的元素可以相同，即內(nèi)部可以出現(xiàn)重復(fù)的鍵值。multiset內(nèi)部所有的元素同樣自動(dòng)按照升序來(lái)排序。multiset的基本操作和set類似，需要注意的是multiset的count()操作返回值可以大于1。而進(jìn)行刪除操作erase()時(shí)會(huì)刪除所有值相同的key，如對(duì){1,1,2}進(jìn)行erase(1)后會(huì)變成{2}。
• set和multiset都引用<set>的頭文件，時(shí)間復(fù)雜度均為，效率非常高。

5. map和multimap

（1）實(shí)現(xiàn)方式：

map和multimap同樣采用紅黑樹(shù)來(lái)實(shí)現(xiàn)。

（2）特性：

• map提供鍵和值一對(duì)一的映射關(guān)系，每個(gè)鍵不允許重復(fù)，不允許修改，但是鍵對(duì)應(yīng)的值是可以修改的。map的內(nèi)部元素自動(dòng)按照鍵進(jìn)行升序排序，因此不能對(duì)map用sort函數(shù)。map提供下標(biāo)操作符，可直接存取元素，即可以使用[]和at()操作。
• multimap提供鍵和值一對(duì)多的映射關(guān)系，但multimap的鍵可以多次出現(xiàn)。multimap的內(nèi)部元素同樣會(huì)根據(jù)key自動(dòng)對(duì)元素進(jìn)行排序，但是multimap不支持使用[]和at()操作。multimap可以通過(guò)count()函數(shù)計(jì)算一個(gè)key值包含多少個(gè)值。

6. hash_map

（1）實(shí)現(xiàn)方式：

hash_map內(nèi)部基于hash table（哈希表）來(lái)實(shí)現(xiàn)。 最大的優(yōu)點(diǎn)就是把數(shù)據(jù)的存儲(chǔ)和查找消耗的時(shí)間大大降低，幾乎可以看成是常數(shù)時(shí)間，但代價(jià)是消耗比較多的內(nèi)存。相當(dāng)于用空間換時(shí)間。

（2）與map對(duì)比：

• 構(gòu)造函數(shù)。hash_map需要hash函數(shù)（等于函數(shù)）；map只需要比較函數(shù)（小于函數(shù)）。
• 存儲(chǔ)結(jié)構(gòu)。hash_map采用hash表存儲(chǔ)，map一般采用紅黑樹(shù)(RB Tree)實(shí)現(xiàn)。因此其memory數(shù)據(jù)結(jié)構(gòu)是不一樣的。

總結(jié)

1. 如果需要高效的隨機(jī)存取，不在乎插入和刪除的效率，使用vector
2. 如果需要大量的插入和刪除元素，不關(guān)心隨機(jī)存取的效率，使用list
3. 如果需要隨機(jī)存取，并且關(guān)心兩端數(shù)據(jù)的插入和刪除效率，使用deque
4. 如果打算查找一個(gè)元素是否存在于某集合中，唯一存在的情況使用set，不唯一存在的情況使用multiset
5. 如果打算存儲(chǔ)數(shù)據(jù)字典，并且要求方便地根據(jù)key找到value，一對(duì)一的情況使用map，一對(duì)多的情況使用multimap

參考文獻(xiàn)：

1. https://blog.csdn.net/alex_xhl/article/details/37692297
2. https://blog.csdn.net/terence1212/article/details/52487656
3. https://blog.csdn.net/wl_ss/article/details/78065182
4. https://blog.csdn.net/aa4790139/article/details/20617023
5. https://blog.csdn.net/xiajun07061225/article/details/7459206
6. http://www.cnblogs.com/hdk1993/p/5811577.html
7. https://blog.csdn.net/weixin_35909255/article/details/70757138
8. https://blog.csdn.net/wl_ss/article/details/78072909
9. https://blog.csdn.net/chen134225/article/details/81744367
10. https://www.cnblogs.com/SWiper/p/6617774.html
11. https://blog.csdn.net/hero_myself/article/details/52312644
12. https://blog.csdn.net/sinat_36165006/article/details/55803329
13. https://www.cnblogs.com/engineerLF/p/5393006.html