68

I have a std::set<int>, what's the proper way to find the largest int in this set?

Paolo Forgia
  • 6,202
  • 8
  • 42
  • 57
leeeroy
  • 10,906
  • 17
  • 49
  • 52

6 Answers6

118

What comparator are you using?

For the default this will work:

if(!myset.empty())
    *myset.rbegin();
else
    //the set is empty

This will also be constant time instead of linear like the max_element solution.

CTT
  • 16,045
  • 6
  • 40
  • 36
  • 2
    Finding the max element is constant time, yes, but populating the set is not, since it's sorting at insert. A unordered_set has constant time insert, but would require a search for the maximum element. – crunchdog Aug 27 '09 at 16:22
  • 2
    But since the original question starts with "I have a std::set", we can assume that non-constant insertion time is going to be incurred regardless of our searching mechanism. Since you've already paid the price, why not take advantage of it by using a constant-time search method? – Darryl Aug 27 '09 at 18:11
  • @crunchdog: `unordered_set` only has constant time average-case, but has linear time worst-case, which is worse than `set` – user102008 Mar 22 '13 at 18:23
  • 4
    FYI `*myset.begin()` gives you the minimum element – Yibo Yang Dec 02 '16 at 19:09
34

Sets are always ordered. Assuming you are using the default comparison (less), just grab the last element in the set. rbegin() might be useful.

Darryl
  • 5,542
  • 1
  • 23
  • 31
6

I believe you are looking for std::max_element:

The max_element() function returns an iterator to the largest element in the range [start,end).

Andrew Hare
  • 333,516
  • 69
  • 632
  • 626
  • 20
    This seems like the slow way to do it, since max_element can't know that the range is sorted. – Mark Ransom Aug 27 '09 at 16:10
  • 5
    This is what I get for answering a question outside my comfort zone :) I didn't know that an `std::set` was sorted by default. Since I assumed that it was not sorted an O(n) algorithm seemed to be the only practical choice. Now knowing what I know, yes this answer is not optimal. – Andrew Hare Aug 27 '09 at 17:08
5

Since set sorts the element in ascending order by default, just pick up the last element in the set.

Naveen
  • 71,879
  • 44
  • 171
  • 229
1
if(!myset.empty())
    *myset.rend();
else
    //the set is empty

In an ordered integer set, the last element is the largest one.

Baris Ulgen
  • 11
  • 3
-4

Before you push() in your set<int> save the value in int max in global variable

Paolo Forgia
  • 6,202
  • 8
  • 42
  • 57
arafat almubarok
  • 1
  • please explain what your answer is supposed to do, and maybe provide a code example? I'm curious to see what you come up with! – andrewgu Aug 09 '17 at 06:21