Pourquoi quelqu'un utiliserait-il set au lieu de unordered_set?

C ++ 0x introduit unordered_setce qui est disponible dans boostet dans de nombreux autres endroits. Ce que je comprends, c'est qu'il unordered_sets'agit d'une table de hachage avec une O(1)complexité de recherche. D'un autre côté, ce setn'est rien d'autre qu'un arbre avec une log(n)complexité de recherche. Pourquoi diable quelqu'un utiliserait-il à la setplace de unordered_set? c'est à dire y a-t-il un besoin de setplus?

Quand, pour quelqu'un qui souhaite parcourir les éléments de l'ensemble, l'ordre compte.

Les postes non ordonnés doivent payer leur temps d'accès moyen O (1) de plusieurs manières:

• setutilise moins de mémoire que unordered_setpour stocker le même nombre d'éléments.
• Pour un petit nombre d'éléments , les recherches dans un fichier setpeuvent être plus rapides que les recherches dans un fichier unordered_set.
• Même si de nombreuses opérations sont plus rapides dans le cas moyen pour unordered_set, ils sont souvent assurés d'avoir de meilleures pires complexité des cas pour set(par exemple insert).
• Cela set trie les éléments est utile si vous souhaitez y accéder dans l'ordre.
• Vous pouvez lexicographique comparer différentes sets avec <, <=, >et >=. unordered_setne sont pas tenus de soutenir ces opérations.

Chaque fois que vous préférez un arbre à une table de hachage.

Par exemple, les tables de hachage sont "O (n)" dans le pire des cas. O (1) est le cas moyen. Les arbres sont au pire "O ( log n)".

Utilisez set lorsque:

1. Nous avons besoin de données ordonnées (éléments distincts).
2. Nous aurions à imprimer / accéder aux données (dans l'ordre trié).
3. Nous avons besoin d'un prédécesseur / successeur d'éléments.

Utilisez unordered_set lorsque:

1. Nous devons conserver un ensemble d'éléments distincts et aucune commande n'est requise.
2. Nous avons besoin d'un accès à un élément, c'est-à-dire pas de traversée.

Exemples:

ensemble:

Entrée: 1, 8, 2, 5, 3, 9

Sortie: 1, 2, 3, 5, 8, 9

Unordered_set:

Entrée: 1, 8, 2, 5, 3, 9

Sortie: 9 3 1 8 2 5 (peut-être cet ordre, influencé par la fonction de hachage)

Principalement différence:

Remarque: (dans certains cas, setc'est plus pratique) par exemple en utilisant vectorcomme clé

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 

La raison pour laquelle vector<int>peut être aussi clé setque le vectorremplacement operator<.

Mais si vous utilisez, unordered_set<vector<int>>vous devez créer une fonction de hachage pour vector<int>, car vector n'a pas de fonction de hachage, vous devez donc en définir une comme:

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
}

vous pouvez voir que dans certains cas, unordered_setc'est plus compliqué.

Principalement cité à partir de: https://www.geeksforgeeks.org/set-vs-unordered_set-c-stl/ https://stackoverflow.com/a/29855973/6329006

Parce que std :: set fait partie du C ++ standard et unordered_set ne l'est pas. C ++ 0x n'est PAS un standard, et Boost non plus. Pour beaucoup d'entre nous, la portabilité est essentielle, ce qui signifie s'en tenir à la norme.

Considérez les algorithmes Sweepline. Ces algorithmes échoueraient complètement avec les tables de hachage, mais fonctionneraient parfaitement avec des arbres équilibrés. Pour vous donner un exemple concret d'algorithme sweepline, considérons l'algorithme de fortune. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Encore une chose, en plus de ce que d'autres personnes ont déjà mentionné. Bien que la complexité après amortissement prévu pour l' insertion d' un élément à un unordered_set est O (1), chaque maintenant et il va prendre O (n) parce que les besoins de table de hachage à restructurées (le nombre de seaux besoins de changement) - même avec une «bonne» fonction de hachage. Tout comme l'insertion d'un élément dans un vecteur prend O (n) de temps en temps car le tableau sous-jacent doit être réalloué.

L'insertion dans un ensemble prend toujours au plus O (log n). Cela peut être préférable dans certaines applications.

Pardonnez-moi, encore une chose à noter à propos de la propriété triée:

Si vous voulez une plage de données dans le conteneur, par exemple: Vous avez stocké l'heure dans l' ensemble et vous voulez une heure du 01/01/2013 au 01/01/2014.

Pour unordered_set, c'est impossible.

Bien sûr, cet exemple serait plus convaincant pour les cas d'utilisation entre map et unordered_map .

g++ 6.4 Stdlibc ++ Benchmark ordonné vs non ordonné

J'ai comparé cette implémentation Linux C ++ dominante pour voir la différence:

Les détails et l'analyse complets du benchmark ont ​​été donnés à l' adresse : Quelle est la structure de données sous-jacente d'un ensemble STL en C ++? et je ne les répéterai pas ici.

"BST" signifie "testé avec std::setet" hash map "signifie" testé avec std::unordered_set. "Heap" est pour std::priority_queuelequel j'ai analysé à: Heap vs Binary Search Tree (BST)

En résumé:

• le graphique montre clairement que dans ces conditions, l'insertion de hashmap était toujours beaucoup plus rapide lorsqu'il y avait plus de 100k éléments, et la différence augmente à mesure que le nombre d'éléments augmente

  Le coût de cette augmentation de vitesse est que vous n'êtes pas en mesure de traverser efficacement dans l'ordre.

• les courbes suggèrent clairement que ordonné std::setest basé sur BST et std::unordered_setest basé sur hashmap. Dans la réponse de référence, j'ai en outre confirmé cela en déboguant le code par étape GDB.

Question similaire pour mapvs unordered_map: y a-t-il un avantage à utiliser map sur unordered_map en cas de clés triviales?

Au loin, je dirais qu'il est pratique d'avoir des choses dans une relation si vous cherchez à le convertir dans un format différent.

Il est également possible que si l'accès est plus rapide, le temps de construction de l'index ou la mémoire utilisée lors de sa création et / ou de son accès soit plus long.

Si vous voulez que les choses soient triées, vous utiliserez set au lieu de unordered_set. unordered_set est utilisé sur set lorsque la commande stockée n'a pas d'importance.

Bien que cette réponse ait peut-être 10 ans de retard, il convient de souligner qu'elle std::unordered_setprésente également des inconvénients en matière de sécurité.

Si la fonction de hachage est prévisible (c'est généralement le cas sauf si elle applique des contre-mesures telles qu'un sel aléatoire), les attaquants peuvent fabriquer à la main des données qui produisent des collisions de hachage et font que toutes les insertions et recherches prennent O (n) temps .

Cela peut être utilisé pour des attaques par déni de service très efficaces et élégantes.

De nombreuses (la plupart?) Implémentations de langages qui utilisent en interne des cartes de hachage se sont heurtées à ceci:

• Javascript
• PHP
• Java