STL Map: Foundation Skills

MSVC has very good STL support.

Consequently, one owes it to owns good self to know the STL well in order to harness it to maximum power in MSVC-exploiting programmaction. One knows STL well if one knows all the data structures, methods and time complexities of using the various STL methods.

The first super-basic thing we will cover is iterators on a map.

map::lower_bound - returns an iterator pointing to first element in a container whose key is not < (but possibly equal to) x, where x is the argument to lower_bound. So map::lower_bound returns an iterator the the lowest value in the map. The elements of a map are ordered by the key. Complexity is logarithmic in size.

map::upper_bound(x) though returns an iterator to the key whose value is STRICTLY greater than x. then doing map.erase(result-of-lbound, result-of-ubound), will delete all elements with keys in the range [lbound,ubound).

STL multimap ("multi-key map") also has similar iterator functions. In fact, definition of lower_bound and upper_bound is same for map and multimap.

For completeness, we describe the equal_range(x) function. This returns a pair of iterators demarcating the start and end of a range for elements equal to x in the map.