CODEWITHSUNDEEP
c++c++11setstdmapstdset
nnrales
nnrales

Reputation: 1519

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 ?

Upvotes: 4

Views: 5287

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726619

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.

Upvotes: 7

Related Questions