Différence entre std::set et std::priority_queue

Question

Étant donné que à la fois std::priority_queue et std::set (et std::multiset) sont des conteneurs de données qui stockent des éléments et vous permettent d'y accéder de manière ordonnée, et ont la même complexité d'insertion O(log n), quels sont les avantages d'utiliser l'un par rapport à l'autre (ou, dans quelles situations opter pour l'un ou l'autre)?

Je sais que les structures sous-jacentes sont différentes, mais je suis moins intéressé par la différence dans leur implémentation que par la comparaison de leur performance et de leur adéquation pour divers usages.

Note: Je sais pour l'absence de doublons dans un ensemble. C'est pourquoi j'ai également mentionné std::multiset car il a exactement le même comportement que std::set mais peut être utilisé lorsque les données stockées sont autorisées à être comparées en tant qu'éléments égaux. Alors s'il vous plaît, ne commentez pas sur le problème des clés uniques/multiples.

Answer 1

Une file de priorité seulement vous donne accès à un élément dans un ordre trié -- c'est-à-dire, vous pouvez obtenir l'élément de priorité la plus élevée, et quand vous le retirez, vous pouvez obtenir le suivant en priorité, et ainsi de suite. Une file de priorité permet également des éléments en double, donc c'est plus comme un multi-ensemble qu'un ensemble. [Edit : Comme @Tadeusz Kopec l'a souligné, construire un tas est également linéaire sur le nombre d'éléments dans le tas, alors que la construction d'un ensemble est en O(N log N) sauf s'il est construit à partir d'une séquence déjà ordonnée (auquel cas c'est aussi linéaire)].

Un ensemble vous permet un accès complet dans un ordre trié, donc vous pouvez, par exemple, trouver deux éléments quelque part au milieu de l'ensemble, puis traverser dans l'ordre de l'un à l'autre.

Answer 2

std::priority_queue permet de faire ce qui suit :

1. Insérer un élément O(log n)
2. Obtenir le plus petit élément O(1)
3. Effacer le plus petit élément O(log n)

tandis que std::set offre plus de possibilités :

1. Insérer n'importe quel élément O(log n) et la constante est supérieure à celle de std::priority_queue
2. Trouver n'importe quel élément quelconque O(log n)
3. Trouver un élément, >= que celui que vous cherchez O(log n) (lower_bound)
4. Effacer n'importe quel élément quelconque O(log n)
5. Effacer n'importe quel élément par son iterator O(1)
6. Déplacer vers l'élément précédent/suivant dans l'ordre trié O(1)
7. Obtenir le plus petit élément O(1)
8. Obtenir le plus grand élément O(1)

Answer 3

Set/multiset sont généralement soutenus par un arbre binaire. http://en.wikipedia.org/wiki/Binary_tree

priority_queue est généralement soutenu par un tas. http://en.wikipedia.org/wiki/Heap_(data_structure)

Donc la vraie question est quand devriez-vous utiliser un arbre binaire plutôt qu'un tas?

Les deux structures sont présentées dans un arbre, cependant les règles sur la relation entre les ancêtres sont différentes.

Nous appellerons les positions P pour parent, L pour enfant gauche et R pour enfant droit.

Dans un arbre binaire L < P < R.

Dans un tas P < L et P < R

Alors les arbres binaires trient "latéralement" et les tas trient "verticalement".

Donc si nous considérons ceci comme un triangle alors dans l'arbre binaire L,P,R sont complètement triés, tandis que dans le tas la relation entre L et R est inconnue (seulement leur relation à P).

Cela a les effets suivants:

• Si vous avez un tableau non trié et que vous voulez le transformer en arbre binaire cela prend O(nlogn) temps. Si vous voulez le transformer en tas cela ne prend que O(n) temps, (car il suffit de comparer pour trouver l'élément extrême)

• Les tas sont plus efficaces si vous avez seulement besoin de l'élément extrême (le plus bas ou le plus haut selon une fonction de comparaison). Les tas ne font que les comparaisons nécessaires (paresseusement) pour déterminer l'élément extrême.

• Les arbres binaires effectuent les comparaisons nécessaires pour ordonner l'ensemble entier, et maintiennent l'ensemble entier trié tout le temps.

• Les tas ont une recherche en temps constant (peek) de l'élément le plus bas, les arbres binaires ont une recherche en temps logarithmique de l'élément le plus bas.

Answer 4

Étant donné que à la fois std::priority_queue et std::set (et std::multiset) sont des conteneurs de données qui stockent des éléments et vous permettent d'y accéder de manière ordonnée, et ont la même complexité d'insertion O(log n), quels sont les avantages d'utiliser l'un par rapport à l'autre (ou, dans quelles situations choisir l'un ou l'autre)?

Même si les opérations d'insertion et de suppression pour les deux conteneurs ont la même complexité O(log n), ces opérations pour std::set sont plus lentes que pour std::priority_queue. Cela est dû au fait que std::set effectue de nombreuses allocations mémoire. Chaque élément de std::set est stocké dans sa propre allocation. std::priority_queue (avec le conteneur sous-jacent std::vector par défaut) utilise une seule allocation pour stocker tous les éléments. D'autre part, std::priority_queue effectue de nombreuses opérations d'échange sur ses éléments tandis que std::set n'effectue que des échanges de pointeurs. Ainsi, si l'échange est une opération très lente pour le type d'élément, utiliser std::set peut être plus efficace. De plus, l'élément peut ne pas être échangeable du tout.

La surcharge mémoire pour std::set est également beaucoup plus importante car elle doit stocker de nombreux pointeurs entre ses noeuds.

Answer 5

Pour être honnête, je n'ai jamais utilisé une file de priorité. Mais j'ai trouvé une excellente explication de quand l'utiliser sur cette page sgi : http://www.sgi.com/tech/stl/priority_queue.html.

La note de bas de page [2] le décrit bien. Je n'étais pas sûr si je pouvais faire un copier-coller donc j'ai mis un lien.