jaka jest różnica między set i unordered set W C++?

Natknąłem się na to dobre pytanie, które jest podobne, ale wcale nie to samo, ponieważ mówi o Javie, która ma inną implementację tabel hashowych, ponieważ posiada zsynchronizowany accesor / mutator różnice między HashMap i Hashtable?

Więc jaka jest różnica w implementacji C++ set i unordered_set ? To pytanie można oczywiście rozszerzyć na map vs unordered_map i tak dalej dla innych kontenerów C++.

Oto mój inicjał ocena

Set : podczas gdy standard nie prosi wprost o zaimplementowanie go jako drzewa, ograniczenie złożoności czasowej zapytane o jego operacje dla find/insert oznacza, że zawsze będzie zaimplementowany jako drzewo. Zwykle jako drzewo RB (jak widać w GCC 4.8), które jest zrównoważone wysokością. Ponieważ są zrównoważone wysokością, mają przewidywalną złożoność czasową dla funkcji find ()

Plusy: Kompaktowy (w porównaniu do innych DS w porównaniu)

Con: złożoność czasu dostępu to O (lg n)

Unordered_set : podczas gdy standard nie prosi wprost o zaimplementowanie go jako drzewa, ograniczenie złożoności czasowej zapytane o jego operacje dla find/insert oznacza, że zawsze będzie zaimplementowany jako hash-table.

Plusy:

  1. Faster (promises amortized O (1) for search)
    2. W przeciwieństwie do innych formatów, nie można ich używać do tworzenia wątków.]}

Wady:

  1. Look up not guaranteed to be O (1) therotical worst case is O (n)
    2. Nie tak zwarty jak drzewo. (dla celów praktycznych współczynniki obciążenia nigdy nie są 1)

Uwaga : O (1), dla hashtable wynika z założenia, że nie ma kolizji. Nawet przy obciążeniu .5, co druga zmienna wstawiania prowadzi do kolizji. Można zaobserwować, że współczynnik obciążenia tablicy hash jest odwrotnie proporcjonalny do liczby operacji wymaganych do uzyskania dostępu do elementu w niej. Więcej redukujemy # operations, sparser hash-table. Kiedy składowane elementy mają rozmiar porównywalny do wskaźnika, wtedy narzut jest dość znaczący.

Edit: ponieważ większość mówi, że pytanie zawiera w sobie wystarczającą odpowiedź, zmieniam pytanie na "Czy przegapiłem jakąś różnicę między mapą/zestawem do analizy wydajności, którą należy znać ??"

Author: Community, 2013-04-18
Source

4 answers

Myślę, że generalnie odpowiedziałeś na swoje pytanie, jednak to:

Nie tak zwarty jak drzewo. (dla celów praktycznych współczynniki obciążenia nigdy nie są 1)
To niekoniecznie prawda. Każdy węzeł drzewa (Zakładamy, że jest to czerwono-czarne drzewo) dla typu T wykorzystuje przestrzeń równą co najmniej 2 * pointer_size + sizeof(T) + sizeof(bool). Może to być 3 * pointer size w zależności od tego, czy drzewo zawiera wskaźnik parent dla każdego węzła drzewa.

Porównaj to z hash-mapą: zostanie zmarnowana tablica miejsce dla każdej mapy hashowej ze względu na fakt, że load factor < 1 Jak już powiedziałeś. Jednak zakładając, że mapa hash używa pojedynczo połączonych list do łączenia łańcuchów (i naprawdę nie ma prawdziwego powodu, aby tego nie robić), każdy wstawiony element bierze tylko sizeof(T) + pointer size.

Należy zauważyć, że analiza ta ignoruje wszelkie napowietrzne, które mogą pochodzić z dodatkowej przestrzeni używanej przez wyrównanie.

