Remarks
- To use any of
std::map
or std::multimap
the header file <map>
should be included.
std::map
and std::multimap
both keep their elements sorted according to the ascending order of keys. In case of std::multimap
, no sorting occurs for the values of the same key.
- The basic difference between
std::map
and std::multimap
is that the std::map
one does not allow duplicate values for the same key where std::multimap
does.
- Maps are implemented as binary search trees. So
search()
, insert()
, erase()
takes Θ(log n) time in average. For constant time operation use std::unordered_map
.
size()
and empty()
functions have Θ(1) time complexity, number of nodes is cached to avoid walking through tree each time these functions are called.