Ordered Data Structure that allows to efficiently remove duplicate items
- by devoured elysium
I need a data structure that
Must be ordered (adding elements a, b and c to an empty structure, will make them be at positions 0, 1 and 2).
Allows to add repeated items. This is, I can have a list with a, b, c, a, b.
Allows removing all ocurrences of a given item (if I do something like delete(1), it will delete all ocurrences of 1 in the structure).
I can't really pick what the best data structure could be in here. I thought at first about something like a List(the problem is having an O(n) operation when removing items), but maybe I'm missing something? What about trees/heaps? Hashtables/maps?
I'll have to assume I'll do as much adding as removing with this data structure.
Thanks