Dla dowolnego elementu T, który ma mały rozmiar (a więc dowolny typ podstawowy), dominuje rozmiar wskaźników i innych nadmiarowych. Przy współczynniku obciążenia > 0.5 (dla przykład) std::unordered_set może rzeczywiście zużywać mniej pamięci niż odpowiednik std::set.

Innym dużym brakującym punktem jest fakt, że iteracja przez std::set gwarantuje uzyskanie kolejności od najmniejszego do największego, na podstawie podanej funkcji porównawczej, podczas gdy iteracja przez std::unordered_set zwróci wartości w "losowej" kolejności.

 28
Author: Yuushi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-04-18 07:28:44

Kolejną różnicą (choć nie związaną z wydajnością) jest to, że wstawianie set nie unieważnia iteratorów, podczas gdy wstawianie unordered_set może, jeśli spowoduje ponowne pobranie. W praktyce jest to dość niewielki problem, ponieważ odniesienia do rzeczywistych elementów pozostają ważne.

 11
Author: dhaffey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-04-19 18:35:05

Yuushi już dobrze odnosi się do efektywności przestrzennej i innych punktów; tylko kilka innych części pytania, które skomentuję...

O(1), dla hashtable wynika z założenia, że nie ma kolizji.

To nieprawda. To, co O(1) oznacza nie to, że pierwsza próba wyszukiwania zawsze się powiedzie, to to, że jest - średnio-stała liczba prób potrzebnych, a nie coś, co rośnie wraz ze wzrostem liczby wartości. Na przykład z unordered_set lub ..._map, the max_load_factor domyślnie 1.0 na budowie, a jeśli współczynnik obciążenia zbliży się do tego z dobrą funkcją skrótu, średnia liczba elementów, które hashują do jednego łyżki, będzie wynosić około 2, niezależnie od tego, ile wartości znajduje się w tabeli.
Nawet przy obciążeniu .5, co druga zmienna wstawiania prowadzi do kolizji.

Prawda, ale to nie jest tak tragiczne, jak można intuicyjnie oczekiwać: że średnia długość łańcucha 2 Na 1.0 współczynnik obciążenia nie jest zły.

Można zaobserwować, że współczynnik obciążenia tabeli hash jest odwrotnie proporcjonalna do liczby operacji wymaganych do uzyskania dostępu do element w nim. Więcej redukujemy # operations, sparser hash-table.

Na pewno istnieje korelacja (nie jest odwrotna).

 2
Author: Tony Delroy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-02-13 08:16:14

W niektórych przypadkach set jest wygodniejszy.

Na przykład użycie vector jako klucza: 

set<vector<int>> s;
s.insert({1, 2});
s.insert({1, 3});
s.insert({1, 2});

for(const auto& vec:s)
    cout<<vec<<endl;   // I have override << for vector
// 1 2
// 1 3

Powód, dla którego vector<int> może być w set ponieważ vector override operator<.

Ale jeśli używasz unordered_set<vector<int>> musisz utworzyć funkcję hashową dla vector<int>, ponieważ vector nie ma funkcji hashowej, więc musisz zdefiniować taką jak: 

struct VectorHash {
    size_t operator()(const std::vector<int>& v) const {
        std::hash<int> hasher;
        size_t seed = 0;
        for (int i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
        return seed;
    }
};

vector<vector<int>> two(){
    //unordered_set<vector<int>> s; // error vector<int> doesn't  have hash function
    unordered_set<vector<int>, VectorHash> s;
    s.insert({1, 2});
    s.insert({1, 3});
    s.insert({1, 2});

    for(const auto& vec:s)
        cout<<vec<<endl;
    // 1 2
    // 1 3
}

Widać, że w niektórych przypadkach unordered_set jest bardziej skomplikowane.

Głównie cytowane od: https://stackoverflow.com/a/29855973/6329006

Większa różnica między unordered_set a set Zobacz to: https://stackoverflow.com/a/52203931/6329006

 1
Author: Jayhello,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-09-06 12:25:59