Raghavendra Mahuli wrote:

Is O(ln2 n) good enough for all of those operations?

--------I think that is sufficient

Is the number of possible values bounded? If so, how many possible

values of elements are there? 10,000? 2^32? I don't mean how many

elements you need to store in your container, but how many different

values might exist for the type of your integer; for example, if you're

using 16-bit integers, there are 2^16=65536 possible values.

-----i am storing memory addresses....So all values in the range are

possible.....but they'll generally be multiples of 4...........And

maximum

possible value is 2^32.

For the values that aren't multiples of 4, stick them in a std::set.

The access time for them will be logarithmic with the cardinality of the

set, but since that cardinality is small, the performance should be good.

This leaves 2^(32-2) = 2^30 values to store; you could use a sequence of

bits, initialized to zero, to represent whether each value is in the

collection. Since you allow up to two of each element, you'll probably

want an extra bit per element to show whether it has been inserted more

than once. This means you need 2^31 bits. I would recommend using two

std::vector<bool>: one to represent whether each value had been

inserted at least once, and another to represent whether each value had

been inserted more than once. You'll need at least 256 MB of RAM, plus

space for the std::set. The machines where I work typically have

multiple GB of RAM, so this is probably the solution I would choose if

performance were critical.