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

C ++ 0x introduit unordered_set qui est disponible dans boost et dans de nombreux autres endroits. Ce que je comprends, c’est que unordered_set est une table de hachage avec une complexité de recherche O(1) . D’autre part, set n’est rien d’autre qu’une arborescence avec log(n) complexité de recherche log(n) . Pourquoi est-ce que quelqu’un utiliserait set au lieu de unordered_set ? Est-ce qu’il y a un besoin de set plus?

Lorsque, pour quelqu’un qui veut parcourir les éléments de l’ensemble, la commande compte.

Les ensembles non ordonnés doivent payer pour leur temps d’access moyen O (1) de plusieurs manières:

set utilise moins de mémoire que unordered_set pour stocker le même nombre d’éléments.
Pour un petit nombre d’éléments , les recherches dans un set peuvent être plus rapides que les recherches dans un ensemble unordered_set .
Même si de nombreuses opérations sont plus rapides dans le cas moyen de unordered_set , elles garantissent souvent une meilleure complexité dans les cas les plus défavorables (par exemple, insert ).
Cet set sortinge les éléments est utile si vous souhaitez y accéder dans l’ordre.
Vous pouvez comparer lexicographiquement différents set avec < , <= , > et >= . unordered_set s n'est pas requirejs pour prendre en charge 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 “O ( log n)” au pire.

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

Considérons 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érez l’algorithme de la fortune. http://en.wikipedia.org/wiki/Fortune%27s_algorithm

Encore une chose, en plus de ce que d’autres personnes ont déjà mentionné. Alors que la complexité amortie attendue pour insérer un élément dans un unordered_set est O (1), de temps en temps il faudra O (n) car la table de hachage doit être restructurée (le nombre de compartiments doit changer) – 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 pourrait être préférable dans certaines applications.

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

Si vous voulez une gamme de données dans le conteneur, par exemple: Vous avez enregistré l’heure dans le jeu et vous voulez du temps du 2013-01-01 au 2014-01-01.

Pour unordered_set c’est impossible.

Bien entendu, cet exemple serait plus convaincant pour les cas d’utilisation entre map et unordered_map .

En passant, je dirais qu’il est pratique d’avoir des relations dans une relation si vous souhaitez le convertir dans un format différent.

Il est également possible que le temps d’access à l’index ou la mémoire utilisée lors de la création et / ou de l’access soit plus rapide.

Si vous voulez que les choses soient sortingées, vous utiliserez set au lieu de unordered_set. unordered_set est utilisé par-dessus lorsque la commande stockée n’a pas d’importance.