2

我需要一个可搜索的 GUID 集合（存储为 16 个字节），其中实际的唯一 ID 是智能指针结构/类的成员。这是引用计数并由其他对象在“最后一个引用删除”的基础上指向 - 类似于std::shared_ptr. 但是由于我的智能指针类的自定义性质，我不想使用shared_ptr.

但是，我确实想使用类似std::unordered_map或std::unordered_set（如果它们足够快）来保存指针集合。

即使智能指针地址是唯一的，因此最好用作散列，但我需要表中的可搜索键作为 GUID；这样我就可以用它find(guid)来快速定位正确的智能指针。

很难用语言解释，所以这里有一些代码：

class SmartPointer
{
public:
   GUID guid;
   int refCount; // Incremented/decremented when things point or stop pointing to it.
   void* actualObject; // The actual data attached to the smart pointer.
};

// Generate a unique 128-bit id.
GUID id;

// Create the smart pointer object.
SmartPointer* sp = new SmartPointer();
sp->guid = id;

// Create a set of SmartPointers.
std::unordered_set<SmartPointer*> set;
set.insert(sp);

// Need to find a SmartPointer based on a known GUID and not the pointer itself.
SmartPointer* found = set.find(id);

我认为这应该可以通过像这里这样的自定义哈希/相等函数中的一些取消引用来实现，但我不确定具体如何。

4

1 回答 1

6

使用标准散列容器，您需要一个可散列键（即可以通过散列算法转换为 size_t 的东西）和键的等价运算符，以防散列冲突（即两个 GUID 不同但散列到相同的值）。

为了通过 GUID 查找 SmartPointer，您可能需要 unordered_map 而不是 unordered_set。请参阅底部的示例。

在任何情况下，有两种方法可以散列自定义类：(1) 专门化 std::hash 或 (2) 在散列容器的类型定义中提供散列和可能的相等函子。

专门化 std::hash

要为您的智能指针专门化 std::hash 以便它查看 GUID，请执行以下操作：

namespace std 
{ 
    template<>
    struct hash< SmartPointer > 
    {
        size_t operator()( const SmartPointer& sp ) const
        {
            return hash( sp.guid );
        }
    };

    template<>
    struct hash< GUID > 
    {
        size_t operator()( const GUID& id ) const
        {
            return /* Some hash algo to convert your GUID into a size_t */;
        }
    };
}

（这两种特化可以根据您的需要进行组合。如果您只使用 GUID 作为散列键，如下面的 unordered_map 示例中所示，那么您不需要 SmartPointer 的特化。如果您只散列 SmartPointer 作为您的键，如当你只使用 std::unordered_set 时，你可以直接在第一个专业化中散列 sp.guid，而不是让它踢到第二个专业化。）

定义了这些特化后，假设您为哈希类型定义了相等比较，它将在标准的基于哈希的容器中自动为您哈希。像这样使用它：std::unordered_map<GUID, SharedPointer>或std::unordered_set<SharedPointer>。（有关以这种方式进行专业化的更多信息，请参阅如何为自定义类型扩展 std::tr1::hash？。）

在散列容器类型中使用自定义函子

对于 (2)，您可以更改无序集/映射的类型并提供仿函数作为模板参数：

struct HashSmartPointer
{
    std::size_t operator()( const SmartPointer& sp ) const
    {
        return /* Some hash algo to convert your sp.guid into a size_t */;
    }
};

std::unordered_set< SmartPointer, HashSmartPointer > mySet;

再次假设您为 SmartPointer 定义了相等性以处理冲突（否则，将另一个参数添加到 unordered_set 的相等函子的模板参数中）。

完整示例

这是一个完整的程序，演示了我认为您所要求的内容：

#include <vector>
#include <cstdlib>
#include <cstdint>
#include <algorithm>
#include <cassert>
#include <unordered_map>

class GUID // Some goofy class. Yours is probably better
{
public:
   std::vector<uint8_t> _id;

   GUID()
     : _id(16)
   {
      std::generate(_id.begin(),_id.end(), std::rand);
   }

   friend bool operator ==( const GUID& g1, const GUID& g2 )
   {
      return std::equal( g1._id.begin(), g1._id.end(), g2._id.begin() );
   }

