J'ai besoin d'un conteneur pour stocker des paires, j'ai deux opérations:
Pour la première opération, la carte est une bonne structure. Pour la deuxième opération, semble une file d'attente prioritaire est une bonne. Comment ferais-tu ceci? Est-ce qu'il y a de toute façon pour avoir les deux opérations effectuées sans avoir une boucle O (n)? Merci.
5 Réponses :
Créer un Structure de tas (pour la deuxième balle) et mettre chacun de ses nœuds dans un Carte (pour la première balle).
EDIT:
Une implémentation de Min Heap que j'avais fait du temps dans le passé
Vous pouvez également utiliser std :: priority_queue .
@Toolbox Une structure de tas est un moyen de mettre en œuvre une priorité_queue :)
Je sais - ce que je voulais dire, c'est qu'il n'est pas nécessaire de réapprouer ce qui fait déjà partie de la norme C ++.
boost :: Bimap pourrait faire ce que vous voulez, où la carte inverse est utilisée pour implémenter n ° 2.
Et si plusieurs clés ont la même valeur?
@Templatetypeypef: Votre choix, plusieurs index sont possibles, comme bimap
Je pense que le bimap est la meilleure route
Et si plusieurs clés ont la même valeur associée à eux?
Une solution asymptotique efficace pour cela serait d'utiliser une combinaison d'une table de hachage et d'un tas de fibonacci. Vous utiliseriez la table de hachage pour pouvoir accéder à la valeur associée à une clé particulière dans O (1) heure et utiliseriez le tas Fibonacci pour pouvoir rechercher rapidement la paire de la clé / de la valeur la plus basse (le faire dans O (1)).
Si vous souhaitez modifier la valeur associée à une clé, si vous augmentez la valeur, vous pouvez le faire dans (amorti) O (1) fois en utilisant l'opération d'augmentation-clé sur le tas de fibonacci, qui a o (1) Temps amorti. Si vous diminuez la valeur, il faudra une heure (log n) pour supprimer l'élément hors du tas Fibonacci, puis la réinsérer.
Globalement, cela donne une complexité de temps de
J'espère que cela vous aide!
C'est une bonne solution! Vous devriez également noter les effectifs: les garder synchronisés et l'utilisation de la mémoire.
@Mooing Duck - Idéalement, vous serez dans sa propre classe afin que vous ne puissiez pas obtenir les deux synchronisés les uns avec les autres. Et oui, il y a plus d'utilisation de la mémoire, bien que ce n'est qu'un facteur constant que d'avoir une seule des deux structures.
@TemplatetypeDef: +1, mais un tas de fibonacci plutôt qu'un tas binaire (ou un tas nary) - vraiment? Je comprends que les limites amorties théoriques peuvent être meilleures, mais est-ce le cas pratiquement? Voir, par exemple: Stackoverflow.com/Questtions/504823/... . De plus, les tas de Fibonaaci n'ont-ils pas en réalité une faible complexité des cas pour certaines opérations?
@Darren Engwirda- Fibonacci Les tas ont de mauvaises performances les plus performantes, mais d'excellentes performances amorties. Si vous devez garantir que chaque opération est rapide, une file d'attente brodée fonctionnerait également. Et oui, les tas de fibonacci peuvent être plus lents que les tas binaires. Cette solution est asymptotiquement bonne, mais pourrait ne pas être aussi rapide en pratique que si le jeu de données est assez gros.
@TemplatetypeDef: lol sur facteur constant plus d'une structure, pour quelque chose asymptotiquement bien plutôt que pratiquement bon.
Selon mon standard C ++ 0X, Il suffit d'utiliser une carte. Lookup aléatoire est O (journal (n)) et pour obtenir l'élément le plus élevé prend o (1) heure. La propriété fondamentale d'itérateurs de conteneurs associatifs est qu'elles se déroulent à travers les conteneurs de l'ordre non décroissant des clés où le non-décroissant est défini par la comparaison utilisée par la comparaison utilisée. Pour les construire.
Est-ce que cela se tient pour la carte de hachage? puis rechercher serait aussi O (1)
Non, les hachages sont non-commandées, vous ne pouvez donc pas trouver l'élément le plus élevé.