std::multimap<key, value>和std::map<key, std::set<value>>有什么区别？

Question

std::multimap<key, value>和std::map<key, std::set<value>>有什么区别？

c++dictionarycontainerskey-valuemultimap

104

我发现它们有一个唯一的键和多个值。

- superK

4个回答

58

多重映射存储键值对，其中键和值均可以出现多次。

map<key, set<value>> 只会为特定的键存储每个值一次。为了做到这一点，它将需要比较值，而不仅仅是键。

这取决于您的应用程序是否认为相等的值是等价的，或者您是否希望将它们分别存储。也许它们包含不参与集合比较的不同字段。

- Bo Persson

6

所以，std::multimap<key, value> 就像是 std::map<key, std::multiset<value>>，它们之间的区别在于后者的值是排序的。没错吧？ - superK

3

不，std::multimap<key, value> 允许同一个键出现多次，而 std::map<key, whatever> 要求键的唯一性。 - Yixing Liu

14

map::insert

由于map容器不允许重复的键值，插入操作会对每个要插入的元素进行检查，以确定容器中是否已存在具有相同键值的另一个元素。如果有，该元素不会被插入，其映射值也不会发生任何改变。

另一方面

multimap::insert

可以插入任意数量具有相同键的项。

http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/

- Luka Rahne

这是一个关于map和multimap的区别以及内部工作原理的好链接。链接 - Rndp13

10

后者不要求值可以被排序（通过运算符 operator< 或比较函数），而前者需要。

- Björn Pollex

看起来 operator< 在 map 和 multimap 上的工作方式是相同的？http://en.cppreference.com/w/cpp/container/map/operator_cmp - johnbakers

是的，但我的回答涉及到值的排序。假设您有一个没有排序的类型T。您可以使用它来创建一个std::multimap<U, T>，但您不能使用它来创建一个std::map<U, std::set<T>>。 - Björn Pollex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- typedef · Accepted Answer

std::map是一个关联容器，它允许您将唯一的键与类型值相关联。例如：

void someFunction()
{
    typedef std::map<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    auto it = myMap.find("test");
    if (it != myMap.end())
        std::cout << "value for " << it->first << " is " << it->second << std::endl;
    else
        std::cout << "value not found" << std::endl;
}

std::multimap与std::map相似，但是键不再是唯一的。因此，您可以找到一系列项目而不仅仅是一个唯一项。例如：

void someFunction()
{
    typedef std::multimap<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("test", 45));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    std::pair<auto first, auto second> range = myMap.equal_range("test");
    for (auto it = range.first; it != range.second; ++it)
        std::cout << "value for " << it->first << " can be " << it->second << std::endl;
}

std::set 类似于 std::map，但它不是将键与值相关联。它仅存储键类型，并确保在集合中唯一。

你还有 std::multiset，它遵循相同的模式。

所有这些容器都提供了 O(log(n)) 的查找 / 区间查找访问。