What's the difference between std::multimap<key, value> and std::map<key, std::set<value> >

Question

I found that they have one key and multiple values which is unique.

Answer 1

A std::map is an associative container, that allows you to have a unique key associated with your type value. For example,

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;
}

A std::multimap is equal to a std::map, but your keys are not unique anymore. Therefore you can find a range of items instead of just find one unique item. For example,

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;
}

The std::set is like an std::map, but it is not storing a key associated to a value. It stores only the key type, and assures you that it is unique within the set.

You also have the std::multiset, that follows the same pattern.

All these containers provide an O(log(n)) access with their find / equal_range.