我聽到很多人說，如果容器中預期的元素數量相對較少，最好使用std::vector而不是std::map，儘管我僅將容器用於查找而不用於迭代。矢量或地圖，哪一個使用？
這背後的真正原因是什麼？
很明顯，map的查找性能不會比矢量的查找性能差（儘管可能是納秒/微秒），它與內存使用情況有關嗎？
在虛擬地址空間的分片中，向量的性能是否比map更好/更差？
我正在使用與Visual Studio（即微軟實現）一起提供的STL庫嗎？它與其他實現有什麼不同？
我推測你正在比較map<A, B>和vector<pair<A, B> >。
首先，在一個非常小的矢量中找到一個項目可能比在地圖中同樣的東西更快，因爲矢量中的所有內存都是連續的（因此可以更好地播放計算機的緩存等等） ，並且在向量中查找某些內容所需的比較次數可能與地圖大致相同。在地圖中查找元素需要在非常大的容器範圍內執行更少的操作。
映射變得比矢量更快的點取決於實現，處理器上，映射中的數據以及處理器緩存中的內存等細微內容。通常情況下，地圖變得更快的點大概是5-30個元素。
另一種方法是使用散列容器。他們通常被命名爲hash_map或unordered_map。名爲hash_map的類不是官方標準的一部分（並且在那裏有一些變體）; std::tr1::unordered_map是。哈希映射通常比查找的普通映射更快，無論它有多少個元素，但它是否更快取決於關鍵是什麼，它如何被散列，你必須處理什麼值以及如何處理密鑰在std :: map中進行比較。它不會像std :: map那樣按照特定的順序來保存東西，但是你說過你並不關心它。如果鍵是整數或指針，我會推薦哈希映射，因爲這些哈希映射非常快。
地圖通常以二叉搜索樹的形式實現，而漫步二叉樹總會帶來一點開銷（執行比較，走路鏈接等）。矢量基本上只是數組。對於非常少量的數據，可能是8或12個元素，有時候對數組進行線性搜索比對二叉搜索樹進行搜索要快。
您可以自己運行一些計時以查看盈虧平衡點的位置 - 搜索四個元素，然後搜索八個，然後十六個等等，爲您的特定STL實現找到最佳位置。
地圖確實傾向於在整個堆中有一堆小的分配，而向量是連續的，因此在迭代所有來自前面的元素的情況下，向量的緩存命中率有時會更好一些回來。
你甚至不需要做線性搜索。 std :: lower_bound在任何已排序的容器上爲您提供二分搜索。當有很多密鑰插入，改變搜索樹的結構時，Map很有用。如果它是一個相當靜態的集合，那麼排序後的向量和lower_bound將很容易地匹配地圖的性能，而不僅僅是幾個元素。當然在實踐中還是值得比較的！ – Zoomulator 2012-11-07 12:14:05
如果您一次完成所有插入操作，然後進行大量查找，則可以在插入時使用矢量並對其進行排序;然後使用lower_bound快速查找。它可能比使用地圖更快，即使是大量的項目。
我想你應該首先使用適合數據的容器。 std :: vector用於在C或pre-STL C++中使用數組的情況：您希望連續的內存塊以快速恆定時間查找來存儲值。應該使用std :: map將鍵映射到值。這裏的主要重疊是一個矢量與以size_t爲關鍵字的映射。在這種情況下，有兩個問題：索引是否連續？如果沒有，你可能會用矢量來浪費記憶。其次，你想要什麼查找時間？一個向量具有恆定的時間查詢，而std :: map通常被實現爲一個RB樹，它具有O（log n）查找時間，甚至一個哈希映射（例如TR1 unordered_map）通常具有更差的複雜度，因爲索引（或其散列）將映射到可以包含多個值的存儲區。
如果是針對帶有成對的矢量：可以使用矢量的元素並使用find來查找元素。但這是一個二分搜索，實際上和std :: map一樣快。
無論如何，嘗試以明顯的方式對數據建模。過早優化往往沒有多大幫助。
「默認情況下，在需要容器時使用向量」 - Bjarne Stroustrup。
否則，我覺得這一點流程圖是很好的幫助：
另一種方式來看待這個，如果是我們談論的小容器，那麼沒有人會需要很長時間才能查找。除非你在非常緊密的循環中搜索這個容器，否則時間上的差異可能可以忽略不計。
在這種情況下，我會尋找哪個容器更符合你想要做的。如果你正在尋找一個特定的值，map的內建find（）方法比創建一個for循環和迭代一個vector更容易（而且使用起來更簡單）。
你的時間可能比幾個納秒更有價值。
基本上，地圖用於查找。
但是，有時可以使用std::vector而不是std::map甚至查找。
如果鍵值對中的元素數量非常少，那麼即使在std::vector<std::pair<x,y>>中，也可以使用鍵進行迭代搜索。
這是因爲散列需要時間，尤其是對於散列字符串和其他像map中的數據操作等操作。
如果你有更多的元素需要查找，並且你想在你有的元素列表中進行頻繁的查找，你只會在std :: map中看到更好的區別。
奇怪的是我發現Java的HashMap比C++ Map快得多。您帖子的最後一段可能描述了原因。 – wmac 2013-05-26 03:44:41
@wmac：對：將Java的`HashMap`與C++`hash_map`或`unordered_map`以及Java的`SortedMap`與C++`map`進行比較會更準確。 – 2015-12-02 23:05:14
當我進行基準測試時，我發現std :: map out的std :: map大約在8000左右，但在某些硬件上低至1000，我使用的代碼可在https：// github上獲得。 com/BlackToppStudios/DAGFrameScheduler/blob/8bfaa295b76f8e58dd4fc21186e1c7f3dd3e323a/tests/dagsizestests.h – Sqeaky 2015-12-24 17:46:45