Tak jak mówisz, I assume the buckets can get big..., lepiej używać std::list. Wyszukiwanie jest liniowe w obu przypadkach, ale dodawanie elementów jest stałe w std::list.
I guess they're all the same, since data isn't ordered - Nie, nie są. Gdyby tak było, byłby tylko jeden pojemnik. Każdy pojemnik ma swoje zalety i wady, różne pojemniki są używane w różnych sytuacjach.
Trochę informacji o wektorze:
std::vector ma zdolności, to dlaczego ma capacity() i size() metod. Obie są różne. Załóżmy, że pojemność wynosi 4, a ty masz 2 elementy, wtedy rozmiar będzie wynosił 2. Zatem dodanie kolejnego elementu zwiększy rozmiar (wyniesie 3) i wszystko będzie bardzo szybkie.
Co się stanie, gdy trzeba będzie dodać 5 elementów, a pojemność 4? Całkowicie nowy pamięć jest alokowana, wszystkie stare elementy są kopiowane w nowej pamięci, wszystkie stare elementy są zniszczone (ich destruktory są nazywane, jeśli typów zdefiniowanych przez użytkownika). Następnie stara pamięć musi być uwolniona. Są to kosztowne operacje, jeśli uważasz, że dodawanie/usuwanie elementów będzie częściej.
Można tego uniknąć, stosując metodę std::vector::reserve, aby zarezerwować wcześniej pamięć i nie należy ponownie przydzielać nowej pamięci, a także kopiować wszystko w kółko. Jest to jednak przydatne, gdy znasz przybliżony rozmiar tych wektorów. Przypuszczam, że nie masz w tej sytuacji (zarezerwowanie dużej ilości pamięci też nie jest dobrym rozwiązaniem - nie powinieneś marnować pamięci tak jak ta). Tak więc, wolałbym std :: list.
Lub podwójne hash.
W każdym razie, przydział nowej pamięci i kopiowanie obiektów nie zdarza się tak często, ponieważ std::vector jest "sprytny", a przy przydzielaniu nowej przestrzeni nie zwiększa pojemności za pomocą tylko jednego elementu lub czegoś podobnego. Myślę, że to podwaja, ale nie jestem tego pewien. Argh, nie wiem, jak to się nazywa w języku angielskim. Prawdopodobnie coś takiego jak "akumulacyjny czas/pamięć" lub "akumulacyjna złożoność":?Nie wiem:/
UWAGA: Cokolwiek wybierzesz, proponuję zwrócić uwagę na funkcję skrótu. Najważniejsze tutaj. Kontener hash NIE powinien mieć zbyt wielu elementów z tym samym hash. Tak więc, moja rada jest poszukiwanie dobrej funkcji hash, a to nie będzie miało większego znaczenia.
Mam nadzieję, że pomogło (:
EDIT: Chciałbym polecić ten artykuł - comparing std::vector and std::deque - to idealny - porównuje zużycie pamięci (przydzielanie, dealokując, rośnie), użycie procesora, itd ja polecam cały site dla takich artykułów - nie ma ich wiele, ale są naprawdę dobrze napisane:
Wektor jest OK, niekoniecznie optymalny.Zdejmowanie od środka nie jest efektywne, więc jeśli twoje wiadra mogą być duże, może porównać go z 'list' i/lub' deque' .Jeśli twoje kubły nie mogą się powiększyć, 'wektor' może przecenić.Każdy trzy mają liniowe wyszukiwanie. Struktura nas, która może pokonać liniowy czas wyszukiwania, jest kolejnym hashtable (lub tym samym stołem ponownie), jak w podwójnym haszowaniu. Bez zlecenia nie ma nic w standardowych bibliotekach: wszystko, co robią, to rzeczy z rozkazami i czystymi sekwencjami. –
'Deque' może być lepszy niż' vector', ponieważ nigdy nie musi przenosić i przenosić wszystkiego. Dostęp jest nieco wolniejszy, funkcja push_back jest potencjalnie dużo szybsza, w zależności od tego, ile kosztują elementy do skopiowania. 'list' zwykle ma więcej alokacji pamięci niż którykolwiek z nich i może być wolniejsze z tego powodu. –