I have a std::set<int>
, what's the proper way to find the largest int in this set?
6 Answers
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.
-
2Finding 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. Aug 27, 2009 at 16:22
-
2But 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?– DarrylAug 27, 2009 at 18:11
-
@crunchdog:
unordered_set
only has constant time average-case, but has linear time worst-case, which is worse thanset
Mar 22, 2013 at 18:23 -
5
Sets are always ordered. Assuming you are using the default comparison (less), just grab the last element in the set. rbegin() might be useful.
-
1
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).
-
21This seems like the slow way to do it, since max_element can't know that the range is sorted. Aug 27, 2009 at 16:10
-
5This 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. Aug 27, 2009 at 17:08
Since set sorts the element in ascending order by default, just pick up the last element in the set.
if(!myset.empty())
*myset.rend();
else
//the set is empty
In an ordered integer set, the last element is the largest one.
Before you push()
in your set<int>
save the value in int max
in global variable
-
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!– andrewguAug 9, 2017 at 6:21