| container name | implementation/underlying struct | notes/ sample |
| unordered_set | The value of an element is at the same time its key, that identifies it uniquely.
hash table |
|
| unordered_multiset | much like unordered_set containers, but allowing
different elements to have equivalent values. hash table Internally when an existing value is inserted, the data structure increases its count which is associated with each value. As count of each value is stored in unordered_multiset, it takes more space than unordered_set (if all values are distinct). |
use case: may allow us to insert duplicated items, maybe good for counting?
find(): Searches the container for an element with k as key and returns an iterator to it if found,
To obtain a range with all the elements whose key is k you can use member function equal_range. To just check whether a particular key exists, you can use count. count(): Count elements with a specific key
equal_range():
Returns the bounds of a range that includes all the elements in the container with a key that compares equal to k.
|
| set | store unique elements following a specific order.
the value of an element also identifies it (the value is itself the key, of type T), and each value must be unique. Sets are typically implemented as binary search trees. |
|
| multiple_set | store elements following a specific order, and where multiple elements can have equivalent values.
Multisets are typically implemented as binary search trees. |
sometimes it is used to replace max/mini-heap
( as heap may allow duplicated key, but may has other different value for that struct) , since it allows insert/remove elements, ( of course cost bigger than heap, as it keep the order of the whole set) |
| unordered_map | similar to unodered_set( only have key) using hash, it has :
hash : key->value |
|
| unordered_multimap | much like unordered_map containers, but allowing different elements to have equivalent keys.
hash: key–> multiple values |
equal_range: Returns the bounds of a range that includes all the elements in the container with a key that compares equal to k.
no [] operator for unordered_multimap because values corresponding to a key are not unique, there can be many values associated with a single key so [] operator can not be applied to them. |
| map | store elements formed by a combination of a key value and a mapped value, following a specific order.
Maps are typically implemented as binary search trees. |
|
| multimap | store elements formed by a combination of a key value and a mapped value, following a specific order, and where multiple elements can have equivalent keys.
Multimaps are typically implemented as binary search trees. |
equal_range: Returns the bounds of a range that includes all the elements in the container which have a key equivalent to k.
for the same key, seems there is no order at all ( or just keep as it was inserted?) |
References:
http://www.cplusplus.com/reference/map/multimap/
