为什么multimap允许重复的键值对？

Question

编辑：请注意，我并不是在问为什么multimap不能包含重复的键。

multimap允许包含重复的键-值对背后的原理是什么？（而非键）

#include <map>
#include <string>
#include <iostream>

int
main(int argc, char** argv)
{
    std::multimap<std::string, std::string> m;
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "C"));
    std::cout << m.size() << std::endl;
    return 0;
}

这会打印出3，有点让我惊讶，我期望multimap的行为类似于一组pair，所以我期待结果是2。

直觉上，这与C++的std::map行为不一致，其中insert不总是更改映射（与operator[]相反）。

它背后是否有理由，还是仅仅是随意的呢？

- Alex B

---

也许 std::set<std::pair<std::string, std::string> > > 是你要找的容器？它可以保存两个条目。 - Sjoerd

@Sjoerd 是的，但这不是问题所在。问题是它为什么会表现出这样的行为。我不是在寻找特定问题的解决方案。 - Alex B

这就是为什么我将它作为评论而不是答案。同时也是为了未来寻找解决方案的观众们。 - Sjoerd

"std::map<K, std::set<V>>" 比 "std::set<std::pair<K,V>>" 更好。可惜我不能再编辑我的第一个评论了... - Sjoerd

Answer 1

多重映射（Multimap）只具有按键排序的谓词。它没有确定值是否相等的方法。 值"A"是值"a"的副本吗？如果没有第二个值的谓词，就无法确定。因此，在多重映射中讨论重复值甚至没有意义。

如果您想要一个存储成对数据并且强制保证成对数据的唯一性的容器，请查看 boost::multi_index_container。它非常灵活，但结果需要很多参数。

- MSalters

---

虽然你的回答是合理的，但有一个小细节：我认为第一段反转了因果关系。Multimap不强制每个键对应的值唯一，不是因为它只有针对键的谓词，而是它只有针对键的谓词，正是因为它不强制每个键对应的值唯一。 - Alex B

从某种意义上说，这个问题的逻辑是相反的。你可以有一个不允许重复键值对的容器，但那就不再是std::multimap了。 - MSalters

一个存储一对值并强制保证两部分的唯一性的容器...或者简单地使用std::set< std::pair<std::string, std::string> >。 - bloody

Answer 2

编辑：此回答不再回答当前问题。我将保留它，因为它得到了很多赞，所以它对一些人肯定是有用的。

multimap 中的 multi 表示同一个键值(key)可以出现多次(multiple times)。

标准不对作为值的类型限制，因此不能假设定义了 operator==()。为了不让你的代码结果取决于是否定义了 operator==()，它从未被使用。

std::multimap 不能替代 std::map。正如您注意到的那样，当插入多个相同的键时，它的行为会有所不同。如果想要 std::map 的行为，请使用 std::map。

还有一个 std::multiset。

理由：有时候人们也希望将同一个键的所有旧条目保存下来。 [TBD：在此插入一些例子]

个人而言，我几乎从不使用 std::multimap。如果我想要同一键的多个条目，我通常会依赖于 std::map<std::vector<T> >。

- Sjoerd

---

有人知道std::multimap的一个好用例吗？这将改善我的答案。 - Sjoerd

我知道键不能重复，并在问题的第一句话中说明了这一点。但它会重复键值对，这似乎是不必要的。我看不出有任何用例。 - Alex B

我发现std::multimap比map<K,vector<T>>更容易管理。在频繁添加/删除时可能更有效率。任何1:N映射都适用于multimap。 - edA-qa mort-ora-y

如果需要键查找，则任何可能包含重复项的容器都适合于multimap。我相信任何人都可以想出为什么可能需要在集合中包含重复项的许多原因！ - edA-qa mort-ora-y

@edA-qa map<K,vector<T>> 记录插入的顺序。 map<K,set<T>> 移除重复项（正如 OP 所期望的）。这些都是不使用 std::multimap 的理由。但你说得对，当频繁删除时，std::multimap 可能会更有效率 - 尽管到那时，你最好使用真正的数据库。 - Sjoerd

Answer 3

这些值可以重复，因为它们不需要相互比较。容器除了将它们复制到内部之外，无法对这些值进行其他操作。这使得像 multimap< int, my_class > 这样的类型成为可能。

如果不希望出现重复的键值对，则可以使用 set< pair< T, U > > 并使用 lower_bound 找到给定键的第一个匹配项。

- Potatoswatter

Answer 4

正如您所知，multimap允许具有多个键。由于它不对值的可比性施加任何约束，因此无法检查值是否已经重复。

如果您想要一些允许重复键但不是键值对的字典数据结构，则必须确保值是可比较的。

假设我们有某种游戏，其中有一个二维世界的正方形区域，您可以在区域上放置物品。您可以使用multimap<Field，Item>，这将允许您在该区域上保留两个相同的物品。这里的物品不必是可比较的。

- x13n

Answer 5

我的理解是multimap基于键的查找/插入，而不是值。因此，在插入元素时，重复键上的值是否相同并不影响。

23.3.2 类模板multimap

1 multimap是一种支持等效键（可能包含多个相同键值的副本）并提供基于键快速检索另一类型T值的关联容器。

- dubnde

Answer 6

"multimap"旨在支持“多个”键，而不像简单的"map"那样只支持一个键。由于它允许多个键，因此它不会关心它们的值，所以在您的示例中显示了3个元素。另一个区别是，无法为multimap使用operator []。

- iammilind

Answer 7

使用重复的[map，value]对的一种方法是计算书页上单词出现的次数，无论是零次（因此该单词在multimap中没有条目），还是一次（有一个条目），或者多次（在multimap中有多个make_pair（word，page_number）的出现次数）。我发现这种用法更多是偶然的设计。

- user13619691