Fastest way to check if a number is in a list of numbers

Question

I need to check whether an ID (a long integer) is in a list of ~10,000 IDs. I need to do this about 10^9 times over on a loop, and speed is relatively important. Is using a c++ set the quickest way to do this? Something like:

set<long> myset;

// (Populate myset)

long id = 123456789;

if(myset.find(id) != myset.end()) {
     // id is in set
}

Or is there a quicker way?

Answer 1

The quickest way, if your long has a limited range, is a bitmap (e.g. vector<bool>). If that's not doable, a unordered_set (hash_set) should be attempted. And if that keeps hitting worst-case, then use a set

Answer 2

Hm, depending on how you generate the numbers and how many there are, it might be faster to use an std::vector ,sort it (you can even keep it sorted while inserting the numbers), and the use binary search to check if the number is in there.

Generally, a set works fine, but there are tradeoffs. The vector has less memory overhead, and since all numbers are stored in a continuous block of memory, it might outperform a set in some situations, but you would have to test that.

Answer 3

You can build a hash table and check in O(1) if the ID exist.