Chinese Yellow Pages | Classifieds | Knowledge | Tax | IME

c++ multi-set/multi-map, set/map and its unordered version

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
Searches the container for elements whose key is k and returns the number of elements found.
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.
Erase function deletes all instances of values associated with the supplied key.
Find function returns an iterator to any instance of key-value pair among all pairs associated with that key.

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/

 

 

Please rate this


Comments are closed here.