1

我的目标是进行字符串实习。为此，我正在寻找一个可以执行以下操作的散列容器类：

  • 每个节点只分配一块内存
  • 每个节点不同的用户数据大小

值类型如下所示：

struct String
{
    size_t refcnt;
    size_t len;
    char data[];
};

每个 String 对象都有不同的大小。这将通过 operator new + Placement new 来完成。所以基本上我想自己分配Node，稍后再推入容器中。

以下容器不适合：

  • std::unordored_set

  • boost::multi_index::*

    无法分配不同大小的节点

  • boost::intrusive::unordered_set

    一开始似乎有效。但有一些缺点。首先，您必须自己分配存储桶数组并维护负载因子。这只是不必要且容易出错。

    但另一个问题更难解决：您只能搜索具有 String 类型的对象。但是每次查找条目时分配一个字符串效率低下，并且您只有一个 std::string 作为输入。

是否有任何其他散列容器可用于此任务？

4

2 回答 2

0

您的定义String不会在 C++ 中编译；显而易见的解决方案是data用指针替换字段（在这种情况下，您可以将结构本身放入 中 std::unordered_set）。

可以在 C++ 中创建一个开放式结构，如下所示：

struct String
{
    int refcnt;
    int len;
    char* data()
    {
        return reinterpret_cast<char*>(this + 1);
    }
};

但是，如果您这样做，您就是在薄冰上滑冰。对于 以外的类型char，存在this +无法适当对齐的风险。

如果你这样做，那么你std::unordered_set将不得不包含指针，而不是元素，所以我怀疑你会为此付出任何努力。

于 2012-12-04T11:36:37.253 回答
0

我认为您无法使用任何标准容器来做到这一点。

您可以做的是存储指针String并提供自定义哈希和 cmp 函子

struct StringHash
{
   size_t operator() (String* str)
  {
    // calc hash
  } 
};

struct StringCmp
{
   bool operator() (String* str1, String* str2)
  {
    // compare
  } 
};

std::unordered_set<String*, StringHash, StringCmp> my_set;
于 2012-12-04T10:52:01.513 回答