Q

載體或多重映射困境

c++
stl

2011-09-08 66 views 0 likes

0

我有是否有一個multimap <int key, int value>或維持含有對應到int密鑰的所有值的矢量的矢量的兩難境地。載體或多重映射困境

我很感興趣，這一定INT鍵查找該值時，執行速度更快。

2011-09-08 vedran

+3

您是否嘗試過並使用您域中的一些典型數據來分析結果？ – Mankarse

+0

我只是最近才嘗試使用分析工具AMD CodeAnalyst，但我仍然不太熟練。對不起，但我是這個世界上的新人。：/ – vedran

A

回答

4

如果你想有一個multimap，而不僅僅是一個map，替代將可能是一個vector< list<int> >或類似的東西（其實是multimap或多或少與list元素類型map）。

一般來說，vector查找更快：這是O(1)爲陣VS O(log n)在地圖（在這兩個情況下，我還不算搜索到list/vector/set /任何用於「多」部分）。但，使用vector，你必須讓它大如您想使用的最大int鍵;如果您的密鑰是連續的，這不是問題，但是如果您的索引稀疏，multimap可能是更好的選擇。另一方面，如果你不需要有序遍歷，unordered_multimap（它實際上是一個哈希表）可能是兩個世界中最好的：你可以得到類似數組的樣本O(1)，而不必保留一個巨大的空數組。。

2011-09-08 10:01:10

1

我會建議map<int, vector<int>>

因爲一旦您完成您所有的值的矢量地圖搜索。

否則你的解決方案將需要每個值的新搜索

2011-09-08 09:57:55

+2

'multimap'具有'equal_range'函數，所以你不需要爲每個值重新搜索。 – Mankarse

+0

這不完全正確。一個典型的實現是樹結構，所以'equal range'函數只是從給定的起點遍歷樹。 –

+0

@EdHeal：從給定的起點遍歷樹有什麼問題？如果它比遍歷向量慢，它只是_marginally_所以。 –

1

我想你是在做過早的優化。這並不好，因爲只有在使用分析器的情況下才能進行優化。不要浪費時間，並根據您的需求使用專用容器。

2011-09-08 10:00:03 Camelot

+2

在某種程度上，當然。儘管不要太晚地分析剖析，因爲如果你選擇了錯誤的容器，並且你的代碼不容易與容器模塊化，那麼你將會有一個噩夢在稍後改變它。你應該爲這項工作選擇正確的容器，有時候，根據「速度」（實際上是複雜性增長）來思考可以幫助你認識到這個工作的正確容器是什麼。 –

+0

香草薩特在他的101條建議中寫到了這件事。你的代碼必須基於抽象而不是像容器這樣的細節。因此，在將來的重構中，它將會改變混凝土容器 – Camelot

+0

正確的，你選擇的數據模型是這些抽象的一部分......即使代碼中的特定類型不是。 –

2

如果你的鑰匙是連續去的載體，但如果你的密鑰是大洞，然後在地圖上會更好（因爲你不會有存儲「空」的記載爲矢量），我會說，再加上它會讓你更容易計算你有多少記錄等。性能智慧的向量基於數組，因此查找速度通常更快（因爲映射必須通過幾條數據才能執行查找）。

2011-09-08 10:00:36

4

忘記哪個是「更快」。您可以稍後進行簡介，但不要迷戀這一點。更重要的是，一種方法可以使您的存儲空間更少，而另一種方法則不會 - 專注於此並決定哪種方法最適合您的問題。

2011-09-08 10:15:12

相關問題