Delete a value from set with constant time using STD and C++

Question

I need to have a set of integers and able to remove a value in constant time. How do I achieve that?

For now I'm using std::list but it's not constant time:

int myints[]= {17,89,7,14};
std::list<int> mylist (myints,myints+4);
mylist.remove(89);

Answer 1

If you truly need constant time deletion guaranteed then you probably want to use an std:bitset if the size is known at compile time.

If the size isn't known at compile time, you might consider Boost dynamic_bitset or std::vector<bool>. The latter is often criticized because it's not a container, which can be quite surprising since vector instantiated over other types is a container. Nonetheless, it appears that it can do the job at hand perfectly well.

In any case, with any of these you'd have a bit/Boolean value for each value in the allowable range. You'd "insert" a value by setting the bit/Boolean at that index to 1/true, and "delete" a value by setting the the bit/Boolean at that index to 0/false.

For all of the preceding, enumerating the elements currently in the set (or even finding how many it contains) is linear on the range of numbers the set can potentially store (whereas your current implementation can find the number of items currently stored in the set with constant complexity, and find the members in the set with complexity that's linear on the number of items it actually contains.

If you expect the set of numbers to be relatively sparse, and can live with the deletion time usually being approximately constant, even though it's not guaranteed, then you probably want to use std::unordered_set instead.

There is also std::set, which guarantees logarithmic complexity for a deletion. This is normally O(log N), which is slower than std::unordered_set (normally O(1)), but its worst case is also O(log N), which is better than the worst case for unordered_set, which is O(N) in the worst case.

Any of these is likely to give a substantial speed improvement over the std::list you're (apparently) currently using. The exact difference will vary, but a full order of magnitude speed improvement (for this particular operation) wouldn't be terribly surprising at all (well, I wouldn't be surprised, anyway).