Find unused ID.

[Uzytkownik]

I've map<unsigned int, Class*>. I'd like to find unused ID.
Is it easier (and/or faster) code:
template<class Class>
int findID(map<unsiged int, Class*>)
{
unsigned int max;
set<unsigned int> Set;
for(map<unsigned int, Class*>::iterator it = mymap.begin(); it !=
mymap.end; it++)
{
Set.insert(it->first);
if(it->first > max)
max = it->first;
}
for(unsigned int i = 0; i <= max; i++)
if(Set.find(i) == Set.end())
return i;
return max + 1;
}
Regards.

 

[Cyrille]

Uzytkownik a écrit :

I've map<unsigned int, Class*>. I'd like to find unused ID.
Is it easier (and/or faster) code:
template<class Class>
int findID(map<unsiged int, Class*>)
{
unsigned int max;
set<unsigned int> Set;
for(map<unsigned int, Class*>::iterator it = mymap.begin(); it !=
mymap.end; it++)
{
Set.insert(it->first);
if(it->first > max)
max = it->first;
}
for(unsigned int i = 0; i <= max; i++)
if(Set.find(i) == Set.end())
return i;
return max + 1;
}
Regards.

Just look for it directly in the map:
for ( unsigned int i=0;
i < std::numeric_limits<unsigned int>::max();
i++)
if (mymap.find(i) != mymap.end())
return i;

It may not be the fastest code, but it is the easiest.

The fastest should be:
unsigned int i = 0;
for ( map<unsigned int, Class*>::iterator it = mymap.begin();
it != mymap.end();
it++, i++))
if (it->first != i)
return i;

Indeed, inside std::map, the data is sorted by its key member, so you
just have to check non corresponding ones.

--