如何在 id 序列中有效地重用已发布的 id

Question

假设我们有 PID 生成器，它为 7 个进程 {1,2,3,4,5,6,7} 生成了 7 个 ID。 流程 3 和 6 已完成，id 3 和 6 可供使用。现在我们开始三个新进程。 如何实现高效算法，首先按此顺序为它们分配 ID 3、6 和 8。

我正在考虑将已发布的 ID 存储在排序树中，但这需要额外的结构来跟踪序列中的 'holes'。对正在使用的 id 进行排序的树结构有助于获得下一个最大的 id，但是它在寻找漏洞方面有什么优势吗？

Answer 1

就用一个优先级队列（堆）来追踪所有的漏洞，像这样：

#include <queue>

std::priority_queue<int> q;
int all_free_after = 1;

void free_one_pid(int pid) {
    // the priority_queue returns the largest one inside the queue
    // but we want the smallest one
    // so we are push the opposite number into the queue
    q.push(-pid);
}

int get_one_pid() {
    if (q.empty()) { return all_free_after++; }
    int res = -q.top();
    q.pop();
    return res;
}