如何在std :: set <int>中找到最大的int？

Question

我有一个std::set<int>,找到这个集合中最大的int的正确方法是什么？

Answer 1

你使用什么比较器？

对于默认值,这将起作用:

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

与max_element解决方案一样,这也是恒定时间而不是线性时间.

但由于最初的问题以“我有一个 std::set”开头，因此我们可以假设无论我们的搜索机制如何，都会产生非常量的插入时间。既然你已经付出了代价，为什么不通过使用恒定时间搜索方法来利用它呢？ (5认同)
FYI`*myset.begin()`为您提供最小元素 (4认同)
是的，找到max元素是固定时间，是的，但不是要填充集合，因为它是在插入时排序的。unordered_set具有固定的时间插入，但是需要搜索最大元素。 (2认同)

Answer 2

总是订购套装.假设您正在使用默认比较(less),只需抓取集合中的最后一个元素.rbegin()可能很有用.

Answer 3

我相信你在寻找std::max_element:

该max_element()函数将迭代器返回到[start,end]范围内的最大元素.

这似乎是缓慢的方法,因为max_element不能知道范围是如何排序的. (18认同)
这就是我在舒适区之外回答问题所得到的:)我不知道`std :: set`是默认排序的.由于我认为它没有排序,O(n)算法似乎是唯一的实用选择.现在知道我所知道的,是的,这个答案不是最佳的. (4认同)

Answer 4

由于set默认按升序对元素进行排序,因此只需拾取集合中的最后一个元素即可.