45
Ho un std::set<int>, qual è il modo corretto per trovare il più grande int in questo set?Come trovo l'int più grande in un std :: set <int>?
A
risposta
75
Che comparatore stai utilizzando?
Per default questo funzionerà:
if(!myset.empty())
*myset.rbegin();
else
//the set is empty
Questo sarà anche costante di tempo anziché lineare come la soluzione max_element.
6
Credo che si sta cercando std::max_element:
La funzione
max_element()restituisce un iteratore all'elemento più grande della gamma [inizio, fine).
+14
Questo mi sembra il modo lento a farlo, dal momento che max_element non può sapere che la gamma è ordinato. –
+2
Questo è quello che ottengo per rispondere a una domanda al di fuori della mia zona di comfort :) Non sapevo che un 'std :: set' è stato ordinato per impostazione predefinita. Dal momento che ritenevo che non fosse ordinato, un algoritmo O (n) sembrava essere l'unica scelta pratica. Ora sapendo quello che so, sì, questa risposta non è ottimale. –
29
I set sono sempre ordinati. Supponendo che stai usando il confronto di default (meno), prendi semplicemente l'ultimo elemento nel set. rbegin() potrebbe essere utile.
+0
C++ garanzia di ordine standard : http://stackoverflow.com/q/8833938/895245 –
6
Poiché il set ordina l'elemento in ordine crescente per impostazione predefinita, basta raccogliere l'ultimo elemento nel set.
-1
Prima di push() nel vostro set<int> salvare il valore in int max nella variabile globale
+0
per favore spieghi che cosa dovrebbe fare la tua risposta, e magari fornisci un esempio di codice? Sono curioso di vedere cosa ti viene in mente! – andrewgu
Trovare l'elemento massimo è un tempo costante, sì, ma il popolamento del set non lo è, dal momento che è in fase di classificazione. Un unordered_set ha un inserimento di tempo costante, ma richiederebbe la ricerca dell'elemento massimo. – crunchdog
Ma dal momento che la domanda originale inizia con "I have a std :: set", possiamo presumere che il tempo di inserimento non costante verrà sostenuto indipendentemente dal nostro meccanismo di ricerca. Dal momento che hai già pagato il prezzo, perché non approfittarne utilizzando un metodo di ricerca a tempo costante? – Darryl
@crunchdog: 'unordered_set' ha solo un tempo medio costante, ma ha un tempo lineare peggiore, che è peggio di' set' – user102008