unordered_map: która z nich jest szybsza find() lub count()?

Question

Jaki jest najszybszy sposób sprawdzenia, czy kontener unordered_map zawiera element z określonym kluczem?

Answer 1

Będą mieli o jednakowej wydajności. Powinieneś użyć algorytmu, który najlepiej wyraża to, co próbujesz zrobić.

Aby to rozwinąć, ogólnie count() zostanie zaimplementowane przy użyciu find(). Na przykład, w libcxx, count() jest zaimplementowany jako return (find(__k) != end());

Answer 2

Myślę, że Find jest najlepszą opcją, nie trzeba iść dalej.

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

Answer 3

find() i count() są stosowane do wielu pojemników w C++.

Dla map, zestawów itp. Find zawsze będzie miał stały czas wykonania, ponieważ po prostu oblicza wartość skrótu i ​​zwraca iterator do pierwszego znalezionego elementu (end(), jeśli nie zostanie znaleziony).

count() ma z kolei stały czas realizacji O (e), gdzie e to liczba przypadków, w których znaleziony klucz został znaleziony. W najgorszym przypadku jest to zbiór, gdzie wszyscy członkowie są takie same, więc count może mieć złożoność O (n)

map lub unordered_map nie pozwalają na duplikatów, dlatego ich czas asymptotycznej prowadzony będzie taki sam.

Wybór zależy od semantyki w kodzie. Jeśli chcesz tylko sprawdzić, czy klucz istnieje, możesz po prostu użyć count. Jeśli chcesz sprawdzić, czy klucz istnieje, i użyć jego wartości, przejdź do find, ponieważ już masz iterator wskazujący na ten element.