What's the difference between std::multimap<key, value> and std::map<key, std::set<value> >
Solution 1
The multimap stores pairs of (key, value) where both key and value can appear several times.
The map<key, set<value>>
will only store each value once for a specific key. To do that, it will have to be able to compare the values, not just the keys.
It depends on your application if the values that compare equal are equivalent, or if you wish to store them separately anyway. Perhaps they contain fields that are different but do not take part in the comparison for the set.
Solution 2
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.
Solution 3
map::insert
Because map
containers do not allow for duplicate key values, the insertion operation checks for each element inserted whether another element exists already in the container with the same key value if so, the element is not inserted and its mapped value is not changed in any way.
on the other hand
multimap::insert
can insert any number of items with the same key.
http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/
Solution 4
The latter requires that the values can be ordered (either via operator<
or a comparison-function), the former does not.
大宝剑
Updated on July 08, 2022Comments
-
大宝剑 almost 2 years
I found that they have one key and multiple values which is unique.
-
大宝剑 over 12 yearsSo, a std::multimap<key, value> is like a std::map<key, std::multiset<value> >, the difference between them is that the later's values are sorted. Is that right?
-
johnbakers almost 11 yearsIt would appear operator< works the same on either map or multimap? en.cppreference.com/w/cpp/container/map/operator_cmp
-
Björn Pollex almost 11 yearsYes, but my answer referred to the ordering of the values. Suppose you have a type
T
that as no ordering. You can use it to create anstd::multimap<U, T>
, but you cannot use to the create anstd::map<U, std::set<T> >
. -
vancexu about 10 yearsIn multimap function, this line
std::pair<auto first, auto second> range = myMap.equal_range("test");
doesn't work, becauseerror: 'auto' not allowed in template argument
. Useconst auto range = myMap.equal_range("test")
instead. -
Rndp13 almost 9 yearsGood link on the both the difference and how it works internally. link
-
lolololol ol over 7 yearsmapType? Shouldn't it be MapType on line 4?
-
463035818_is_not_a_number over 6 yearsnot sure who was first, but one is obviously a copy paste of the other : cppbuzz.com/What-is-difference-between-map-and-multimap
-
typedef over 6 yearsahah, cppbuzz is scraping StackOverflow or what?, I wrote this answer myself years ago when I was still daily coding in c++. And there is indeed a typo line 4, thanks @lololololol
-
typedef over 6 years(and their copy/paste failed, they do not even display types in template std::map declaration : std::map<std::string, int>)
-
Yixing Liu almost 6 yearsNo,
std::multimap<key, value>
allows the same key to appear multiple times whereasstd::map<key, whatever>
requires the uniqueness ofkey
. -
L. F. almost 5 years@typedef Someone else scraping your work is a serious problem. In such cases, the correct action is to use the "contact us" form. See meta.stackexchange.com/a/200178.