20

编辑： 请注意，我不是在问为什么 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[]）。

它背后有什么理由，还是只是任意的？

4

7 回答 7

19

Multimap 仅具有对键进行排序的谓词。它无法确定值是否相等。值“A”是值“a”的副本吗？如果没有值的第二个谓词，就没有任何意义。因此，在多图中谈论重复值甚至没有意义。

如果您想要一个存储对并强制对的两个部分唯一性的容器，请查看boost::multi_index_container. 它非常灵活，但结果需要大量参数。

于 2011-04-12T08:31:21.697 回答
12

编辑：此答案不再回答当前问题。我会保持原样，因为它得到了很多人的支持，所以它一定对某些人有用。

multi inmultimap表示同一个键可以出现多次。

该标准对用作值的类型没有限制，因此不能假设operator==()已定义。因为我们不希望您的代码结果取决于是否定义了 operator==()，所以它永远不会被使用。

std::multimap不是替代品std::map。正如您所注意到的，当多次插入相同的密钥时，它的行为会有所不同。如果您想要std::map的行为，请使用std::map.

还有一个std::multiset。

理性：有时人们也想保留同一个键的所有旧条目。[待定：在此处插入一些示例]

就个人而言，我几乎没有使用过std::multimap. 如果我想要同一个键的多个条目，我通常依赖std::map<std::vector<T> >.

于 2011-04-12T08:14:11.900 回答
2

允许这些值重复，因为它们不需要相互比较。除了将它们复制进去之外，容器不能对这些值做任何事情。这使得像multimap< int, my_class >.

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

于 2011-04-12T08:39:18.757 回答
1

如您所知，multimap允许有多个键。由于它对值的可比性没有任何限制，因此无法检查值是否没有加倍。

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

假设我们有一个游戏，其中有一个 2D 的正方形世界，你可以在场地上放置物品。您可以拥有multimap<Field, Item>，这将允许您在场上保留两个相同的项目。项目不必在这里进行比较。

于 2011-04-12T08:21:07.563 回答
1

我的推理是多图基于键查找/插入而不是值。因此，重复键上的值是否相同在插入元素时不起作用。

23.3.2类模板多图

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

于 2011-04-12T09:53:47.413 回答
0

与简单的“map”不同， “multimap”旨在支持“多个”键。由于它允许多个键，因此不会打扰它们的值，因此它在您的示例中显示了 3 个元素。另一个区别是，一个不能有operator []for multimap。

于 2011-04-12T08:25:40.280 回答
0

A use of duplicate [map,value] pairs is to count the number of occurrences of say a word on a page of a book, be it no times, thus no entry in the multimap for that word, be it once with one entry, or more than once with the number of occurrences in multimap for make_pair(word, page_number). It was more by accident that design that I found this usage.

于 2020-05-26T11:32:34.393 回答