Ordonné Structure de données qui permet d'éliminer efficacement les doublons

Question

J'ai besoin d'une structure de données qui

• doit être commandé (ajouter des éléments a, b and c à une structure vide, les fera être à des positions 0, 1 and 2).
• Permet d'ajouter des éléments répétés. C'est, je peux avoir une liste avec a, b, c, a, b.
• Permet de supprimer toutes les occurrences d'un élément donné (si je fais quelque chose comme delete(1), il supprimera toutes les occurrences de 1 dans la structure). Si j'ai des éléments a, b, c, d, c, e et supprimer l'élément c, je devrais obtenir a, b, d, e.
• J'ai juste besoin d'accéder aux éléments de deux façons. Le premier, est lors de la suppression d'une ocorrence donnée (voir point ci-dessus) et l'autre est quand je convertis les données que j'ai dans cette structure en une liste.

Je ne sais pas vraiment quelle pourrait être la meilleure structure de données ici. Je pensais d'abord à quelque chose comme une liste (le problème est d'avoir une opération O(n) lors de la suppression des éléments), mais peut-être qu'il me manque quelque chose? Qu'en est-il des arbres/tas? Hashtables/cartes?

Je dois supposer que je ferai autant d'ajouter que de supprimer avec cette structure de données.

Merci

Answer 1

Je pense que vous pourriez avoir à écrire une structure de données dédiée (en fonction de vos besoins en matière d'efficacité).

Quelque chose comme une liste doublement liée avec un nextEqualItemPtr supplémentaire et un HashMap pointant vers le premier de chaque élément.

Ensuite, vous pouvez trouver rapidement le premier "b" à supprimer et suivre tous les nextEqualItemPtrs pour les supprimer tous (double lien si facile à garder la liste intacte). Frais généraux garde la carte à jour vraiment. La liste nextEqualItemPtr d'un nouvel élément peut simplement pointer vers le nœud retourné par map.put (clé) .nextEqualItemPtr

Je voudrais certainement utiliser quelque chose de simple d'abord, et ne brancher ce genre de chose que si/quand il est trop lent .

Answer 2

l'interface Bag de Collections Apache (homepage) devrait répondre à vos besoins. Il a de nombreuses implémentations donc peut-être aussi un qui garde la trace de l'ordre d'insertion (votre premier point).

Et il a:

• removeAll
• remove(count)

Il est également très rapide par rapport à l'aide d'un LinkedList normal ou ArrayList mais je ne suis pas sûr d'avoir des indices d'éléments insérés .

Il est décrit comme

Interface Sac pour les collections qui ont un certain nombre d'exemplaires de chaque objet