   friend bool operator !=( const GUID& g1, const GUID& g2 )
   {
      return !(g1 == g2);
   }
};

class SmartPointer
{
public:
   GUID guid;
   int refCount; // Incremented/decremented when things point or stop pointing to it.
   void* actualObject; // The actual data attached to the smart pointer.

   friend bool operator ==( const SmartPointer& p1, const SmartPointer& p2 )
   {
      // This may not be right for you, but good enough here
      return p1.guid == p2.guid;
   }
};

struct HashGUID
{
    std::size_t operator()( const GUID& guid ) const
    {
        // Do something better than this. As a starting point, see:
        //   http://en.wikipedia.org/wiki/Hash_function#Hash_function_algorithms
        return std::accumulate( guid._id.begin(), guid._id.end(), std::size_t(0) );
    }
};

int main()
{
   // Create the smart pointer object.
   SmartPointer sp1, sp2, sp3;

   assert( sp1.guid != sp2.guid );
   assert( sp1.guid != sp3.guid );
   assert( sp2.guid != sp3.guid );

   // Create a set of SmartPointers.
   std::unordered_map<GUID, SmartPointer, HashGUID> m;
   m[sp1.guid] = sp1;
   m[sp2.guid] = sp2;
   m[sp3.guid] = sp3;

   const GUID guid1 = sp1.guid;    
   const GUID guid2 = sp2.guid;    
   const GUID guid3 = sp3.guid;    

   // Need to find a SmartPointer based on a known GUID and not the pointer itself.
   auto found1 = m.find( guid1 );
   auto found2 = m.find( guid2 );   
   auto found3 = m.find( guid3 );   

   assert( found1 != m.end() );
   assert( found2 != m.end() );
   assert( found3 != m.end() );

   assert( found1->second == sp1 );
   assert( found2->second == sp2 );
   assert( found3->second == sp3 );
}

更新下面的 OP 评论

根据经验，如果您将原始指针存储在标准容器中，您可能做错了。如果您要存储智能指针的原始指针，则更是如此。引用计数指针的要点是所包含的指针（实际对象）不重复，而智能指针设备可以有许多副本浮动，每个副本对应于引用计数的一个增量，并且每个引用相同的包含对象。因此，您通常会看到类似std::unordered_set< std::shared_ptr<MyClass>, Hasher, Equality >.

如果您想为 SmartPointer 的所有实例设置一个 GUID，您可能希望 GUID 成为引用计数数据的（秘密）部分：

class SmartPointer
{
public:
   int refCount; // Incremented/decremented when things point or stop pointing to it.
   struct
   {
       GUID guid;
       void* actualObject; // The actual data attached to the smart pointer.
   } *refCountedData;
};

将 SmartPointer 与 std::unordered_set 一起使用，您将只有一份 GUID 副本，但由于所有散列机制都在 std::unordered_set 内部，因此您无权访问散列键。要通过 GUID 在集合中查找它，您需要进行手动搜索，这否定了散列的优势。

为了得到你想要的，我认为你要么需要定义自己的散列容器，让你更好地控制来自外部的散列，要么使用像侵入式引用计数 GUID 对象之类的东西，例如：

class GUID
{
public:
    typedef std::vector<std::uint8_t> ID;
    int refCount;
    ID* actualID;
    // ...
};

SmartPointer sp1, sp2;

std::unordered_map< GUID, SmartPointer > m;
m[ sp1.guid ] = sp1;
m[ sp2.guid ] = sp2;

在这种情况下，GUID actualID 只存在一个副本，尽管它是映射的键和映射中值的成员，但它的引用计数装置将存在多个副本。

在 64 位系统上，计数可能是 32 位，指针可能是 64 位，这意味着 GUID 对象的每个副本总共需要 12 个字节，每个实际 GUID 可以节省 4 个字节。使用 32 位计数器和指针，每个 GUID 将节省 8 字节，使用 64 位计数器和指针，它将占用与 GUID 数据相同的空间。前两个中的一个在您的应用程序/平台中可能值得，也可能不值得，但最后一个可能不值得。

如果是我，我只会复制 GUID 对象作为键，直到我知道它基于测量是不可接受的。然后我可以优化 GUID 对象的实现以在不影响用户代码的情况下进行内部引用计数。

于 2013-03-20T14:29:24.353 回答