vector 表示一段連續(xù)的內(nèi)存區(qū)域每個(gè)元素被順序存儲(chǔ)在這段內(nèi)存中
對(duì)vector 的隨機(jī)訪問比如先訪問元素5 然后訪問15 然后再訪問7 等等效率很高
因?yàn)槊看卧L問離vector起始處的位移都是固定的
但是在任意位置而不是在vector 末尾插人元素則效率很低因?yàn)樗枰汛迦朐赜疫叺拿總€(gè)元素都拷貝一遍類似地刪除任意一個(gè)而不是vector的最后一個(gè)元素效率同樣很低因?yàn)榇齽h除元素右邊的每個(gè)元素都必須被復(fù)制一遍這種代價(jià)對(duì)于大型的復(fù)雜的類對(duì)象來說尤其大
一個(gè)deque 也表示一段連續(xù)的內(nèi)存區(qū)域但
是與vector 不同的是它支持高效地在其首部插入和刪除元素它通過兩級(jí)數(shù)組結(jié)構(gòu)來實(shí)
現(xiàn)一級(jí)表示實(shí)際的容器第二級(jí)指向容器的首和尾
list 表示非連續(xù)的內(nèi)存區(qū)域并通過一對(duì)指向首尾元素的指針雙向鏈接起來從而允許
向前和向后兩個(gè)方向進(jìn)行遍歷在list 的任意位置插入和刪除元素的效率都很高指針必須
被重新賦值但是不需要用拷貝元素來實(shí)現(xiàn)移動(dòng)另一方面它對(duì)隨機(jī)訪問的支持并不好
訪問一個(gè)元素需要遍歷中間的元素另外每個(gè)元素還有兩個(gè)指針的額外空間開銷
下面是選擇順序容器類型的一些準(zhǔn)則
如果我們需要隨機(jī)訪問一個(gè)容器則vector 要比list 好得多
如果我們已知要存儲(chǔ)元素的個(gè)數(shù)則vector 又是一個(gè)比list 好的選擇
如果我們需要的不只是在容器兩端插入和刪除元素則list 顯然要比vector 好
除非我們需要在容器首部插入和刪除元素否則vector 要比deque 好