Given a 64 bit positive integer. How to determine in the most efficient way whether the given integer has ever been seen or not?
Implementation in C++11 (Please do include this fact, while suggesting your opinions)
Intent: I am generating numbers randomly, by flipping one bit at a time. I need to check every time on generation of a number whether it has been previously generated or not? ex: 1,4,8,16,3,5,9,11,12, .... .
1.I can create an unordered_map. However, I would be wasting memory for storing the value part which is boolean in this case. And also hashing isnt the cheapest operation and also their is a penalty of rehasing.
- Can create a list and keep it sorted. Too expensive operations --Sorting and lookup.