地図で最初に利用可能なキーを取得

Question

私はオブジェクトIDを使ってオブジェクトへのポインタを格納するマップを持っています。

typedef std::map<unsigned int, Entity*> entityMap; 
entityMap entitymap; 

は、私はちょうどentitymapに最新の値を取り、1

Entity *entity = new Entity; 
entity->id = /*newest entity+1*/; 
entitymap.insert(std::pair<unsigned int,Entity*>(entity->id,entity)); 

ことによってそれを増加させることができるエンティティにIDを割り当てるには、しかし、すべてが今してエンティティであるため、数が不必要に大きくなる可能性が削除され、マップから削除されます。

std::map<unsigned int,Entity*>::iterator it; 
it = entitymap.find(EntityID); 
if(it != entitymap.end()) 
{ 
    Entity *entity= it->second; 
    entitymap.erase(it); 
} 
delete entity; 

私はこれらの値を保持するマップを持つことができました。私は次のエンティティID 3を主張したいと思います

1,2,4,8,10 

その場合

。

Answer 1

IDが数値的に順序付けられているので、あなたは「穴」を見つけるまで、あなたはマップ全体を歩くことができます：マップが大きく、最初の穴が終わり近くにある場合

unsigned int i = 1; // or whatever your smallest admissable key value is 

for (auto it = m.cbegin(), end = m.cend(); 
          it != end && i == it->first; ++it, ++i) 
{ } 

// now i is the next free index 

これは長い時間がかかることがあり。この調査に着手する前に、最大のキー値（m.crbegin()->firstによって与えられる）がm.size()よりかなり大きいかどうか最初に確認できます。

Answer 2

リストがあまり大きくならないと仮定すると、リリースされた最小の識別子を少なくとも保持することができます。それからあなたがそれを再使用するとき、Kerrek SBによって言及されるように次の利用可能な識別子を検索してください。

class { 
... 
    static int g_smallest_free_id; // init to 1 
... 
}; 

void delete_id() 
{ 
    if(m_id < g_smallest_free_id) { 
     m_id = g_smallest_free_id; 
    } 
} 

void new_id() 
{ 
    int id = g_smallest_free_id; 
    // the -1 is because it looks like you start your ids at 1 
    // since we skip all the known identifiers before id, 
    // the loop is reduced from the current id to the next only 
    for(interator it = list.begin() + id - 1; 
        it != list.end(); ++it) { 
     // find next available id 
    } 
} 

この

あなたは、ベクターを使用することができ、最小の自由な識別子は、あなたのクラスの静的変数なければならないことを示します（すべてのインスタンスに共通する。）コメントで述べたように

、擬似コードであります代わりに。ソートされていなくても、識別子を無期限に増やすことはできません。ベクトルの欠点は、少しのメモリを使用することです...（多くのオブジェクトを扱う場合はたくさんありますが、マップも同様です）

Answer 3

解放されたすべてのキーのうち、Heapを保つことができます。キーを解放するたびにヒープに追加し、キーを使用するたびにヒープからキーを削除します。これらの操作はどちらもO（log n）です。ルートノードが最小のキーを持つようにヒープを作成します。

ヒープが空の場合は、通常と同じように、前の最大のキーを増やして新しいキーを割り当てます。

Answer 4

これはあなたのマップがどのように密に応じて、潜在的に遅いが、理解することは非常に簡単です：

typedef std::map<Key, Value> Table; 

std::optional<Key> findFirstFreeSlot(const Key& start, const Key& end, const Table& table) 
{ 
    for (Key i = start; i <= end; i++) { 
    if (table.find(i) == table.end()) { 
     return i; 
    } 
    } 
    return std::none; 
}