C ++中唯一可重用ID的最快容器或算法 [英] Fastest container or algorithm for unique reusable ids in C++

问题描述

我需要唯一可重复使用的ID.用户可以选择自己的ID，也可以索取免费的ID.该API基本上是

I have a need for unique reusable ids. The user can choose his own ids or he can ask for a free one. The API is basically

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等.这不是必需条件，只是为了帮助说明.

Assume ids happen to start at 1 and progress, 2, 3, etc. This is not a requirement, just to help illustrate.

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已经被声明使用.

Because id 3 has already been declared used.

同时记住使用哪些ID并找到免费ID的最佳容器/算法是什么?

What's the best container / algorithm to both remember which ids are used AND find a free id?

如果您想了解特定的用例，则OpenGL的glGenTextures，glBindTexture和glDeleteTextures等效于AllocateId，MarkAsUsed和FreeId

If you want to know the a specific use case, OpenGL's glGenTextures, glBindTexture and glDeleteTextures are equivalent to AllocateId, MarkAsUsed and FreeId

推荐答案

我的想法是使用 std :: set 和 Boost.interval ，所以 IdManager 将保存一组免费ID的非重叠间隔. AllocateId()非常简单，非常快捷，仅返回第一个空闲间隔的左边界.其他两种方法稍微有点困难，因为可能有必要拆分一个现有的间隔或合并两个相邻的间隔.但是它们也相当快.

My idea is to use std::set and Boost.interval so IdManager will hold a set of non-overlapping intervals of free IDs. AllocateId() is very simple and very quick and just returns the left boundary of the first free interval. Other two methods are slightly more difficult because it might be necessary to split an existing interval or to merge two adjacent intervals. However they are also quite fast.

这是使用间隔的想法的说明:

So this is an illustration of the idea of using intervals:

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

这篇关于C ++中唯一可重用ID的最快容器或算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！