Jak wybrać między mapą a mapą nieuporządkowaną?

Question

Załóżmy, że chciałbym zmapować dane za pomocą ciągu znaków jako klucza. Jaki kontener powinienem wybrać, map lub unordered_map? unordered_map zajmuje więcej pamięci, więc załóżmy, że pamięć nie jest problemem, a problemem jest szybkość.

unordered_map powinien ogólnie dawać średnią złożoność O (1) w najgorszym przypadku O (n). W jakich przypadkach może dojść do O (n)? Kiedy map uzyskuje większą oszczędność czasu niż unordered_map? Czy zdarza się, gdy n jest małe?

Zakładając, że użyłbym STL unordered_map z domyślnym VS hasera. mapa. ciąg jest kluczem.

Jeśli mam zamiar powtórzyć elementy zamiast dostępu do pojedynczego elementu za każdym razem, czy powinienem preferować map?

Answer 1

W praktyce, jeśli pamięć nie jest wydanie, unordered_map jest zawsze szybsze, jeśli chcesz uzyskać dostęp do jednego elementu.

Najgorszy przypadek jest teoretyczny i związany z pojedynczym hashem dla wszystkich elementów. Nie ma to praktycznego znaczenia. Numer unordered_map jest wolniejszy, gdy tylko zalogujesz się co najmniej N elementów należących do tego samego skrótu. Nie ma to również znaczenia praktycznego. W niektórych scenariuszach specjalnych można użyć specjalnego algorytmu mieszającego, który zapewnia bardziej równomierną dystrybucję. W przypadku zwykłych ciągów, które nie współdzielą określonego wzorca, ogólne funkcje mieszające pochodzące z unordered_map są równie dobre.

Jeśli chcesz posortować mapę (używając iteratorów) w sposób posortowany, nie możesz użyć unordered_map.Wręcz przeciwnie, map pozwala nie tylko, ale również może dostarczyć następnego elementu mapy opartej na zbliżenia klucza (patrz lower_bound i upper_bound metod).

Answer 2

W jakich przypadkach miałoby dojść do O (n)?

jeśli masz taką złe funkcji skrótu, która produkuje taką samą wartość skrótu dla wszystkich stirngs wejściowych (czyli produkują kolizje) ...

Co pojemnik powinien wybrałem, map lub unordered_map ?

Zawsze masz pytania o wymagania i rodzaj/ilość danych, które posiadasz.

Kiedy mapa zyskuje więcej czasu niż nieuporządkowana_mapa?

To tylko różne struktury. Lepiej zrobić chiose wykorzystać jeden z nich w zależności od typowych przypadków użycia (takeing w koncie, jakie dane masz i jej wysokości)

Czy to hppaen gdy n jest małe?

W przypadku małej ilości danych wszystko zależy od konkretnej implementacji STL ... Więc czasami nawet zwykły wektor/tablica może być szybsza niż kontenerów asocjacyjnych ...

Answer 3

Jaki kontener powinienem wybrać, mapować lub mapować_zabezpieczony? unordered_map zajmuje więcej pamięci, więc załóżmy, że pamięć nie jest problemem, a problemem jest szybkość.

profilu, a następnie zdecydować. unordered_map jest zwykle szybszy, ale różni się w zależności od przypadku.

W jakich przypadkach miałoby dojść do O (n)?

Gdy mieszania nie jest dobra, a kilka elementów są przypisane do tych samych pojemników.

Kiedy mapa zyskuje więcej czasu niż nieuporządkowana_mapa? Czy to się wydarzy, gdy n jest małe?

Prawdopodobnie nie, ale zrób to, jeśli naprawdę cię to obchodzi. Posiadanie kontenera o małym rozmiarze jest wąskim gardłem Twojego programu, co wydaje się bardzo mało prawdopodobne. W każdym razie, prosty vector z liniowym wyszukiwaniem może być szybszy w takich przypadkach.

---

Najważniejszą rzeczą przy podejmowaniu decyzji, to wymagania zamawiającego i brak iteratora unieważnieniu. Jeśli potrzebujesz, musisz użyć map. W przeciwnym razie, unordered_map.

Answer 4

     | map    | unordered_map 
--------------------------------------------------------- 
element ordering  | strict weak  | n/a 
         |     | 
common implementation | balanced tree | hash table 
         | or red-black tree| 
         |     | 
search time   | log(n)   | O(1) if there are no hash collisions 
         |     | Up to O(n) if there are hash collisions 
         |     | O(n) when hash is the same for any key 
         |     |  
Insertion time   | log(n)+rebalance | Same as search 
         |     | 
Deletion time   | log(n)+rebalance | Same as search 
         |     | 
needs comparators  | only operator < | only operator == 
         |     | 
needs hash function | no    | yes 
         |     | 
common use case  | when good hash is| In most other cases. 
         | not possible or | 
         | too slow. Or when| 
         | order is required|