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的用例

回答

相关问题