c++ - 为类的每个实例分配唯一 ID

Question

我正在从 XML 文件中导入项目。每个 XML 元素(FoodItem、Person、Order、CoffeeRun)都是一个类，并且每个元素都有唯一 ID(该类唯一)。

<person>
<id>0</id>
<name>...</name>
</person>

<FoodItem>
<id>0</id>
<name>Coffee</name>
</FoodItem>

我正在尝试开发一个子类 DatabaseItem，以确保一个类中没有两个对象具有相同的 ID。你能帮助我开发一种有效的算法来确保没有对象与另一个对象具有相同的 ID 吗？

我的 2 种方法对我来说似乎有点低效:

• 使用一个静态类 vector ，其中包含目前为止所有使用过的 ID。当创建一个新的 DatabaseID( int requestedID ) 对象时，我通过遍历 vector 中所有使用的值来检查 ID 是否可用，以检查 ID 是否已经存在，我认为这就是 Big-O速度？

• 使用静态类 bool vector，其中 vector 的每个元素对应一个 id(因此 vector[1] 将对应于 ID 为 1 的对象)。我通过查看 vector 中的元素是否为真来检查 ID 是否已被占用 if ( v[nID] == true ) {//此 ID 已被占用 }。这看起来效率很低，因为这意味着我的 vector 会占用大量内存，对吗？

• 我不熟悉在 C++ 中使用 map ，但也许我应该在这里使用一个？

任何关于高效算法的建议都会非常有帮助:

class DatabaseItem
{
    public:
        static unsigned int instanceCount;

        DatabaseItem()
        {
            // Assign next available ID
        }

        DatabaseItem( unsigned int nID )
        {
            // Check that that id is not already taken
            // if id is taken, look for next available id &
            // give the item that id
        }

    private:
        unsigned int uniqueID;
};

// My solution: Do you have any better ideas that ensure no objects jave the same ID?
// This seems REALLY inefficient...
class DatabaseItem
{
    public:
        static unsigned int instanceCount;
        static vector <unsigned int> usedIDs;

        DatabaseItem()
        {
            DatabaseItem::instanceCount++;
            uniqueID = instanceCount;
            usedIDs.add( instanceCount );
        }

        DatabaseItem( unsigned int nID )
        {
            if ( isIDFree( nID ) )
            {
                uniqueID = nID;
            }
            else uniqueID = nextAvailableID();

            DatabaseItem::instanceCount++;
        }

        bool isIDFree( unsigned int nID )
        {
            // This is pretty slow to check EVERY element

            for (int i=0; i<usedIDs.size(); i++)
            {
                if (usedIDs[i] == nID)
                {
                    return false;
                }
            }

            return true;
        }

        unsigned int nextAvailableID()
        {
            while ( true )
            {
                unsigned int ID = 0;

                if ( isIDFree( ID ) )
                {
                    return ID;
                }
                else ID++;
            }
        }

    private:
        unsigned int uniqueID;
};


// Alternate that uses boolean vector to track which ids are occupied
// This means I take 30000 boolean memory when I may not need all that
class DatabaseItem
{
    public:
        static unsigned int instanceCount;
        static const unsigned int MAX_INSTANCES = 30000;
        static vector <bool> idVector;

        // Is this how I initialise a static class vector...? (note this code will be outside the class definition)
        // vector <bool> DatabaseItem::idVector( MAX_INSTANCES, false );

        DatabaseItem()
        {
            uniqueID           = nextAvailableID();
            idVector[uniqueID] = true;
        }

        DatabaseItem( unsigned int nID )
        {
            if ( nID >= MAX_INSTANCES )
            {
                // not sure how I shd handle this case?
            }

            if ( idVector[nID] == false )
            {
                uniqueID      = nID;
                idVector[nID] = true;
            }
            else
            {
                uniqueID           = nextAvailableID();
                idVector[uniqueID] = true;
            }

            instanceCount++;
        }

        unsigned int nextAvailableID()
        {
            for (int i=0; i<idVector.size(); i++)
            {
                if ( !idVector[i] )
                {
                    return i;
                }
            }

            return -1;
        }

        bool isIDFree( unsigned int nID )
        {
            // Note I cannot do this: Because I am using Mosync API & it doesn't support any C++ exceptions'

            // I declare idVector with no size! so not idVector( 30000, false)... just idVector;
            // then I allow an exception to occur to check if an id is taken

            try
            {
                return idVector[nID];
            }
            catch (...)
            {
                return true;
            }
        }

    private:
        unsigned int uniqueID;
};

Answer 1

A vector<bool>是通过每个 bool 值一位来实现的，因此它不会像您假设的那样浪费那么多空间。

A set<unsigned int>是解决这个问题的简单方法。 vector<bool>是比较快的。两者都可以使用一些内存。根据您的使用模式，还有一些其他解决方案:

• 安unsigned int all_taken_upto_this;结合 set<int>涵盖所有高于 all_taken_upto_this 的奇怪 ID - 从集合中移除并尽可能增加计数器。

• A map<unsigned int, unsigned int>这在逻辑上被视为 begin,end采取的或自由的序列。这需要一些小技巧才能正确实现(例如，当您在两个元素之间添加最后一个 ID 时合并连续的 map 元素)

您可能会使用预制的“稀疏位集”类型的数据结构——我不知道任何实现 OTOH。