Kontenery (unordered_*) wkładają wszystkie elementy z takim samym hashem do tego samego kubełka. Wydajność działania zależy od funkcji hash-ującej, która powinna zawsze zwracać ten sam rezultat, dla tych samych argumentów. Idealnie, każda wartość, powinna trafić do innego kubełka. W przypadku wyszukiwania, najpierw odszukiwany jest kubełek, a później sekwencyjnie porównywane są jego elementy.
Biblioteka dostarcza, kilka metod, które pokazują w jaki sposób zarządzane są nasze obiekty i w ten sposób, pozwalają dowiedzieć się gdzie wydajność może zostać poprawiona.
#include <iostream>
#include <unordered_map>
using namespace std;
int main()
{
const std::string key = "kilo";
std::unordered_map<std::string, int> m = {
{"delta", 7},
{key, 99},
{"hotel", 21},
{"foxtrot", 2},
};
cout << "Ilosc kubelkow: " << m.bucket_count() << endl;
cout << "Max do skorzytania: " << m.max_bucket_count() << endl;
const int bucket = m.bucket(key);
cout << "Element '" << key << "' jest w kubelku: " << bucket << endl;
cout << "Elementow w kupelku(" << bucket << "): " << m.bucket_size(bucket) << endl;
cout << "Srednia liczba elem. na kubelek: " << m.load_factor() << endl;
cout << "Sredni rozmiar kubelka jaki kontener bedzie chcial zachowac: " <<
m.max_load_factor() << endl;
for(const auto &val: m)
cout << "map[" << val.first << "] = " << val.second << endl;
return 0;
}
Dodatkowo mamy do dyspozycji metody rehash(n), która reorganizuje mapę tak, by liczba_kubełków >= n i liczba_kubełków > size/max_load_factor. Oraz metodę reserve(m), która sprawia, że mapa może przechowywać m elementów bez rehash-owania.Wyniki:
Ilosc kubelkow: 11 Max do skorzytania: 268435455 Element 'kilo' jest w kubelku: 6 Elementow w kupelku(6): 1 Srednia liczba elem. na kubelek: 0.363636 Sredni rozmiar kubelka jaki kontener bedzie chcial zachowac: 1 map[foxtrot] = 2 map[hotel] = 21 map[kilo] = 99 map[delta] = 7Domyślnie tego typu kontenery korzystają z operator ==, by porównać elementy, oraz z obiektu typu hash<key_type> by wygenerować hash. Można jednak wskazać własne metody, które się tym zajmą.
#include <iostream>
#include <unordered_map>
using namespace std;
struct Color {
Color(int v) : value(v) {}
string getValue() const {
return "#" + std::to_string(value);
}
private:
int value;
};
size_t hashColor(const Color& c) {
cout << "hashColor " << c.getValue() << endl;
return c.getValue().length();
}
bool equalOp(const Color &l, const Color &r) {
cout << "equalOp " << l.getValue() << " " << r.getValue() << endl;
return l.getValue() == r.getValue();
}
int main()
{
std::unordered_map<Color,
string,
decltype(hashColor)*,
decltype(equalOp)*> m(42, hashColor, equalOp);
m[Color(1)] = "red";
m[Color(2)] = "blue";
m[Color(3)] = "green";
return 0;
}
Wyniki:hashColor #1 hashColor #2 equalOp #2 #1 hashColor #3 equalOp #3 #2 equalOp #3 #1Na koniec link, do artykułu wgryzającego się w szczegóły implementacyjne unordered_map:
