C++中用于唯一可重复使用ID的最快容器或算法

Question

我需要独特的可重用ID。用户可以选择自己的ID，或者请求一个免费的ID。API基本上是这样的：

class IdManager {
public:
  int AllocateId();          // Allocates an id
  void FreeId(int id);       // Frees an id so it can be used again
  bool MarkAsUsed(int id);   // Let's the user register an id. 
                             // returns false if the id was already used.
  bool IsUsed(int id);       // Returns true if id is used.
};

假设 id 从 1 开始递增，2、3 等等。这不是必须的，只是为了帮助说明。

IdManager mgr;
mgr.MarkAsUsed(3);
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());
printf ("%d\n", mgr.AllocateId());

将会输出

1
2
4

因为id 3已经被声明使用了。

什么是最好的容器/算法，既可以记住哪些id已被使用，又可以找到一个空闲的id？

如果你想知道一个具体的用例，OpenGL的glGenTextures、glBindTexture和glDeleteTextures相当于AllocateId、MarkAsUsed和FreeId。

- gman

---

AllocatedId() 会将其标记为已使用吗？ - Naveen

让OpenGL为您分配和跟踪ID有什么问题吗？ - jalf

我正在编写一个GL驱动程序。这就是为什么是的，AllocateId()会将其标记为已使用。 - gman

您的用户名是可接受的。：] - GManNickG

最大的ID号码和一次分配的最大ID数量是多少？这可能会有所不同。 - Mark Ransom

ids 可以是 INT_MIN 到 INT_MAX 之间的任何数字，除了唯一无效的 ID 0。除了内存不足外，没有最大数量的 ids，但我怀疑大多数用户程序不会使用超过几千个。 - gman

Answer 1

我的想法是使用 std::set 和 Boost.interval，这样 IdManager 就能保存一组不重叠的可用 ID 区间。 AllocateId() 很简单且速度很快，只需返回第一个空闲区间的左边界即可。其他两种方法稍微有些复杂，因为可能需要分割现有的区间或合并相邻的区间。但它们也非常快速。

下面是使用区间的示意图：

IdManager mgr;    // Now there is one interval of free IDs:  [1..MAX_INT]
mgr.MarkAsUsed(3);// Now there are two interval of free IDs: [1..2], [4..MAX_INT]
mgr.AllocateId(); // two intervals:                          [2..2], [4..MAX_INT]
mgr.AllocateId(); // Now there is one interval:              [4..MAX_INT]
mgr.AllocateId(); // Now there is one interval:              [5..MAX_INT]

这是代码本身：

#include <boost/numeric/interval.hpp>
#include <limits>
#include <set>
#include <iostream>


class id_interval 
{
public:
    id_interval(int ll, int uu) : value_(ll,uu)  {}
    bool operator < (const id_interval& ) const;
    int left() const { return value_.lower(); }
    int right() const {  return value_.upper(); }
private:
    boost::numeric::interval<int> value_;
};

class IdManager {
public:
    IdManager();
    int AllocateId();          // Allocates an id
    void FreeId(int id);       // Frees an id so it can be used again
    bool MarkAsUsed(int id);   // Let's the user register an id. 
private: 
    typedef std::set<id_interval> id_intervals_t;
    id_intervals_t free_;
};

IdManager::IdManager()
{
    free_.insert(id_interval(1, std::numeric_limits<int>::max()));
}

int IdManager::AllocateId()
{
    id_interval first = *(free_.begin());
    int free_id = first.left();
    free_.erase(free_.begin());
    if (first.left() + 1 <= first.right()) {
        free_.insert(id_interval(first.left() + 1 , first.right()));
    }
    return free_id;
}

bool IdManager::MarkAsUsed(int id)
{
    id_intervals_t::iterator it = free_.find(id_interval(id,id));
    if (it == free_.end()) {
        return false;
    } else {
        id_interval free_interval = *(it);
        free_.erase (it);
        if (free_interval.left() < id) {
            free_.insert(id_interval(free_interval.left(), id-1));
        }
        if (id +1 <= free_interval.right() ) {
            free_.insert(id_interval(id+1, free_interval.right()));
        }
        return true;
    }
}

void IdManager::FreeId(int id)
{
    id_intervals_t::iterator it = free_.find(id_interval(id,id));
    if (it != free_.end()  && it->left() <= id && it->right() > id) {
        return ;
    }
    it = free_.upper_bound(id_interval(id,id));
    if (it == free_.end()) {
        return ;
    } else {
        id_interval free_interval = *(it);

        if (id + 1 != free_interval.left()) {
            free_.insert(id_interval(id, id));
        } else {
            if (it != free_.begin()) {
                id_intervals_t::iterator it_2 = it;
                --it_2;
                if (it_2->right() + 1 == id ) {
                    id_interval free_interval_2 = *(it_2);
                    free_.erase(it);
                    free_.erase(it_2);
                    free_.insert(
                        id_interval(free_interval_2.left(), 
                                    free_interval.right()));
                } else {
                    free_.erase(it);
                    free_.insert(id_interval(id, free_interval.right()));
                }
            } else {
                    free_.erase(it);
                    free_.insert(id_interval(id, free_interval.right()));
            }
        }
    }
}

bool id_interval::operator < (const id_interval& s) const
{
    return 
      (value_.lower() < s.value_.lower()) && 
      (value_.upper() < s.value_.lower());
}


int main()
{
    IdManager mgr;

    mgr.MarkAsUsed(3);
    printf ("%d\n", mgr.AllocateId());
    printf ("%d\n", mgr.AllocateId());
    printf ("%d\n", mgr.AllocateId());

    return 0;
}

- user184968

---

这也是我所想的，尽管我不知道boost::numeric::interval。当我调用free_.find()时，我不太确定您的<运算符如何找到正确的区间，但我相信我会弄清楚的。 - gman

在许多情况下，使用pos参数作为提示可以使集合中的insert操作更加高效。例如，当您决定在分配后删除一个区间时，您将在完全相同的位置插入，因此保留在移除和插入点之前的iterator实际上会增加性能，因为此时不需要查找。 - Matthieu M.

干得好。分配将会很快，而且有Mattheiu的性能提示，释放也应该很好。我想唯一可能存在的问题是在实际使用中，使用不同的分配和释放选择时会创建多少个间隔，但这可以进行分析...我有几种情况，这种设计可能会派上用场。 - Len Holgate

我对一个行为问题有评论。创建一个变量和我的单元测试发现了一个问题。如果您填满id管理器并尝试释放最后一个id，则不会正确释放插槽。例如，uint16_t max将是65535，在完整的IdManager中，it = free_.upper_bound(id_interval(id,id)); if (it == free_.end()) { return ;将解决free_.end()，因为没有区间可以严格小于interval(max,max)通过您的operator<定义，这个free调用不会修改底层集合。您需要检查id是否与max匹配。 - user3023451

当ID被删除时，没有检查与先前间隔的合并，因此如果您分配n个ID然后取消分配它们，则会得到n个范围为1的间隔。这浪费了很多内存！ - QuantumKarl

Answer 2

最好知道你需要跟踪多少个id。如果只有一百左右，使用简单的set即可，并进行线性遍历以获取新的id。但如果像几千个这样的数量，线性遍历将会变成性能瓶颈，尤其是考虑到set的缓存不友好特性。

个人建议如下：

• set：易于跟踪id O(log N)
• 将新id提供为当前最大值+1... O(1)

如果在应用程序的生命周期中不分配超过max<int>()个id，则应该可以满足要求，否则...使用更大的类型（将其设置为无符号的，使用long或long long），这是最容易开始的方法。

如果这还不够，请给我留言，我将编辑并寻找更复杂的解决方案。但是，簿记越复杂，实际执行所需时间就越长，犯错的机会也越高。

- Matthieu M.

---

我的当前实现使用了一个集合和线性搜索。当前的最大值加1是一个很好的想法，但如果用户选择INT_MAX或UINT_MAX作为他们的个人ID之一，它就会完全失败。所谓的失败是指我必须回到线性搜索。问题是，这是一个GL驱动程序，每秒钟调用数百次glBind函数。因此，在查找时O(log N)似乎太慢了。 - gman

Answer 3

类似于skwllsp，我会跟踪未分配的范围，但我的方法略有不同。基本容器将是一个映射，其中键是范围的上限，值是下限。

IdManager::IdManager()
{
    m_map.insert(std::make_pair(std::numeric_limits<int>::max(), 1);
}

int IdManager::AllocateId()
{
    assert(!m_map.empty());
    MyMap::iterator p = m_map.begin();
    int id = p->second;
    ++p->second;
    if (p->second > p->first)
        m_map.erase(p);
    return id;
}

void IdManager::FreeId(int id)
{
    // I'll fill this in later
}

bool IdManager::MarkAsUsed(int id)
{
    MyMap::iterator p = m_map.lower_bound(id);

    // return false if the ID is already allocated
    if (p == m_map.end() || id < p->second || id > p->first)))
        return false;

    // first thunderstorm of the season, I'll leave this for now before the power glitches
}

