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

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

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

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

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

? ? ? ?已知元素是連續(xù)存儲的，當我們在容器內(nèi)添加一個元素時，想想會發(fā)生什么事情：

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

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

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

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

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

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

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

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

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

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

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