(It can be made even more efficient under certain situations with a std::set<> and std::set<>::upper_bound() , but that's unlikely to be worth it.
Another idea, which may be worth it with some patterns of usage would be to maintain a cache of recently released ids).
The protocol I am implementing requires me to use the lowest possible IDs, and I'd also need the ID factories to be independent of each other for the same type. I understand how your code works, mostly, but I'm not sure how to change it. Also, I don't see where the implementation is for release?
Edit: I updated my first post with my current code
Thanks, I'll start dissecting that code to try and understand it...
> The protocol I am implementing requires me to use the lowest possible IDs
I'm a bit curious. Why?
I actually don't know, and I'm pretty sure I could get away with using your previous example given how the protocol works (and if it turns out that I can, I will indeed use that method), but currently my job is to implement the protocol as-is. The problem is that it has to be compatible with existing software that expects it to behave this way.
Anyway, I'll start digesting your examples. I guess it is reassuring to know that the reason I couldn't think of a simpler way is because there actually wasn't a simpler way.
'next' holds the next id to be generated if there are no free released ids to pick from.
If we have generated a total of 1000 fresh ids, 'next' would be 'min' + 1000. If 50 of these 1000 ids are in the free ids list, no new id is generated, and the smallest free id is picked. We would now have 49 of the 1000 ids generated left in the free list.
If the free list is empty, all 1000 ids generated so far are in use; we would need to get a fresh id. The new id would be 'next' ( 'min' + 1000 ), and next would be incremented; it becomes 'min' + 1001.
> I can't tell which performs better, or if mine is somehow incorrect.
Yours is correct.
However, IDs.find(++lowest) is O( log N );
while ++iter ... ( *iter > n ) ... ( iter < max ) is O(1).
In while(IDs.find(++lowest) != IDs.end()) the ordered-ness of the std::set<> is not being exploited.
In that scenario, we might as well change std::set<> to std::unordered_set<> for which find() is amortised O(1)
template < typename T > struct id_factory< T, int_type<T> >
staticconstexpr T min = std::numeric_limits<T>::min() ;
T n ;
if( free_ids.empty() ) n = next++ ; // *** and used here
else // ...
return n ;
T next = min ; // **** declared with an initializer here