Я бы сказал, что в общем случае, когда ключ может иметь любой тип, разрешенный картой, это невозможно. Даже способность сказать, существует ли какой-то неиспользуемый ключ, требует определенных знаний о типе.
Если мы рассмотрим ситуацию с int, вы можете хранить std :: set смежных сегментов неиспользуемых ключей (поскольку эти сегменты не перекрываются, можно использовать естественное упорядочение - просто сравните их начальные точки). Когда нужен новый ключ, вы берете первый сегмент, обрезаете первый индекс и помещаете остальные в набор (если остальные не пусты). Когда какой-то ключ освобождается, вы обнаруживаете, есть ли в наборе соседние сегменты (в силу природы набора это возможно при сложности O (log n)), и выполняете объединение, если необходимо, в противном случае просто помещаете сегмент [n, n] в набор.
таким образом, вы определенно будете иметь тот же порядок сложности времени и порядок потребления памяти, что и карта независимо от истории запросов (поскольку количество сегментов не может быть больше, чем map.size () + 1)
как то так:
class TKeyManager
{
public:
TKeyManager()
{
FreeKeys.insert(
std::make_pair(
std::numeric_limits<int>::min(),
std::numeric_limits<int>::max());
}
int AlocateKey()
{
if(FreeKeys.empty())
throw something bad;
const std::pair<int,int> freeSegment=*FreeKeys.begin();
if(freeSegment.second>freeSegment.first)
FreeKeys.insert(std::make_pair(freeSegment.first+1,freeSegment.second));
return freeSegment.first;
}
void ReleaseKey(int key)
{
std:set<std::pair<int,int>>::iterator position=FreeKeys.insert(std::make_pair(key,key)).first;
if(position!=FreeKeys.begin())
{//try to merge with left neighbour
std::set<std::pair<int,int>>::iterator left=position;
--left;
if(left->second+1==key)
{
left->second=key;
FreeKeys.erase(position);
position=left;
}
}
if(position!=--FreeKeys.end())
{//try to merge with right neighbour
std::set<std::pair<int,int>>::iterator right=position;
++right;
if(right->first==key+1)
{
position->second=right->second;
FreeKeys.erase(right);
}
}
}
private:
std::set<std::pair<int,int>> FreeKeys;
};