de l'index ou de la position dans std::set

J'ai un std::set de std::string. J'ai besoin de la "index" ou "position" de chaque chaîne dans le jeu, est-ce un véritable concept dans le contexte?

Je suppose que find() retourne un itérateur à la chaîne, donc ma question est peut-être mieux exprimé ainsi : "Comment puis-je convertir un itérateur pour un certain nombre?".

  • stackoverflow.com/questions/1796503/index-or-position-in-stdset/... @seh si nous voyons un point de vue sémantique, ce que vous avez dit est correct, Mais les décors sont commandés. Ils sont généralement mis en œuvre en utilisant une certaine forme d'Équilibre des arbres comme le rouge noir de l'arbre, et l'utilisation stricte de la faiblesse de la commande à l'ordre les éléments de l'ensemble. Je ne sais pas si la norme mandats cet ordre ou pas. Mais c'est la façon dont il est
  • Vous pouvez envisager d'utiliser un vecteur trié plutôt que d'un ensemble. Plutôt que d'utiliser find(), vous obtenez la performance de la recherche binaire avec LB = std::lower_bound(v.begin(),v.end(),value) => un itérateur vers le premier élément >= value, et index = LB - v.begin() est l'indice de cet élément, ce qui peut être égale à value ou plus, si value n'est pas dans le vecteur trié.
InformationsquelleAutor | 2009-11-25
  1. 15

    std::distance est ce que vous avez besoin. Vous voulez, je suppose que std::distance(set.begin(), find_result)

    • Remarque: std::distance est O(n) puisque set les itérateurs sont des modèles de BidirectionalIterator et pas RandomAccessIterator
    • std::la distance est de O(N) est-il possible d'obtenir les statistiques d'ordre de O(log(n)) ?
    • Il n'y a pas de bonne façon. Le calcul de la distance est réalisable en O(logN) tout décent structure adaptée tenue des livres, mais ce n'est pas requise par la norme, et pas de bibliothèque STL je sais qu'il ne. Vous avez besoin otfind ou d'écrire une structure sur mesure.
    InformationsquelleAutor laura
  2. 1

    Je ne pense pas que c'est significatif - de l'ensemble sont "auto incrustée" et triées ainsi, l '"indice" serait invalidé lorsque le jeu est modifié.

    Bien sûr, cela dépend de la manière dont vous souhaitez utiliser l'index et si l'ensemble est essentiellement statique (un dictionnaire).

    • Je pense que tant que le conteneur est ordonné à la position de ses éléments a de sens sémantique. En particulier, la position réelle peut être important, en fonction de ce que vous faites (horodatée de données par exemple). Si l'ensemble des modifications, puis naturellement le fait de la position de certains éléments.
    InformationsquelleAutor Gray-M
  3. 1

    En dépit de ce que les autres ont écrit ici, je ne pense pas que "index" ou "position" a de sens que par rapport à un ensemble. En termes mathématiques, un ensemble n'expose qu'à ses membres et peut-être sa cardinalité. Le sens des opérations impliquent de tester si un élément est un membre de l'ensemble, et en les combinant ou en soustrayant des ensembles pour produire de nouvelles séries.

    Certaines personnes parler de jeux de que les structures de données en perdant termes, par des facettes de l'être "commandé" ou "non ordonnée", et si elles permettent de reproduire ou de faire respecter l'unicité. L'ancien facette distingue un tableau avec une O(n) insertion de la garde, où une tentative d'insérer un élément balaye d'abord les membres existants pour voir si le nouvel élément existe et, si non, insère le nouvel élément à la fin, et d'une table de hachage, qui pourrait les conserver afin qu'au sein d'un segment de la chaîne. Un arbre Rouge-Noir Arbre utilisé par std::set est quelque part entre les deux; sa traversée de l'ordre est déterministe à l'égard de la faible stricte de commande imposées par le comparateur de prédicat, mais, à la différence du tableau esquissé ci-dessus, il ne conserve pas ordre d'insertion.

    L'autre facette — savoir si le jeu permet de dupliquer des éléments — est dénuée de sens en mathématiques, et plus précisément décrit comme une sac. Une telle structure reconnaît la différence entre l'identité et de valeur "de la monotonie."

    Problème peut impliquer soucier de la position de certains; il n'est pas clair de quelle position, mais je pense que vous allez avoir besoin de quelques données de structure distincte de std::set pour modéliser correctement. Peut-être un std::map cartographie de votre ensemble d'éléments pour chaque position de le faire. Qui ne garantirait pas que les positions sont uniques.

    Il peut également aider à clarifier le problème à penser à comment vous auriez du modèle comme relations, comme dans une base de données relationnelle. Ce que comprend la clé? Quelles portions de les entités peuvent varier de manière indépendante?

    • Je suis la construction d'un "set" de chaînes uniques à partir d'une base de données, puis ces chaînes doivent être représentés comme des numéros. La distance en fonction de() suffit. Il est possible (probable?) que le jeu n'est pas un bon choix, je l'ai fait parce qu'il me semblait un moyen efficace de garantir l'unicité des cordes. Le TSL est toute nouvelle pour moi.
    • Si vous avez trouvé un design qui permet de résoudre votre problème, tout est bien. Si vous vous trouvez réchauffement de la STL concepts, vous pouvez profiter du livre des Éléments de Programmation par Stepanov et McJones (elementsofprogramming.com).
    InformationsquelleAutor seh