If I understand the objective entirely, I'd suggest a class perform the containment which owns two vectors, one of the type of the structure you're targeting, and the other a vector<int>.

Call the vector<someclass> storage, vector<int> deletedIdList.

You might prefer making deletedIdList a deque, but that's up to you.


The class would also have a "NextId" integer, starting at zero.

As insertions are performed, NextId is used an incremented.

That's true only if the deletedIdList is empty.

If the deletedIdList is not empty, then the last entry is removed, and the Id stored there is reused.

Reuse implies placement at storage[ id ];
Extension implies placement using storage.push_back.


When an entry is removed, the position at storage[ id ] is marked somehow - perhaps you're using smart pointers (I prefer this solution), which can be nulled - perhaps you set that object id to -1, however you like marking it.

The Id being removed is appended to the deletedIdList.


The advantage to this approach, when done cleanly, is constant time (relatively) to the reuse/new addition logic, as well as quick looping (given the extra step required to skip deleted entries) and simple control.