title: Data structure for a set of keys with efficient find-missing
body: <p>I'm looking for a data structure that supports the following operations for 
  integer keys <code>k</code> ranging from 0 to M-1.</p>
  
  <ul>
  <li>O(1) or O(log n) <code>insert(k)</code>, <code>erase(k)</code>, <code>lookup(k)</code>.</li>
  <li>O(1) or O(log n) for the special operation <code>find_missing_key()</code> which returns any key not currently present in the structure.</li>
  <li>O(n) or O(n log n) space. In particular. should not be O(M).</li>
  </ul>
  
  <p>An obvious implementation would be a "list-of-free-keys" structure, implemented as a heap; but that would take O(M) space. Is there some data structure that fulfills all of the requirements?</p>