std::multimap 的用例

Question

我不太明白这个数据结构的用途。

std::multimap<K, V>

和

std::map<K, std::vector<V>>

有什么区别。

std::multiset

也是如此 - 它可能只是

std::map<K, int>

，其中 int 计算 K 出现的次数。我是否遗漏了这些结构的用途？

Answer 1

一个反例似乎是合适的。

考虑按名称分组的地址列表中的 PhoneEntry。

bool AddressListCompare(const PhoneEntry& p1, const PhoneEntry& p2){
    return p1.name<p2.name;
}

multiset<PhoneEntry, AddressListCompare> addressList;

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

这对于 set+count 来说是不可行的。 如果不需要这种行为，您的对象+计数方法似乎会更快。例如 multiset::count() 成员状态

“复杂性：大小的对数+ 计数呈线性。”

Answer 2

您可以使用您建议的替换，并提取类似的行为。 但这些接口与处理常规标准容器时的接口有很大不同。 这些容器的一个主要设计主题是它们共享尽可能多的接口，使它们尽可能可互换，以便可以选择适当的容器，而无需更改使用它的代码。

例如，

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。

Answer 3

多重映射或多集允许您拥有具有重复键的元素。

即集合是一组无序的元素，它们都是唯一的，因为 {A,B,C} == {B,C,A}