Pourquoi sur terre serait d'utiliser n'importe lieu de unordered_set?

Question

S'il vous plaît, excusez mon ignorance sur ce sujet :)

C++0x est d'introduire unordered_set qui est disponible en boost et de nombreux autres endroits. Ce que je comprends, c'est qu' unordered_set est une table de hachage avec O(1) recherche de complexité. D'autre part, set n'est rien, mais un arbre avec log(n) recherche de complexité. Pourquoi sur terre serait d'utiliser n'importe set au lieu de unordered_set? j'.e est-il besoin d' set plus?

Answer 1

Non ordonnée ensembles doivent payer pour leurs O(1) temps d'accès moyen de plusieurs façons:

• set utilise moins de mémoire alors unordered_set de stocker le même nombre d'éléments.
• Pour un petit nombre d'éléments, des recherches dans une set pourrait être plus rapide que les recherches en unordered_set.
• Même si de nombreuses opérations sont plus rapides dans le cas moyen pour unordered_set, ils sont souvent la garantie d'avoir une meilleure pire des cas, la complexité de set (par exemple, insert).
• Qu' set trie les éléments est utile si vous souhaitez accéder dans l'ordre.
• Vous pouvez comparer les différents sets avec == et la comme. unordered_sets ne sont pas nécessaires à l'appui de ces opérations.

Answer 2

Lorsque, pour quelqu'un qui veut effectuer une itération sur les éléments de l'ensemble, l'ordre des questions.

Answer 3

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

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

Answer 4

Envisager sweepline algorithmes. Ces algorithmes manquerait totalement avec les tables de hachage, mais très beau travail de l'équilibre des arbres. Pour vous donner un exemple concret d'un sweepline algorithme de considérer la fortune de l'algorithme. http://en.wikipedia.org/wiki/Fortune%27s%5Falgorithm