帶整數鍵和矢量的地圖之間的區別

Question

矢量是具有整數鍵的unordered_map的特殊形式嗎？這似乎是因爲矢量也有整數鍵。

如果不是，有什麼區別？

Answer 1

主要區別在於數據如何存儲。

A vector將數據存儲在其調整大小的內部數組中，並添加更多元素。 unordered_map內部使用哈希表。

實際上，一個vector可以讓你在後麪攤銷恆定時間插入（它需要調整大小和複製/移動所有內容），按索引進行恆定時間訪問，以及直到時間的插入和刪除（所有後續元素必須移位）。另外，由於vector是連續的，因此可以將它傳遞給期望c樣式數組的函數。

unordered_map通過鍵爲您提供分期恆定時間查找（因爲散列並不完美，碰撞迫使查找遍歷內部鏈表），攤銷常量時間插入和刪除。

參見：http://en.cppreference.com/w/cpp/container/unordered_map 和：http://en.cppreference.com/w/cpp/container/vector

Answer 2

不可以，vector中的索引是連續的，在map中不是必須的。

另外，vector中的值保證在連續存儲器中，而不是在map中。

這兩個意味着兩個大多數操作的複雜性不同。

Answer 3

向量是一個數組周圍的容器。

無序映射是圍繞二叉樹的容器。

這意味着它們具有不同的性能特徵。一些例子：

• 訪問由索引的元素是在 矢量/陣列的常數時間的操作，但在二叉樹的對數時間的操作。 都很便宜，但在矢量上更快。
• 增加矢量的容量是昂貴的（線性時間），但是對於二叉樹（對數時間）而言便宜。