Dlaczego ktoś miałby używać set zamiast unordered_set?

Wprowadzamy C ++ 0x, unordered_setktóry jest dostępny w boostwielu innych miejscach. Rozumiem, że unordered_setjest to tabela skrótów ze O(1)złożonością wyszukiwania. Z drugiej strony setto nic innego jak drzewo o log(n)złożoności wyszukiwania. Dlaczego, u licha, ktoś miałby używać setzamiast unordered_set? tj. czy jest już taka potrzeba set?

Kiedy dla kogoś, kto chce iterować elementy zestawu, kolejność ma znaczenie.

Nieuporządkowane zestawy muszą płacić za średni czas dostępu O (1) na kilka sposobów:

• setzużywa mniej pamięci niż unordered_setprzechowywanie tej samej liczby elementów.
• W przypadku niewielkiej liczby elementów wyszukiwania w a setmogą być szybsze niż wyszukiwania w unordered_set.
• Mimo, iż wiele operacji szybciej w średnim przypadku dla unordered_set, często są one gwarantowane mieć lepsze najgorszym przypadku zawiłości dla set(na przykładinsert ).
• To set sortuje elementy jest przydatne, jeśli chcesz uzyskać do nich dostęp w kolejności.
• Można leksykograficznie porównać różne setsz <, <=, >i >=. unordered_setnie są wymagane do obsługi tych operacji.

Zawsze, gdy wolisz drzewo od tabeli skrótów.

Na przykład tabele skrótów mają w najgorszym przypadku wartość „O (n)”. O (1) to przeciętny przypadek. W najgorszym przypadku drzewa są „O ( log n)”.

Użyj zestawu, gdy:

1. Potrzebujemy uporządkowanych danych (odrębnych elementów).
2. Musielibyśmy wydrukować / uzyskać dostęp do danych (w posortowanej kolejności).
3. Potrzebujemy poprzednika / następcy elementów.

Użyj unordered_set, gdy:

1. Musimy zachować zestaw odrębnych elementów i nie jest wymagana żadna kolejność.
2. Potrzebujemy dostępu do pojedynczego elementu, tj. Bez przechodzenia.

Przykłady:

zestaw:

Wejście: 1, 8, 2, 5, 3, 9

Wyjście: 1, 2, 3, 5, 8, 9

Unordered_set:

Wejście: 1, 8, 2, 5, 3, 9

Wyjście: 9 3 1 8 2 5 (może ta kolejność, na którą ma wpływ funkcja skrótu)

Głównie różnica:

Uwaga: (w niektórych przypadkach setjest to wygodniejsze) na przykład użycie vectorjako 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 

Powodem, dla którego vector<int>może być kluczem setbo vectorręcznym operator<.

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

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_setjest to bardziej skomplikowane.

Cytowane głównie z: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

Ponieważ std :: set jest częścią Standard C ++, a unordered_set nie jest. C ++ 0x NIE jest standardem, podobnie jak Boost. Dla wielu z nas przenośność jest niezbędna, a to oznacza trzymanie się standardów.

Rozważmy algorytmy linii przebiegu. Algorytmy te całkowicie zawiodłyby w przypadku tablic mieszających, ale działają pięknie ze zrównoważonymi drzewami. Aby dać ci konkretny przykład algorytmu linii losowania, rozważ algorytm fortuny. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Jeszcze jedno, oprócz tego, o czym wspomniały już inne osoby. A oczekiwane zamortyzowany złożoność do wprowadzania elementu do unordered_set O (1), co jakiś czas, a następnie będzie się O (N), ponieważ wymaga mieszającego stołowych restrukturyzowany (liczby segmentów musi zmienić) - nawet „dobra” funkcja skrótu. Podobnie jak wstawianie elementu do wektora wymaga od czasu do czasu O (n), ponieważ podstawowa tablica musi zostać ponownie przydzielona.

Wstawienie do zestawu zawsze zajmuje najwyżej O (log n). Może to być preferowane w niektórych aplikacjach.

Przepraszam, jeszcze jedna rzecz, na którą warto zwrócić uwagę w przypadku posortowanej nieruchomości:

Jeśli chcesz zakres danych w kontenerze, na przykład: Zapisałeś czas w zestawie , a chcesz czas od 01.01.2013 do 01.01.2014.

Dla unordered_set jest to niemożliwe.

Oczywiście ten przykład byłby bardziej przekonujący dla przypadków użycia między mapą a unordered_map .

g++ 6.4 Stdlibc ++ benchmark uporządkowanego a nieuporządkowanego zestawu

Testowałem tę dominującą implementację Linux C ++, aby zobaczyć różnicę:

Pełne szczegóły i analiza testu porównawczego zostały podane pod adresem: Jaka jest podstawowa struktura danych STL w C ++? i nie będę ich tutaj powtarzał.

„BST” oznacza „przetestowano z, std::seta„ mapa skrótów ”oznacza„ przetestowano z std::unordered_set. „Sterta” jest, dla std::priority_queuektórej przeanalizowałem: Heap vs Binary Search Tree (BST)

Krótkie podsumowanie:

• wykres wyraźnie pokazuje, że w tych warunkach wstawianie haszmap było zawsze dużo szybsze, gdy jest więcej niż 100 tys. elementów, a różnica rośnie wraz ze wzrostem liczby elementów

  Koszt tego przyspieszenia polega na tym, że nie jesteś w stanie efektywnie poruszać się po kolei.

• krzywe wyraźnie sugerują, że zamówiony produkt std::setjest oparty na BST i oparty na std::unordered_sethashmap. W odpowiedzi referencyjnej dodatkowo potwierdziłem, że przez krok GDB debugowanie kodu.

Podobne pytanie dla mapvs unordered_map: Czy jest jakaś przewaga używania map nad unordered_map w przypadku trywialnych kluczy?

Z drugiej strony, powiedziałbym, że wygodnie jest mieć rzeczy w związku, jeśli chcesz przekonwertować je na inny format.

Możliwe jest również, że chociaż dostęp do niego jest szybszy, czas potrzebny na zbudowanie indeksu lub pamięci używanej podczas tworzenia i / lub uzyskiwania dostępu do niego jest dłuższy.

Jeśli chcesz, aby rzeczy były posortowane, użyj set zamiast unordered_set. unordered_set jest używany nad zestawem, gdy kolejność przechowywania nie ma znaczenia.

Chociaż ta odpowiedź może być opóźniona o 10 lat, warto na to zwrócić uwagę std::unordered_set ma również wady bezpieczeństwa.

Jeśli funkcja skrótu jest przewidywalna (jest to zwykle przypadek, chyba że stosuje środki zaradcze, takie jak losowa sól), atakujący mogą ręcznie tworzyć dane, które powodują kolizje hash i powodują, że wszystkie wstawienia i wyszukiwania zajmują O (n) czasu .

Można to wykorzystać do bardzo skutecznych i eleganckich ataków typu „odmowa usługi”.

Wiele (większość?) Implementacji języków, które wewnętrznie używają map skrótów, napotkało to:

• Javascript
• PHP
• Jawa