Single data structure using 2 different comparators

Question

I have the following problem. A lot of elements to be processed. I need good time complexity for the following operations:

• contains element
• add element
• peek element

And by good time complexity I mean O(1) or O(logn).

I have well defined boolean predicate which determines when two elements are equal.

Each element can be marked/unmarked, but the value of this flag is not part of the equality check. I am using this structure in a while loop. I want to iterate over all the unmarked elements in a cycle that performs the following(until there is at least one unmarked element):

• it takes an unmarked element from the container (does not remove it)
• marks it
• constructs new unmarked element (depending on the one from step 1)
• pushes the new element into the container only if there is no equal element (does not matter marked or unmarked)

I thought of using the standard c++ set, which is sorted and using the marked flag for determining the order (i.e. unmarked come first, which could simulate peeking by getting the first element), but this breaks the "contains" method, because being marked/unmarked does not relate to the "equals" predicate.

So I need something between set and priority queue. Any ideas ? Thank you.

Answer 1

You can implement two hash tables. One represents unmarked elements, the other represents marked elements. Marking an element means moving it out of the unmarked hash table and into the marked hash table. Containment is determined to see if the element resides in either one of the tables. Finding an unmarked element means only searching the unmarked hash table.

Answer 2

You can implement the marks as a set of pointers to the elements, distinct from the main container, which sounds much like a hash table (C++ unordered_set). If the elements are not distinguished by their memory addresses but merely by their values, use a set of key values.