A container with O(1) insertion (amortized) and O(n) iteration

Question

I'm looking for a set-like container class that has these basic properties:

1. has amortized O(1) insertion time, duplicate inserts are ignored
2. has O(n) iteration time (specifically O(capacity) is not acceptable)
3. reuses memory / only allocates when it exceeds current capacity

The use-case is that I have a larger container of objects. During each loop I'll add a subset of those objects to this new container. This subset can be from 1-5 objects or up to 10% of the entire set. I then iterate of the objects in this new set. Each loop the object will be cleared and the processed started again.

My original approach used a invasive boolean on the objects indicating if it belonged to this new set. Thus insertion was true constant time, and it used no new memory. However iteration was sub-optimal.

I've tried a boost::unordered_set and get worse performance than my original approach. Presumably since, as hash map, it fails to meet Point #2.

Point #3 is relevant since I'm coding at a latency level where the cost of memory allocation is very significant. Thus it is extremely unlikely that a container with continuous allocation will perform well.

Answer 1

Use your first approach to detect whether the element is already in the set (hash map). And put it also in a list for iterating..