Fastest container or algorithm for unique reusable ids in C++
<p>I have a need for unique reusable ids. The user can choose his own ids or he can ask for a free one. The API is basically</p>

<pre><code>class IdManager {
public:
  int AllocateId();          // Allocates an id
  void FreeId(int id);       // Frees an id so it can be used again
  bool MarkAsUsed(int id);   // Let's the user register an id. 
                             // returns false if the id was already used.
  bool IsUsed(int id);       // Returns true if id is used.
};
</code></pre>

<p>Assume ids happen to start at 1 and progress, 2, 3, etc.  This is not a requirement, just to help illustrate.</p>

<pre><code>IdManager mgr;
mgr.MarkAsUsed(3);
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
</code></pre>

<p>Would print</p>

<pre><code>1
2
4
</code></pre>

<p>Because id 3 has already been declared used.  </p>

<p>What's the best container / algorithm to both remember which ids are used AND find a free id?</p>

<p>If you want to know the a specific use case, OpenGL's glGenTextures, glBindTexture and glDeleteTextures are equivalent to AllocateId, MarkAsUsed and FreeId</p>
