C++11 unordered containers

Nowy zestaw kontenerów asocjacyjnych (unordered_set, unordered_multiset, unordered_map i unordered_multimap), do porównywania używają funkcji hash-ujących i operatora == dla klucza. Są najbardziej użyteczne, kiedy korzystamy z klucza, dla którego nie ma oczywistej relacji porządku. A także w aplikacjach, gdzie koszt przechowywania elementów w porządku nie jest istotny. Zazwyczaj jednak łatwiej i wydajniej jest korzystać ze zwykłych kontenerów asocjacyjnych.

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] = 7

Domyś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 #1

Na koniec link, do artykułu wgryzającego się w szczegóły implementacyjne unordered_map:

• http://codecapsule.com/2013/05/13/implementing-a-key-value-store-part-5-hash-table-implementations/