Nous avons besoin d'ADT ayant des fonctionnalités de recherche et de rang. C'est-à-dire, en plus de l'interface de la carte STL, une fonction 'int get_rank (clé)' est requise.
La mise en œuvre standard de cette fonction nécessite de soutenir et de mettre à jour un champ entier supplémentaire dans chaque nœud d'arborescence de recherche auto-équilibrée (par exemple, dans l'arborescence rouge-rouge, utilisé dans la carte STL / Set). Mais il semble que stl map / set ne le fait pas.
Nous recherchons une solution basée sur des conteneurs standard (STL, Boost) ayant la meilleure complexité de temps possible: Rechercher / ajouter / effacer un élément Prendre O (journal n) (comme dans la carte STL / Set), calculer le rang par une touche prend également O (log n).
Par le rang d'un élément, nous entendons la position de l'élément dans la séquence triée de tous les éléments de la carte / ensemble.
exemple. Ensemble = {0, 4, 6, 7, 8} rang (0) = 1, rang (4) = 2, rang (6) = 3, rang (7) = 4, rang (8) = 5.
À notre avis, sous la forme de la complexité de temps limite ci-dessus, le problème ne peut pas être résolu par une combinaison de deux cartes un tri par clé et autre tri par rang.
merci.
4 Réponses :
Je suppose que par Je pense Vous pouvez le faire "externe", car dans ce cas, le rang peut être extrapolé à partir du nombre de fois que le prédicat de comparaison est utilisé ... Il compte le nombre de tests, mais depuis Si vous avez donné une meilleure définition de class vous voulez réellement dire la distance entre la racine, car si elle pouvait être stockée contiguë avec la valeur que vous ne seriez pas obligée d'aller à une telle longueur. std :: map arrête tester dès qu'il obtient la bonne clé ... Ça devrait être d'accord :) Bien qu'il y ait probablement un peu de décalage à en déduire (1 ou 2) pour obtenir le grade à la place. class je peux travailler un peu plus mais je ne veux pas passer trop de temps dans la mauvaise direction.
Le rang de la clé donnée k est le nombre de clés inférieures ou égales à k.
E.g., Set Set S = {1, 3, 4, 6, 9}. Ensuite, rang (1) = 1, rang (4) = 3, rang (9) = 5.
La distance de fonction STL () peut être utilisée pour calculer le rang d'un élément X apparaissant dans l'ensemble S.
rang = distance (s.begin (), s.find (x));
Le problème est que sa complexité de temps est O (n).
Notez que les deux cartes proposées (ou définies) indexées par clé et par rang ne sont pas correctes. Le problème est qu'un changement d'un élément affecte les rangs de nombreux autres. E.G., ajout d'élément 0 à l'ensemble S ci-dessus modifier les rangs de tous les éléments existants: s '= {0, 1, 3, 4, 6, 9}. rang (1) = 2, rang (4) = 4, rang (9) = 6.
merci.
J'ai mis en place un "arbre noir-noir classé" similaire à un arbre noir rouge sauf chaque nœud stocke la distance entre le nœud qui lui précède via une traversée en ordre, plutôt que de stocker une clé. < / p>
Cela fait exactement ce que vous voulez, à l'exception du «rang» du premier nœud est 0 et non 1 (vous pouvez ajouter / soustraire 1 si nécessaire).
Ma solution est un domaine public et est basé sur un didacticiel de domaine public pour un arbre noir régulier. Toutes les opérations - y compris insertion, supprimer, trouver et déterminer le rang ont du temps logarithmique en ce qui concerne le nombre d'éléments de la structure de données.
Vous pouvez le trouver ici: http://code.google.com/p/Options/downloads/list
Vous devez obtenir la dernière version du lien ci-dessus, actuellement (à partir de cette écriture) rrb_v4_release.cpp.
Vous pouvez utiliser une autre carte comme des conteneurs.
Gardez un champ de taille peut rendre un arbre de recherche binaire facile à accéder au hasard.
Voici ma mise en œuvre ...
Style STD, Itérateur d'accès aléatoire ...
Taille d'arbre équilibré ...
https://github.com/mm304321141/zzz_lib/blob/master/sbtree. h
et b + arbre ...
https://github.com/mm304321141/zzz_lib/blob/master/bppree. h
Belle bibliothèque. Mais pourquoi ne pas fournir des notes en anglais?
J'ai une question. Vous avez 2 spécialisations pour SBTREE: Multimap et MultiSet. Qu'en est-il d'une carte régulière et d'une définition? Dans l'ensemble, une classe très utile, acclamations) cherchait un moment quelque chose comme ça. Vous ne pouvez pas voir une raison pour lesquelles les libs standard ne disposent pas de conteneurs équilibrés.
L'un de mes autres projets a besoin d'un rang de sommet multiples pris en charge ... Je le public après ça ...
Les complexités de la recherche, de l'insertion et de la suppression sont souvent inversement liées à l'autre. Nous ne pouvons pas décider quel compromis vous convient le mieux.
Il y a une mise en œuvre de l'arbre de classement satisfaisant toute la complexité de temps la contrainte, voir, par exemple, le livre de Cormen, T.H. "Introduction aux algorithmes".
Il peut être fait avec une extension GNU dans le
libstdc ++ , voir ici .