Runtime complexity of STL Map and Multimap

Runtime complexity of STL Map and Multimap

Maps can be thought of as generalized vectors. They allow map[key] = value for any kind of key, not just integers. Maps are often called associative tables in other languages, and are incredibly useful. They're even useful when the keys are integers, if you have very sparse arrays, i.e., arrays where almost all elements are one value, usually 0.
Maps are implemented with balanced binary search trees, typically red-black trees. Thus, they provide logarithmic storage and retrieval times. Because they use search trees, maps need a comparison predicate to sort the keys. operator<() will be used by default if none is specified a construction time.
Maps store <key, value> pair's. That's what map iterators will return when dereferenced. To get the value pointed to by an iterator, you need to say

(*mapIter).second

Usually though you can just use map[key] to get the value directly.

Warning: map[key] creates a dummy entry for key if one wasn't in the map before. Use map.find(key) if you don't want this to happen.

multimaps are like map except that they allow duplicate keys. map[key] is not defined for multimaps. Instead you use lower_bound() and upper_bound(), or equal_range(), to get the iterators for the beginning and end of the range of values stored for the key. To insert a new entry, use map.insert(pair<key_type, value_type>(key, value)).

Header

#include <map>

Constructors

map< key_type, value_type, key_compare > m;	Make an empty map. key_compare should be a binary predicate for ordering the keys. It's optional and will default to a function that uses operator<.	O(1)
map< key_type, value_type, key_compare > m(begin, end);	Make a map and copy the values from begin to end.	O(n log n)

Accessors

m[key]	Return the value stored for key. This adds a default value if key not in map.	O(log n)
m.find(key)	Return an iterator pointing to a key-value pair, or m.end() if key is not in map.	O(log n)
m.lower_bound(key)	Return an iterator pointing to the first pair containing key, or m.end() if key is not in map.	O(log n)
m.upper_bound(key)	Return an iterator pointing one past the last pair containing key, or m.end() if key is not in map.	O(log n)
m.equal_range(key)	Return a pair containing the lower and upper bounds for key. This may be more efficient than calling those functions separately.	O(log n)
m.size();	Return current number of elements.	O(1)
m.empty();	Return true if map is empty.	O(1)
m.begin()	Return an iterator pointing to the first pair.	O(1)
m.end()	Return an iterator pointing one past the last pair.	O(1)

Modifiers

m[key] = value;	Store value under key in map.	O(log n)
m.insert(pair)	Inserts the <key, value> pair into the map. Equivalent to the above operation.	O(log n)

---