Generating and re-using unique, sequential, positive integers (re-posting from StackOverflow as this is more of a review)

In the past, I've often encountered the following problem and so far my go-to solution was to combine a counter with a hashtable (with open-addressing).

The only operations I need to implement are the following:


next: generates a new integer or re-uses a previously freed one
free: frees a previously generated integer
size: returns the number of generated integers (excluding those who have been freed and not yet re-used)


Here's some working code that I use very often when this case pops up.

class IdGenerator
{
    typedef std::uint64_t Id;

public:
    IdGenerator():
        total_ids_(0)
    {
    }

    Id next()
    {
        Id id;
        if (available_ids_.empty())
        {
            id = total_ids_;
            ++total_ids_;
        }
        else
        {
            auto it = available_ids_.begin();
            id = *it;
            available_ids_.erase(it);
        }
        return id;
    }

    void free(Id id)
    {
        available_ids_.insert(id);
    }

    Id size() const
    {
        return total_ids_ - available_ids_.size();
    }

private:
    std::unordered_set&lt;Id&gt; available_ids_; // usually, I use open-adressing here
    Id total_ids_;
};


While this code generally brings good performance, I've always wondered if there was a faster way of doing this.
The only improvement I can see here is pretty marginal:

unordered containers have an average insert complexity of O(1), but that can become O(N) in degenerate cases (because of hash collision handling). That's pretty rare, but enough in my book to not use the datastructure if a simpler alternative would work just as well.

In your case, std::unordered_set doesn't provide anything you wouldn't get from a simple std::stack or std::queue anyways. So I would personally switch to one of these.

That being said, depending on the context behind how and why you use such an index generator, there are sometimes better ways to do this.

For example, if you are using this logic in order to manage a small block allocator, you can store the free list inside the unalocated memory. see example