Finding a nonexisting key in a std::map

Question

Is there a way to find a nonexisting key in a map?

I am using std::map<int,myclass>, and I want to automatically generate a key for new items. Items may be deleted from the map in different order from their insertion.

The myclass items may, or may not be identical, so they can not serve as a key by themself.

During the run time of the program, there is no limit to the number of items that are generated and deleted, so I can not use a counter as a key.

An alternative data structure that have the same functionality and performance will do.

Edit

I trying to build a container for my items - such that I can delete/modify items according to their keys, and I can iterate over the items. The key value itself means nothing to me, however, other objects will store those keys for their internal usage.

The reason I can not use incremental counter, is that during the life-span of the program they may be more than 2^32 (or theoretically 2^64) items, however item 0 may theoretically still exist even after all other items are deleted.

It would be nice to ask std::map for the lowest-value non-used key, so i can use it for new items, instead of using a vector or some other extrnal storage for non-used keys.

Answer 1

I'd suggest a combination of counter and queue. When you delete an item from the map, add its key to the queue. The queue then keeps track of the keys that have been deleted from the map so that they can be used again. To get a new key, you first check if the queue is empty. If it isn't, pop the top index off and use it, otherwise use the counter to get the next available key.

Answer 2

Let me see if I understand. What you want to do is

look for a key. If not present, insert an element.

Items may be deleted.

Keep a counter (wait wait) and a vector. The vector will keep the ids of the deleted items. When you are about to insert the new element,look for a key in the vector. If vector is not empty, remove the key and use it. If its empty, take one from the counter (counter++). However, if you neveer remove items from the map, you are just stuck with a counter.

Alternative: How about using the memory address of the element as a key ?