mapa vs unordered_map dla kilku elementów

Question

Staram się wybierać między map i unordered_map na następującym przypadku zastosowanie:

Klucz do map jest wskaźnik. Najczęstszym przypadkiem użycia jest to, że na mapie znajduje się pojedynczy element. Ogólnie, maksymalna liczba elementów na mapie jest mniejsza niż 10. Dostęp do mapy jest bardzo często, a szybkość jest najważniejszym czynnikiem. Zmiany na mapie są rzadkie.

Podczas gdy mierzenie prędkości jest oczywiście właściwym podejściem, ten kod będzie używany na kilku platformach, więc próbuję utworzyć ogólną zasadę wyboru między map i unordered_map na podstawie liczby elementów. Widziałem tutaj kilka wpisów wskazujących, że mapa std :: map może być szybsza dla małych elementów liczbowych, ale nie podano definicji "małych".

Czy istnieje pewna reguła dotycząca wyboru między map a unordered_map na podstawie liczby elementów? Czy kolejna struktura danych (np. Wyszukiwanie liniowe poprzez vector) jest jeszcze lepsza?

Answer 1

w założeniu, że zawsze trzeba zmierzyć, aby dowiedzieć się, co jest bardziej odpowiednie pod względem wydajności, jeśli wszystkie te rzeczy są prawdziwe:

1. Zmiany w mapie nie są częste;
2. Mapa zawiera maksymalnie 10 elementów;
3. Wyszukiwanie będzie częste;
4. Dbacie dużo o wydajność;

Powiedziałbym, że lepiej byłoby umieścić swoje elementy w std::vector i wykonać zwykłą iterację wszystkich elementów, aby znaleźć tę, której szukasz.

Przydzieli swoje elementy w ciągłym regionie pamięci, więc lokalizacja pamięci podręcznej może zapewnić większą wydajność - czas wymagany do pobrania linii pamięci podręcznej z pamięci głównej po pominięciu pamięci podręcznej to co najmniej jedna kolejność większa niż czas wymagany do uzyskania dostępu do pamięci podręcznej procesora.

Co ciekawe, wydaje się Boost's flat_map jest idealnym rozwiązaniem dla przypadku użycia (dzięki uprzejmości Praetorian):

flat_map jest podobna do std::map ale jest realizowane jak uporządkowanego wektora. (z dokumentacji online)

Więc jeśli za pomocą Boost jest to opcja dla Ciebie, możesz spróbować tego.

Answer 2

Wierzę, że dla twojego przypadku 10 elementów lub mniej i zazwyczaj tylko jedno wyszukiwanie liniowe nieposortowanego wektora będzie działać najlepiej. Jednak w zależności od zastosowanego algorytmu skrótu, zamiast niego może być szybsza.

To powinno być łatwe do porównania.