J'ai un std :: Ensemble de STD :: String. J'ai besoin de "index" ou "position" de chaque chaîne dans l'ensemble, est-ce un concept significatif dans le contexte?
Je suppose que trouver () retournera un itérateur à la chaîne. Ma question pourrait donc être mieux formulée comme suit: "Comment convertir un itérateur en un numéro?".
3 Réponses :
std :: Distance est ce que vous avoir besoin. Vous voudrez, je suppose std :: Distance (set.begin (), Find_Result)
Remarque: std :: Distance est O (n) depuis que SET Itérateurs sont des modèles de bidirectionaliterator et non randomAssiterator
std :: Distance est O (n) Y a-t-il un moyen d'obtenir les statistiques de la commande dans O (log (n))?
Il n'y a pas de bon moyen. Calcul de la distance est réalisable dans O (logn) pour toute structure décente avec une comptabilité convenable, mais elle n'est pas requise par la norme et aucune bibliothèque STL que je ne sache. Vous avez besoin d'OtFind ou écrivez une structure sur mesure.
Je ne pense pas que ce soit significatif - les réglages sont «auto-clés» et triés ainsi que «l'index» seraient invalidés lorsque l'ensemble est modifié.
Bien sûr, cela dépend de la manière dont vous avez l'intention d'utiliser l'index et si l'ensemble est essentiellement statique (dis un dictionnaire).
Je pense que tant qu'un conteneur est commandé, la position de ses éléments a une signification sémantique. En particulier, la position réelle pourrait être importante, en fonction de ce que vous faites (données expressionnées par exemple). Si l'ensemble change, alors naturellement la position de certains éléments.
Malgré ce que les autres ont écrit ici, je ne pense pas que "l'indice" ou "position" a signification par rapport à un ensemble. En termes mathématiques, un ensemble n'expose que ses membres et peut-être sa cardinalité. Les seules opérations significatives impliquent de tester si un élément est membre de l'ensemble et combinant ou soustrayant des ensembles pour donner de nouveaux ensembles.
Certaines personnes parlent des ensembles comme structures de données en termes de lâche, par des facettes d'être "commandées" ou "non ordonnées", et qu'ils permettent des doublons ou appliquent l'unicité. L'ancienne facette distingue un tableau avec une protection d'insertion O (N) , où une tentative d'insérer un élément ne scanne d'abord les membres existants pour voir si le nouvel élément existe et, sinon, insère le nouvel élément À la fin, et une table de hachage, que pourrait conserver une telle commande uniquement dans une chaîne de godet. Un arbre tel que l'arbre rouge-noir utilisé par L'autre facette - si l'ensemble permet des éléments en double - n'a pas de sens dans les mathématiques et est décrit plus précisément comme un sac . Une telle structure reconnaît la différence entre l'identité et la valeur basée sur la valeur ".
Votre problème peut impliquer de prendre soin d'une position; Ce n'est pas clair ce que signifie ce poste, mais je m'attends à ce que vous alliez avoir besoin d'une structure de données séparée de Cela peut également aider à clarifier le problème pour réfléchir à la façon dont vous le modeler comme relations , comme dans une base de données relationnelle. Qu'est-ce qui comprend la clé? Quelles parties des entités peuvent varier de manière indépendante? std :: set est quelque part entre les deux; Son ordre traversant est déterministe par rapport au strict ordre faible imposé Par le prédicat comparateur, mais, contrairement à la matrice esquissée ci-dessus, il ne conserve pas ordre d'insertion . .
std :: Set pour le modeler correctement. Peut-être un std :: map cartographie de votre ensemble d'éléments à chaque poste ferait. Cela ne garantirait pas que les positions sont uniques.
Je construis un "ensemble" de chaînes uniques d'une base de données, puis ces chaînes doivent être représentées comme des chiffres. La fonction de distance () suffit. Il est possible (probable?) Cet ensemble n'est pas un bon choix, je l'ai fait parce que cela semblait un moyen efficace de garantir l'unicité des chaînes. La STL est un nouveau territoire pour moi.
Si vous avez trouvé un design qui résout votre problème, tout va bien. Si vous vous réchauffez dans les concepts STL, vous pourriez profiter du livre éléments de la programmation par Stepanov et McJones ( élémentsOfprogramming.com ).
Cela peut être vrai pour les "ensembles" en général, mais les éléments d'un std :: set ont des positions définies