지도에서 첫 번째로 사용 가능한 키를 가져옵니다.

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; 

그래서이 값들을 보유한지도를 가질 수 있습니다.

1,2,4,8,10 

어떤 경우에는 내가 ID 3 항에 다음 엔티티를하고 싶습니다.

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; 
}