Menu
In C++ by default both std::set and std::multiset have std::less<T> as their comparator. Can anyone please explain how does std::multiset allow duplicates and std::set does not?
930
The essential difference between the set and the multiset is that in a set the keys must be unique, while a multiset permits duplicate keys.
In Set duplicate values are not allowed to get stored. On other hand in case of MultiSet we can store duplicate values. In case of Set, one cannot change the value once it gets inserted however we can delete or insert it again. However in case of MultiSet also we cannot change the value once get inserted.
These objects are all different when viewed as multisets, although they are the same set, since they all consist of the same elements. As with sets, and in contrast to tuples, order does not matter in discriminating multisets, so {a, a, b} and {a, b, a} denote the same multiset.
Multisets are a type of associative containers similar to the set, with the exception that multiple elements can have the same values. Some Basic Functions associated with multiset: begin() – Returns an iterator to the first element in the multiset –> O(1)
Both start with the equivalent an upper_bound on the existing contents to find the correct insertion point for the new item.
std::set then checks whether that found an existing item with a key equal to the new key, and if so returns, signaling failure.
std::multiset just inserts the new item at that point (and if it didn't return in the step above, std::set does the same).
144
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
