Implementing FIFO behaviour in a hashset
.net, c#, data-structures, hashset
Solution
You could pair the hash set with a queue. The hash set will give you O(1) complexity to test whether the element is in the queue and the queue will give you first in first out behavior, also in O(1)
If you're storing reference types the extra space overhead of using the two data structures would be minimal (double the number of references).
If you are using value types a self-balancing binary search tree would give you look-up and insertion in O(log n) but would allow you to store only one copy of each element.
Problem
I have a requirement in which each element in a collection must be unique and for that purpose i have used a hashset. I however also want to remove elements from the hashset based on First In First Our order. However the default Hashset DataStructure in .NET doesn't have this behaviour. Is there any way to extend hashset to implement this behaviour or should i some other data structure.