4

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 ?

nnrales
  • 1,481
  • 1
  • 17
  • 26

1 Answers1

7

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • beautiful thank you. It seemed to me that there has to be a better way than iterating through it. I though this might be the answer, but wanted to check. – nnrales Dec 01 '16 at 00:19
  • Yeah, I just wanted to find the smallest key. – nnrales Dec 01 '16 at 00:19
  • This answer is very clever, but I found the wording of "Dereference first from the iterator for the key, like this" took me a few parses to grok. Might be worth adding an extra sentence saying that maps are always stored in order so the key of the first/last elements will be smallest/largest respectively. Regardless +1. – Vality Dec 01 '16 at 00:32