Lấy khóa có sẵn đầu tiên trong bản đồ

Question

Tôi có một bản đồ lưu trữ con trỏ đến một đối tượng bằng ID của chúng.

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

Để gán một ID để Entity Tôi chỉ có thể lấy giá trị mới nhất trong entitymap và tăng nó bằng 1.

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

Nhưng số lượng có thể trở thành không cần thiết lớn vì tất cả bây giờ và sau đó là một thực thể là đã xóa và xóa khỏi bản đồ.

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

Vì vậy, tôi có thể có bản đồ chứa các giá trị này;

1,2,4,8,10 

Trong trường hợp này, tôi muốn Pháp nhân tiếp theo yêu cầu ID 3.

Answer 1

Kể từ khi ID được sắp xếp số lượng, bạn có thể đi bộ qua toàn bộ bản đồ cho đến khi bạn tìm thấy một "lỗ":

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 

này có thể mất nhiều thời gian nếu bản đồ lớn và lỗ đầu tiên là gần cuối cùng . Bạn có thể kiểm tra đầu tiên nếu giá trị khóa lớn nhất (được cho bởi m.crbegin()->first) là lớn hơn đáng kể so với m.size() trước khi bắt tay vào thăm dò này.

Answer 2

Giả sử danh sách không phát triển nhiều, ít nhất bạn có thể giữ số nhận dạng nhỏ nhất được phát hành. Sau đó, khi bạn sử dụng lại nó, hãy tìm kiếm số nhận dạng có sẵn tiếp theo như được đề cập bởi 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 
    } 
} 

Đây là mã giả, cho bạn thấy rằng nhận dạng tự do nhỏ nhất có phải là một biến tĩnh trong lớp học của bạn (chung cho tất cả các trường hợp.)

Như đã đề cập trong một chú thích, bạn có thể sử dụng một vector thay thế. Mặc dù nó sẽ không được sắp xếp, bạn vẫn sẽ không phát triển định danh vô thời hạn. Chỉ nhược điểm của vector là bạn sử dụng một bộ nhớ nhỏ ... (rất nhiều nếu bạn xử lý nhiều đối tượng, nhưng bản đồ cũng vậy.)

Answer 3

Bạn có thể giữ Heap của tất cả các phím được giải phóng. Mỗi lần bạn giải phóng khóa, bạn thêm khóa đó vào heap và mỗi khi bạn sử dụng khóa, bạn sẽ xóa nó khỏi heap. Cả hai hoạt động này là O (log n). Bạn sẽ tạo một đống để nút gốc có khóa nhỏ nhất.

Nếu heap trống, thì bạn chỉ cần cấp phát một khóa mới bằng cách tăng phím lớn nhất trước đó như bình thường.

Answer 4

Đây là khả năng chậm, tùy thuộc vào cách dày đặc bản đồ của bạn, nhưng khá dễ hiểu:

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