45
У меня есть std::set<int>, каков правильный способ найти самый большой int в этом наборе?Как найти наибольший int в std :: set <int>?
A
ответ
75
Какой компаратор вы используете?
Для умолчанию это будет работать:
if(!myset.empty())
*myset.rbegin();
else
//the set is empty
Это также будет постоянная время вместо линейной как решение max_element.
6
Я считаю, что вы ищете std::max_element:
max_element()функция возвращает итератор для наибольшего элемента в диапазоне [начало, конец).
+14
Это похоже на медленный способ сделать это, так как max_element не может знать, что диапазон отсортирован. –
+2
Это то, что я получаю для ответа на вопрос вне зоны комфорта :) Я не знал, что по умолчанию был отсортирован 'std :: set'. Поскольку я предполагал, что он не был отсортирован, алгоритм O (n), казалось, был единственным практическим выбором. Теперь, зная, что я знаю, да, этот ответ не оптимален. –
29
Наборы всегда заказываются. Предполагая, что вы используете сравнение по умолчанию (меньше), просто возьмите последний элемент в наборе. rbegin() может быть полезным.
+0
C++ стандартная гарантия заказа : http://stackoverflow.com/q/8833938/895245 –
6
Поскольку набор по умолчанию сортирует элемент по возрастанию, просто выберите последний элемент в наборе.
-1
Перед push() в вашем set<int> сохранить значение в int max в глобальной переменной
+0
, пожалуйста, объясните, что должен делать ваш ответ, и, может быть, представить пример кода? Мне любопытно посмотреть, что вы придумали! – andrewgu
Поиск максимального элемента - это постоянное время, да, но заполнение набора не происходит, поскольку оно сортируется при вставке. Unordered_set имеет постоянную вставку времени, но для этого требуется поиск максимального элемента. – crunchdog
Но поскольку исходный вопрос начинается с «У меня есть std :: set», мы можем предположить, что время непостоянного ввода будет происходить независимо от нашего поискового механизма. Поскольку вы уже заплатили цену, почему бы не воспользоваться ею, используя метод поиска по постоянному времени? – Darryl
@crunchdog: 'unordered_set' имеет только среднее значение среднего времени, но имеет линейное худшее время, что хуже, чем' set' – user102008