Search code examples
c++c++11setstdmapstdset

How to find min/max in std::map like in std::set?

Since both set and map are ordered containers, can the min and the max be found in 0(1) time for std::map like in std::set ? 

// for std::set
// std::set<int> s;
auto min = *s.begin();

auto max = *s.rbegin();

How do I obtain the max and min in O(1) from a std::map ? Other questions here seem to suggest to iterate through the map, but can't we use the ordered properlt of std::map to obtain the result faster ?

Solution

  • Dereference first from the iterator for the key, like this:

    // for std::map<int,string> s
auto minKey = s.begin()->first;
auto maxKey = s.rbegin()->first;

    This works only for keys, not values, because maps are sorted only on their keys.