Queue-like data structure with fast search and insertion
- by Max
I need a datastructure with the following properties:
It contains integer numbers, no duplicates.
After it reaches the maximal size the first element is removed.
So if the capacity is 3, then this is how it would look when putting in it sequential numbers:
{}, {1}, {1, 2}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5} etc.
Only two operations are needed: inserting a number into this container (INSERT) and checking if the number is already in the container (EXISTS).
The number of EXISTS operations is expected to be approximately 2 * number of INSERT operations.
I need these operations to be as fast as possible.
What would be the fastest data structure or combination of data structures for this scenario?