STL: choosing appropriate data structure

[Miran]

I have to manage some object list including object creation, deletion. Each object in the list has an unique ID of type unsigned long. When object is created an unique ID should be generated and the object should be added into the container. I suppose to generate IDs continiouosly by incrementing the maximal ID of the object list. Anyway after some objects are deleted from the list, deleted IDs can be used for creation of new objects. Which container is apropriate for this case map or just vector or might be deque?

[JohnW@Wessex]

A map would be the simplest way to achieve this.

You could use a vector if the maximum id is not too large. You would have to have a method of indicating which 'slots' held valid entries.

If you go the map route and want maximum speed then try std::tr1::unordered_map. I imagine that the hash function for an unsigned long is pretty simple and fast (probably just uses the value)

[Miran]

A map would be the simplest way to achieve this.

Is it really simpler than using vector?
When new object is to be created I should iterate from the begining to check whether the key of the current node is greater than key of the previous node by more than 1 increment. If so to use previous node key + 1 as an ID of new object to be created.
Is there a simple way to do this for map?

You could use a vector if the maximum id is not too large. You would have to have a method of indicating which 'slots' held valid entries.

In case of using vector I'll have an advantage of constant access time to the objects (in contrast to the map approach). Also STL find can be used to find first empty slot in the vector. But, as you mentioned, if maximum ID is going to be large vector memory reallocations and copying the objects will have impact on the speed.

I prefer simpler way for now. Could you please clarify why map is simpler?

Thank You.

[D_Drmmr]

I suppose to generate IDs continiouosly by incrementing the maximal ID of the object list. Anyway after some objects are deleted from the list, deleted IDs can be used for creation of new objects. Which container is apropriate for this case map or just vector or might be deque?

When new object is to be created I should iterate from the begining to check whether the key of the current node is greater than key of the previous node by more than 1 increment. If so to use previous node key + 1 as an ID of new object to be created.

So which is it? Do you have to fill 'gaps' in the id's immediately or do you always have to take the maximum + 1?

[laserlight]

Is it really simpler than using vector?

If your are willing to have unique ids in the range [0, n), then I believe that std::vector would be a simpler option than std::map (then again, it is not like either is particularly complicated). You could store (smart) pointers so as to handle the case of deleted objects (and presumably keep a count of the number of deleted objects so as to retain constant time insertion if no objects have been deleted), though that would not be ideal if you are likely to delete a majority of the objects.

When new object is to be created I should iterate from the begining to check whether the key of the current node is greater than key of the previous node by more than 1 increment. If so to use previous node key + 1 as an ID of new object to be created.
Is there a simple way to do this for map?

Use the rbegin() member function to get an iterator to the last element of the map, upon which you can get the corresponding key.

[JohnW@Wessex]

When new object is to be created I should iterate from the begining to check whether the key of the current node is greater than key of the previous node by more than 1 increment. If so to use previous node key + 1 as an ID of new object to be created.

Is this a requirement, or an implementation idea?

[Miran]

So which is it? Do you have to fill 'gaps' in the id's immediately or do you always have to take the maximum + 1?

Is this a requirement, or an implementation idea?

There is no such a requirement. But in the case if your ID range is small it might be relevant. So I suppose to fill the gaps first, then look for max + 1.

Use the rbegin() member function to get an iterator to the last element of the map, upon which you can get the corresponding key.

But if the gap is in the middle, how can rbegin() help?
I'll get the last node with maximal key, then again I should iterate from the end to the gap, isn't it?

[monarch_dodra]

Hi,
I think you should store all your objects inside either a vector or a map. If you choose vector, then you should place object ID n at vector object n. If you use maps, then the ID will be your key.
I cannot tell you which is the better solution, but both are valid, in my opinion.

For counting ID, I think you should of course have an "IDMax" variable, to know which IDs should be created, but also a vector (or list) for every time you destroy an object, to store available IDs that were deleted.

That way, you can do something like this (pseudo code):

//Create new object
if (listOfUnusedIds.empty())
    obect.setId(IDMax);
    IDMax++;
}
else
{
    unsigned int newId = listOfUnusedIds.pop_back();
    obect.setId(newId);
}

This way, you won't have to iterate over your objects to find un-used IDs.

[JohnW@Wessex]

Using std::map or std::tr1::unordered_map

Just increment the unsigned long index (rolling round to 0 if necessary) and insert.
If you are worried about overwriting entries after 4 billion inserts then use 'find' to check if it exists and increment again if so.

[JVene]

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.

[Miran]

Thank You to all of you for the answers.

JVene's approach is probably fastest one among suggestions.
But it will uselessly eat a memory if many objects are deleted.
Actually the speed is not much important in my case in contrast to the memory size and simplicity (managing 2 containers probably is not simpliest way).

JohnW@Wessex's suggestion always using MAX ID + 1 as new ID and map is quite simple, though little bit slow.
I think this way is convenient in my case (I'm not considering std::tr1::unordered_map since the project is assumed to be 1998 ANSI/ISO compatible).

[JohnW@Wessex]

Actually the speed is not much important in my case in contrast to the memory size and simplicity.

Then map sounds ideal.

and map is quite simple, though little bit slow.

'Slow' is a relative term. If your solution is 'quick enough' then that may be perfectly acceptable.