std::multimap的使用案例

Question

我不太理解这种数据结构的目的。 std::multimap<K, V> 和 std::map<K, std::vector<V>> 之间有什么区别呢？std::multiset也是一样，它只需要是一个计算K出现次数的 std::map<K, int> 就可以了。这些数据结构的用途是否有所遗漏？

- Puppy

Answer 1

一个反例似乎是必要的。

考虑一个按名称分组的通讯录中的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无法实现的。如果不需要这种行为，您的Object+count方法似乎更快。例如，multiset :: count（）成员说明：

“复杂度：大小对数级别+计数线性级别。”

- Captain Giraffe

---

使用自定义谓词将STL容器发挥到极致的好例子。 - Kerrek SB

这似乎与 map<std::string, std::vector<rest of PhoneEntry>> 非常相似。虽然它与我提出的替代方案不完全相同，但也可以进行分解。 - Puppy

@DeadMG 是的，但正如Alan所指出的那样，对于multiset和vector组合，迭代器的行为非常不同。此外，AdressListCompare并不一定只需要比较一个成员。 - Captain Giraffe

如果将其存储为map<K, vector<V>>，那么数据只会被存储一次。在你的例子中，multiset会重复存储键，因为它是值的一部分。 - Puppy

@DeadMG 很好的观点。我认为我们已经成功地展示了这两种方法之间的重要区别；至少，在处理这样的数据集时考虑这两种方法是很有用的。 - Captain Giraffe

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。

- Alan

Answer 3

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

例如，集合是一组非有序元素，这些元素在{A,B,C} == {B,C,A}中都是唯一的。

- Pepe

---

这完全没有回答这个问题。 - Puppy