Data structure in c for fast look-up/insertion/removal of integers (from a known finite domain)

Question

I'm writing a mobile phone based game in c. I'm interested in a data structure that supports fast (amortized O(1) if possible) insertion, look-up, and removal. The data structure will store integers from the domain [0, n] where n is known ahead of time (it's a constant) and n is relatively small (on the order of 100000).

So far I've considered an array of integers where the "ith" bit is set iff the "ith" integer is contained in the set (so a[0] is integers 0 through 31, a[1] is integers 32 through 63 etc).

Is there an easier way to do this in c?

Answer 1

Your idea is simple and efficient - assuming you have 100000 / 8 = 12.5 KB to play with then I don't see any point in looking for other solutions.

Answer 2

A flat array would do, but would cost 100,000 bits. Another possibility is a "hash set".