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.