I have a std::set, what's the proper way to find the largest int in this set ?
+7
A:
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
2009-08-27 16:03:43
This seems like the slow way to do it, since max_element can't know that the range is sorted.
Mark Ransom
2009-08-27 16:10:59
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
2009-08-27 17:08:54
+16
A:
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
2009-08-27 16:04:47
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
2009-08-27 16:22:09
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
2009-08-27 18:11:07
+15
A:
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
2009-08-27 16:06:16
+4
A:
Since set sorts the element in ascending order by default, just pick up the last element in the set.
Naveen
2009-08-27 16:10:14