Menu
Why is std::set defined as an associative container?
I mean std::map is an associative container because it maps a value to a key, but why is it a set?
345
So what makes it associative? The fact that elements in a set are referenced by their key and not by their absolute position in the container. The key, of course, is the element itself. Think of it as a map where the keys are values are equal and given that, where the duplicate copy of the same content is eliminated.
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e. either ascending or descending.
A set is an Associative container which contains a sorted set of unique objects of type Key. Each element may occur only once, so duplicates are not allowed. There are four kind of Associative containers: set, multiset, map and multimap.
Per the C++ standard, iteration over the elements in an std::set proceeds in sorted order as determined by std::less or by the optional comparison predicate template argument.
The map solution results in "Time Limit Exceeded on Test 3", whereas the set solution results in "Time Limit Exceeded on Test 2", which means that Test 2 is such that the map solution works faster on it than the set solution.
A
setsatisfies all of the requirements of [..] an associative container (23.2.4) [...]
Because it satisfies all pre-conditions of being an associative container, which are described in 23.2.4. and aren't as simple as "maps a key to a value".
The second paragraph even highlights this (or rather, highlights that it is in fact map and multimap have additional functionality over associative containers):
2) Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.4) on elements of Key. In addition, map and multimap associate an arbitrary type T with the Key. The object of type Compare is called the comparison object of a container.
The full paragraph is too large to reproduce here.
81
reference at cplusplus.com
In a set, the key is the value, which must be unique.
Edit:
"Elements in associative containers are referenced by their key and not by their absolute position in the container."
44
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
