多重映射相对于向量映射有什么优势？

Question

我不理解为什么需要multimap，因为我们可以创建一个map的向量或集合版本。 对我来说唯一的区别是:

• 在multimap中使用equal_range获取键的元素，在map of vectors中我们使用[]运算符并具有元素的向量。
• 在multimap中使用multimap.insert(make_pair(key,value))添加元素，在map_of_vectors中使用map_of_vectors[key].push_back(value)。

所以为什么要使用multimap呢？对我来说，拥有一个向量比两个迭代器更好，可以获得键的所有值。

这个问题也适用于unordered_map的向量和unordered_multimap。

- Mariusz Pawelski

---

我必须承认，我从未完全理解“multimap”的用途 :/ - Matthieu M.

我有点晚回答这个问题，但multimap比vector的map消耗更多的内存，因为它需要额外的指针。我使用它们的唯一原因是如果我想保留每个元素的键（使用push_back不会保留它）。 - Jcao02

Multimap非常适合于不仅想要跟踪具有不同值的重复键，而且还想在任何时候删除任何键/值对的情况。向量映射不适用于此，虽然您可以使用列表映射，但使用multimap更方便。 - richizy

虽然我理解你的观点（而且我也不倾向于使用multimap），但是同样的事情也可以用map<K, V>和set<pair<K, V>, cmp_first<K, V>>来表示，其中cmp_first比较.first成员。 - lorro

集合的映射：https://dev59.com/R2oy5IYBdhLWcg3wYM2B - Ciro Santilli OurBigBook.com

Answer 1

我认为这取决于具有相同键的所有值是否具有您想要解决的关系。

例如，您是否经常浏览具有键X的所有元素，或将它们传递给函数等？那么在它们已经在自己的单独容器中时更方便，您可以直接进行访问。

然而，如果您只是拥有可能共享相同键值的项目集合，为什么要在其中使用向量呢？使用迭代器遍历 multimap 比在 map、vector 情况下进行嵌套 for 循环更方便。

另一种看待这个问题的方式：如果每个键有多个条目非常普遍，则在 map、vector 情况下您的结构更有效。如果它们很少发生，那么情况就相反。

- ypnos

---

谢谢。你和Artyom的回答让我更了解了一些区别。然而我仍然不认为multimap在现实生活中像vector映射那样有用。但这只是我的个人观点 ;) - Mariusz Pawelski

我的实际结论是：使用multimap，您可以拥有覆盖整个结构的迭代器范围，但这些begin/end迭代器将迭代键和值对（可能不方便）。使用map<...,vector>遍历整个结构更加复杂，但您可以拥有相等序列的仅值的begin/end迭代器。 - Jarek C

Answer 2

multimap<x, y>和map<x, vector<y>>之间有许多重要的区别。

一旦您将一个值插入到multimap中，您就知道该迭代器会保持有效，直到您将其删除，这是一个非常强大的属性，在向量映射中无法实现。

multimap<x,y>::iterator p=mymap.insert(make_pair(a,b));

当你从map中删除迭代器时，它仍然有效，而在第二种情况下，每次向vector添加新条目时，迭代器都会失效。

此外，请注意，map<x，vector<y>>可能具有现有键的空值集，而multimap则不会。

这些是行为差异的不同事物。

老实说，在某些不提供multimap库的语言中，我想念multimap。

- Artyom

---

虽然迭代器失效的角度很有意思，但你的陈述“每次向向量添加新条目时它都会失效”在实践中并不完全正确。只有在向量调整大小时才会使迭代器失效，否则不会……尽管我们通常不知道/不关心它何时调整大小，但我们不应该设计我们的代码来围绕调整大小，并且应该假设迭代器在插入时失效！ - Nawaz

@Nawaz 考虑插入（添加新的）和擦除。 - Gelldur