bool IdManager::IsUsed(int id)
{
    MyMap::iterator p = m_map.lower_bound(id);
    return (p != m_map.end() && id >= p->second && id <= p->first);
}

- Mark Ransom

Answer 4

但我认为您不必保证id必须从1开始。您只需确保可用的id必须大于所有分配的id。

例如，如果先注册了3，则下一个可用的id可以是4。我认为使用1并非必要。

- zs2020

---

除非您不重复使用ID，并且已经限制了分配的ID总数，即使您的用户正在分配、使用和释放ID。 - Len Holgate

如果第一个注册的ID是0xffffffff怎么办？ - Mark Ransom

Answer 5

我假设您想要能够使用 Id 类型的所有可用值，并且希望重复使用已释放的 Id。我还假设如果您从多个线程中使用它，则会锁定集合...

我会创建一个类，其中包含一个 set 来存储分配的 id、一个 list 来存储空闲的 id，以及一个最大分配值，以避免我必须预加载每个可用的 id。

因此，您可以从空的分配 id 集合和空的空闲 id 列表开始，最大分配为 0。如果有空闲列表，则分配时取出其头部；否则取出最大值，检查它是否在分配的 id 集合中，因为它可能被保留。如果是，则增加最大值并重试；如果不是，则将其添加到集合中并返回它。

释放 id 时，只需检查它是否在集合中，如果是，则将其推入空闲列表中。

要保留 id，只需检查集合中是否存在该 id，如果不存在，则添加它。

这样可以快速回收 id，这可能对您有利或不利，也就是说，allocate()、free()、allocate() 将在没有其他线程访问集合时返回相同的 id。

- Len Holgate

Answer 6

压缩向量。但我认为任何容器都不会有明显的差异。

- ima

Answer 7

通常情况下，我会建议您在了解哪些方法被最多使用之前，坚持使用简单的实现。过早地进行调优可能会证明是错误的。使用简单的实现，并记录其使用情况，然后您可以从最常用的函数进行优化。如果您只需要几百个 ID 和一个简单的向量就足够了，那么为快速删除或快速分配进行优化是没有意义的。

- daramarak

---

我认为检查id是否存在应该是快速部分，因为每秒60帧调用glBindXXX数百或数千次，每次调用都需要检查id是否存在，以便知道是否要注册一个新的id。 - gman

但是你有没有想过通常需要多少个ID。你能承受偶尔耗时的重新分配，还是更好地固定分配时间并进行更耗时的检查。向量可以快速查找，但在添加和删除方面更加棘手。但是，如果您的ID数量是半固定的，那么无论如何它可能是正确的选择，如果您可以承受在当前池用尽时进行大规模重新分配，我会坚持使用向量并使用队列来跟踪空闲ID。 - daramarak

Answer 8

所以我的一个朋友指出，在这种情况下，哈希表可能更好。大多数OpenGL程序不使用超过几千个ID，因此具有4096个插槽的哈希表几乎保证每个插槽只有1或2个条目。有一些退化情况，许多ID可能会进入1个插槽，但这是非常不可能的。使用哈希表会使AllocateID变得更慢，但可以使用集合来进行。对于我的用例而言，分配速度较慢比InUse速度快不那么重要。

- gman