C++面試題之list和vector的區(qū)別

1.vector數(shù)據(jù)結(jié)構(gòu)

? ? ? ?vector和動(dòng)態(tài)數(shù)組類似，擁有一段連續(xù)的內(nèi)存空間，并且起始地址不變。因此能高效的進(jìn)行隨機(jī)存取，時(shí)間復(fù)雜度為o(1);但因?yàn)閮?nèi)存空間是連續(xù)的，所以在進(jìn)行插入和刪除操作時(shí)，會(huì)造成內(nèi)存塊的拷貝，時(shí)間復(fù)雜度為o(n)。

2.list數(shù)據(jù)結(jié)構(gòu)

? ? ? ?list是由雙向鏈表實(shí)現(xiàn)的，因此內(nèi)存空間是不連續(xù)的。只能通過指針訪問數(shù)據(jù)，所以list的隨機(jī)存取非常沒有效率，時(shí)間復(fù)雜度為o(n);但由于鏈表的特點(diǎn)，能高效地進(jìn)行插入和刪除。

? ? ? ?已知元素是連續(xù)存儲(chǔ)的，當(dāng)我們?cè)谌萜鲀?nèi)添加一個(gè)元素時(shí)，想想會(huì)發(fā)生什么事情：

? ? ? ?如果容器中已經(jīng)沒有空間容納新的元素，此時(shí)，由于元素必須連續(xù)存儲(chǔ)以便索引訪問，所以不能在內(nèi)存中隨便找個(gè)地方存儲(chǔ)這個(gè)新元素。于是，vector 必須重新分配存儲(chǔ)空間，用來存放原來的元素以及新添加的元素：存放在舊存儲(chǔ)空間中的元素被復(fù)制到新存儲(chǔ)空間里，接著插入新元素，最后撤銷舊的存儲(chǔ)空間。如果 vector 容器在在每次添加新元素時(shí)，都要這么分配和撤銷內(nèi)存空間，其性能將會(huì)非常慢，簡(jiǎn)直無法接受。

? ? ? ?對(duì)于不連續(xù)存儲(chǔ)元素的容器，不存在這樣的內(nèi)存分配問題。例如，在 list 容器中添加一個(gè)元素，標(biāo)準(zhǔn)庫(kù)只需創(chuàng)建一個(gè)新元素，然后將該新元素連接在已存在的鏈表中，不需要重新分配存儲(chǔ)空間，也不必復(fù)制任何已存在的元素。

? ? ? ?由此可以推論：一般而言，使用 list 容器優(yōu)于 vector 容器。但是，通常出現(xiàn)的反而是以下情況：對(duì)于大部分應(yīng)用，使用 vector 容器是最好的。原因在于，標(biāo)準(zhǔn)庫(kù)的實(shí)現(xiàn)者使用這樣內(nèi)存分配策略：以最小的代價(jià)連續(xù)存儲(chǔ)元素。由此而帶來的訪問元素的便利彌補(bǔ)了其存儲(chǔ)代價(jià)。

? ? ? ?為了使 vector 容器實(shí)現(xiàn)快速的內(nèi)存分配，其實(shí)際分配的容量要比當(dāng)前所需的空間多一些。vector 容器預(yù)留了這些額外的存儲(chǔ)區(qū)，用于存放新添加的元素。于是，不必為每個(gè)新元素重新分配容器。所分配的額外內(nèi)存容量的確切數(shù)目因庫(kù)的實(shí)現(xiàn)不同而不同。比起每添加一個(gè)新元素就必須重新分配一次容器，這個(gè)分配策略帶來顯著的效率。事實(shí)上，其性能非常好，因此在實(shí)際應(yīng)用中，比起 list 和deque 容器，vector 的增長(zhǎng)效率通常會(huì)更高。

下面列舉了一些選擇容器類型的法則：

1. 如果程序要求隨機(jī)訪問元素，則應(yīng)使用 vector 或 deque 容器。
2. 如果程序必須在容器的中間位置插入或刪除元素，則應(yīng)采用 list 容器。
3. 如果程序不是在容器的中間位置，而是在容器首部或尾部插入或刪除元素，則應(yīng)采用 deque 容器。

4. 如果只需在讀取輸入時(shí)在容器的中間位置插入元素，然后需要隨機(jī)訪問元素，則可考慮在輸入時(shí)將元素讀入到一個(gè) list 容器，接著對(duì)此容器重新排序，使其適合順序訪問，然后將排序后的 list 容器復(fù)制到一個(gè) vector容器。

? ? ? ?如果程序既需要隨機(jī)訪問又必須在容器的中間位置插入或刪除元素，那應(yīng)該怎么辦呢？

? ? ? ?此時(shí)，選擇何種容器取決于下面兩種操作付出的相對(duì)代價(jià)：隨機(jī)訪問 list 容器元素的代價(jià)，以及在 vector 或 deque 容器中插入／刪除元素時(shí)復(fù)制元素的代價(jià)。通常來說，應(yīng)用中占優(yōu)勢(shì)的操作（程序中更多使用的是訪問操作還是插入／刪除操作）將決定應(yīng)該什么類型的容器。

? ? ? ?決定使用哪種容器可能要求剖析各種容器類型完成應(yīng)用所要求的各類操作的性能。

? ? ? ?如果無法確定某種應(yīng)用應(yīng)該采用哪種容器，則編寫代碼時(shí)嘗試只使用 vector 和 lists 容器都提供的操作：使用迭代器，而不是下標(biāo)，并且避免隨機(jī)訪問元素。這樣編寫，在必要時(shí)，可很方便地將程序從使用 vector 容器修改為使用 list 的容器。