面試題:vector和map的差別，異同。空間分布，100萬資料存哪個比較合适。

文章目錄

• 一、 疊代器差別
• 二、vector
• 三、Map、Set
• 四、vector_map 為什麼比map效率高
• 五、如何選擇
• 六、容器選擇原則
• 七、效率對比

一、 疊代器差別

①vector為順序容器，erase疊代器不僅使所有指向被删元素的疊代器失效，而且使被删元素之後的所有疊代器失效，是以不能使用erase(iter++)的方式，但是erase的傳回值為下一個有效的疊代器：可以這樣使用：

for( iter = c.begin(); iter != c.end(); )

iter = c.erase(iter);

②erase疊代器隻是被删元素的疊代器失效：是以可以這樣使用：

for( iter = c.begin(); iter != c.end(); )

c.erase(iter++);

正因為：map erase 會使被删元素的疊代器失效：是以在使用map iterator時候要注意：

一種很常見的錯誤是：

for ( map<int, string>::iterator it = str_map.begin(); it!=str_map.end(); it++ ) {

if ( some_condition )

str_map.erase(it);

}

删除操作會使it亂掉，再使用it++就出錯了。正确的做法是：

for (map<int, string>::iterator it = str_map.begin(); it != str_map.end()😉

{

if (some_condition)

{

str_map.erase(it++);

}

else

{

it++;

}

}

③Map可以通過key查找元素，而vector查找元素也類似，通過值查找；

④對于vector的值得注意的地方，可以對vector調用排序算法，舉例如下：

typedef struct {

std::string strName;

int money;

}company_person;

然後可以按照strName進行排序；我在一個項目中用到過這個，在一個項目中，用戶端以随機的發送strName，然後在服務端對他們進行重新排序；

⑤map和vector 插入元素的方式不一樣，map沒有push_back這樣的函數，隻有insert依次插入元素，或者直接通過構造函數初始化；

二、vector

向量 相當于一個數組。在記憶體中配置設定一塊連續的記憶體空間進行存儲，支援更新檔大小的存儲。當超過已配置設定的空間是，會整體重新配置設定一塊記憶體進行存儲。

優點:

• 1、不指定一塊連續記憶體進行存儲，可以像數組一樣操作。
• 2、随機通路友善，支援下标通路和vector.at()操作。
• 3、節省空間。

缺點:

• 1、在内部進行插入删除，效率較低。
• 2、隻能在末端進行pop和push。
• 3、當動态長度超過預設配置設定大小後，要整體重新配置設定、拷貝和施放。

三、Map、Set

• Map是STL的一個關聯容器，它提供一對一（其中第一個可以稱為關鍵字，每個關鍵字隻能在map中出現一次，第二個可能稱為該關鍵字的值）的資料處理能力，由于這個特性map内部的實作自建一顆紅黑樹(一種非嚴格意義上的平衡二叉樹)，這顆樹具有對資料自動排序的功能。
• set是集合，set中不會包含重複的元素，這是和vector的第一個差別，第二個差別是set内部用平衡二叉樹實作，便于元素查找，而vector是使用連續記憶體存儲，便于随機存取。

四、vector_map 為什麼比map效率高

• vector是線性存儲，map是二叉樹樹形，是以vector記憶體通路的局部性更好。
• vector, 一次配置設定一個比較大的空間（2^n的配置設定方式）， map每次都需要 new 或delele 一個樹結點, 記憶體配置設定是很耗時的。
• vector_map, 可以在資料構造階段，使用push_back, 填充完，資料後調用一次sort就可以了（快速排序或堆排序）， 而map每次insert都是一次查找和樹的旋轉操作，整個過程就像是個插入排序。
• vector_map, 中的查找，而二分查找，時間複雜度是穩定的log(n), 而map是在log(n) 和 2* log(n)之間 (因為map是紅黑樹樹實作，不是平衡二差樹)。
• vector比map消耗更少的記憶體，vector内部是數組，輔助資料也很少， map是樹形結構，有至少3個指針來維持關系。

五、如何選擇

當我們需要使用鍵值對時，我們應該綜合考慮記憶體和效率兩方面。以下是本人的一些個人建議：

1.元素為pair的vector

1）當vector不會頻繁的在中間或者清單頭插入、删除，且清單有序維護的成本低時，可以考慮使用vector，并利用二分查找來查找指定元素；

2）當資料量較大，記憶體不足以使用unordered_map時，應當使用vector替代；

2.map

1）當資料量不大，并且key的類型無法計算hash值，可以考慮使用map替代vector，以将我們從vector清單有序的維護中解放出來；

2）當資料量不大，且我們需要有序的通路鍵值對時，可以考慮使用map替代unordered_map；

3.unordered_map

1）在記憶體允許并且我們不要求有序的通路所有元素的情況下，我們應該盡量使用unordered_map；

六、容器選擇原則

是以在實際使用時，如何選擇這幾個容器中哪一個，應根據你的需要而定，一般應遵循下面的原則：

1、如果你需要高效的随機存取，而不在乎插入和删除的效率，使用vector。

2、如果你需要大量的插入和删除，而不關心随機存取，則應使用list。

3、如果你需要随機存取，而且關心兩端資料的插入和删除，則應使用deque。

4、如果你要存儲一個資料字典，并要求友善地根據key找value，那麼map是較好的選擇。

5、如果你要查找一個元素是否在某集合記憶體中，則使用set存儲這個集合比較好。

七、效率對比

基本結論：

1、unordered_map比map快

2、vector查找14次，基本和unordered_map查找一次耗時相當（int和string做key差别不大）

3、string作key，vector查詢100次，基本和map查詢一次耗時相當；int作key，vector查詢28次，基本和map查詢一次耗時相當

4、boost的unordered_map和map與STL的效率基本相同

是以：抛棄map，用unordered_map吧。如果明确資料量小，比如小于14個，就用vector或數組，效率更高。