std :: multimap的用例

我不太明白這個數據結構的用途。 std::multimap<K, V>和std::map<K, std::vector<V>>之間有什麼區別。 std::multiset也是如此 - 它可能只是std::map<K, int>，其中int計算了K的出現次數。我是否錯過了這些結構的用法？std :: multimap的用例

來源

2011-06-23 Puppy

我相信'multimap '在結構上等同於'map >'但功能更豐富。我不能保證這一點，所以我會讓它作爲評論。 –

-1

multimap或multiset允許您擁有帶重複鍵的元素。

即一組是，在所有的獨特元件的非有序組{A，B，C} == {B，C，A}

來源

2011-06-23 16:09:06 Pepe

這完全不能回答這個問題。 – Puppy

反例似乎是爲了。

考慮按名稱分組的AdressList中的PhoneEntry。

int AdressListCompare(const PhoneEntry& p1, const PhoneEntry& p2){ 
    return p1.name<p2.name; 
} 

multiset<PhoneEntry, AdressListCompare> adressList; 

adressList.insert(PhoneEntry("Cpt.G", "123-456", "Cellular"));  
adressList.insert(PhoneEntry("Cpt.G", "234-567", "Work")); 
// Getting the entries 
addressList.equal_range(PhoneENtry("Cpt.G")); // All numbers

這對set + count不可行。如果不需要這種行爲，則您的對象+計數方法似乎更快。例如multiset :: count（）成員狀態

「複雜性：對數大小+ 線性計數」。

來源

2011-06-23 16:39:10

+1使用自定義謂詞來良好使用STL容器的好例子。 –

這似乎與'map >'的其餘部分完全相同。雖然與我提議的替代品並不相同，但它也可以分解。 – Puppy

@DeadMG誠然，但正如Alan所指出的，迭代器對於多重集的行爲與向量組合的行爲非常不同。 AdressListCompare也不一定只需要比較一個成員。 –

您可以使用make建議替換，並提取類似的行爲。但接口與處理常規標準容器時會有很大的不同。這些容器的主要設計主題是它們共享盡可能多的接口，使它們儘可能互換，以便可以選擇適當的容器而無需更改使用它的代碼。

例如，std::map<K, std::vector<V>>將有迭代器取消引用std::pair<K, std::vector<V>>而不是std::pair<K, V>。 std::map<K, std::vector<V>>::Count()將不會返回正確的結果，無法解釋向量中的重複項。當然，你可以改變你的代碼來完成糾正這個所需的額外步驟，但是現在你以一種完全不同的方式與容器接口了。你不能在unordered_map或其他一些地圖實現中看到它的性能更好。

從更廣泛的意義上講，您通過處理代碼中的容器實現細節而不是具有處理它自己的業務的容器來打破容器抽象。

完全有可能您的編譯器的實現std::multimap實際上只是一個圍繞std::map<K, std::vector<V>>的包裝。或者它可能不是。對象池分配可能更高效和更友好（哪些向量不是）。

使用std::map<K, int>而不是std::multiset是相同的情況。 Count()不會返回期望值，迭代器不會迭代重複，迭代器將取消引用std::pair<k, int>而不是直接到`K.

來源

2011-06-23 16:57:32 Alan

std :: multimap的用例

回答

相關問題