Wybór pomiędzy std:: map a std:: unordered map

Oprócz powyższych odpowiedzi należy również zauważyć, że to, że unordered_map jest stałą prędkością (O(1)) nie oznacza, że jest szybsza niż map (rzędu log(N)). Stała może być większa niż log(N), zwłaszcza że N jest ograniczona przez 2³² (lub 2⁶⁴).

Więc oprócz innych odpowiedzi (map utrzymuje porządek i funkcje hashowe mogą być trudne) może być tak, że map jest bardziej wydajna.

Na przykład w programie, który uruchomiłem dla bloga post widziałem, że dla VS10 std::unordered_map był wolniejszy od std::map (chociaż boost::unordered_map był szybszy od obu).

Uwaga od trzeciego do piątego taktu.

_{jest to spowodowane Chandler Carruth Google w jego CppCon 2014 wykład}

std::map jest (przez wielu uważane za) bezużyteczne dla pracy zorientowanej na wydajność: jeśli chcesz o (1)-zamortyzowanego dostępu, użyj odpowiedniej tablicy asocjacyjnej (lub z braku jednej, std::unorderded_map); jeśli chcesz posortowanego dostępu sekwencyjnego, użyj czegoś opartego na wektorze.

Również, std::map jest zrównoważonym drzewem; i trzeba go przemierzać, lub ponownie balansować, niewiarygodnie często. Są to Cache-killer i operacje cache-apocalypse... więc powiedz Nie std::map.

Może Cię zainteresować to pytanie na temat wydajnych implementacji map hashowych.

(PS - std::unordered_map jest Cache-nieprzyjazny, ponieważ używa połączonych list jako wiadra.)

Myślę, że to oczywiste, że używasz std::map musisz iterację między elementami na mapie w porządku posortowanym.

Możesz go również użyć, gdy wolisz napisać operator porównania (który jest intuicyjny) zamiast funkcji skrótu (która jest ogólnie bardzo nieintuicyjna).

Powiedzmy, że masz bardzo duże klawisze, być może duże struny. Aby utworzyć wartość skrótu dla dużego ciągu, musisz przejść przez cały łańcuch od początku do końca. To zajmie co najmniej liniowy czas do długości klucza. Jednakże, gdy przeszukujesz tylko drzewo binarne używając operatora > klucza, każde porównanie łańcuchów może zwrócić, gdy zostanie znaleziona pierwsza niezgodność. Jest to zazwyczaj bardzo wcześnie dla dużych strun.

To rozumowanie można zastosować do find funkcji std::unordered_map i std::map. Jeśli charakter klucza jest taki, że wytworzenie skrótu zajmuje więcej czasu (w przypadku std::unordered_map) niż znalezienie lokalizacji elementu za pomocą wyszukiwania binarnego( w przypadku std::map), powinno być szybsze wyszukanie klucza w std::map. Dość łatwo jest myśleć o scenariuszach, w których miałoby to miejsce, ale w praktyce byłyby one dość rzadkie.