45
Ich habe eine std::set<int>, was ist der richtige Weg, um die größte int in diesem Satz zu finden?Wie finde ich den größten int in einem std :: set <int>?
A
Antwort
75
Welchen Komparator verwenden Sie?
Für den Standard dies funktionieren wird:
if(!myset.empty())
*myset.rbegin();
else
//the set is empty
Dies wird auch konstante Zeit statt linear wie die max_element Lösung sein.
6
Ich glaube, Sie suchen std::max_element:
Die
max_element()Funktion gibt einen Iterator auf das größte Element in der Bereich [Start, Ende).
+14
Dies scheint die langsame Art und Weise, es zu tun, da max_element kann nicht wissen, dass der Bereich sortiert wird. –
+2
Das ist, was ich bekomme, um eine Frage außerhalb meiner Komfortzone zu beantworten :) Ich wusste nicht, dass ein 'std :: set 'standardmäßig sortiert war. Da ich annahm, dass es nicht sortiert war, schien ein O (n) Algorithmus die einzige praktische Wahl zu sein. Jetzt weiß ich, was ich weiß, ja, diese Antwort ist nicht optimal. –
29
Sätze werden immer bestellt. Angenommen, Sie verwenden den Standardvergleich (weniger), greifen Sie einfach das letzte Element in der Menge. rbegin() könnte nützlich sein.
+0
C++ Standardbestellgarantie : http://stackoverflow.com/q/8833938/895245 –
6
Da set das Element standardmäßig in aufsteigender Reihenfolge sortiert, nehmen Sie einfach das letzte Element in der Menge auf.
-1
Bevor Sie push() in Ihrem set<int> in int max in globalen Variablen den Wert speichern
+0
Bitte erläutern Sie, was Ihre Antwort tun soll, und vielleicht ein Codebeispiel bereitstellen? Ich bin gespannt auf was du kommst! – andrewgu
Das maximale Element zu finden ist eine konstante Zeit, ja, aber die Menge wird nicht gefüllt, da es bei der Einfügung sortiert wird. Ein ungeordnetes_set hat eine konstante Zeiteinfügung, würde jedoch eine Suche nach dem maximalen Element erfordern. – crunchdog
Aber da die ursprüngliche Frage mit "Ich habe ein std :: set" beginnt, können wir annehmen, dass unabhängig von unserem Suchmechanismus eine nicht konstante Einfügungszeit auftritt. Da Sie den Preis bereits bezahlt haben, warum nutzen Sie ihn nicht aus, indem Sie eine Suchmethode mit konstanter Zeit verwenden? – Darryl
@crunchdog: 'unordered_set' hat nur konstanten Zeitdurchschnitts-Fall, hat aber lineare Zeit worst-case, was schlimmer ist als' set' – user102008