unordered_map: quale è più veloce find() o count()?

Question

Qual è il modo più veloce per capire se un container-ha un elemento con una chiave specificata?

Answer 1

Avranno circa pari prestazioni. Dovresti usare l'algoritmo che meglio esprime ciò che stai cercando di fare.

Per elaborare quello, in genereverrà implementato utilizzando find(). Ad esempio, in libcxx, count() viene implementato come return (find(__k) != end());

Answer 2

Penso che il Trova sia l'opzione migliore qui, non c'è bisogno di andare oltre.

http://www.cplusplus.com/reference/unordered_map/unordered_map/find/

Answer 3

find() e count() sono applicabili a molti contenitori in C++.

Per mappe, set, ecc., Find avrà sempre un tempo di esecuzione costante, poiché calcola semplicemente l'hash e restituisce un iteratore al primo elemento trovato (end() se non trovato).

count() d'altra parte, ha un tempo di esecuzione costante O (e), dove e è il numero di volte che viene trovata la chiave fornita. Il caso peggiore è una raccolta dove tutti i membri sono uguali, così count potrebbe avere un O complessità (n)

map o unordered_map non consentono di duplicati, quindi il loro tempo di esecuzione asintotico sarebbe la stessa.

La scelta dipende dalla semantica del codice. Se vuoi solo verificare se esiste una chiave, puoi semplicemente usare count. Se desideri verificare se esiste una chiave e utilizzarne il valore, vai su find poiché hai già un iteratore che punta a quell'elemento.