c++ - String-Interning 使用哪个容器

Question

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

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

值类型如下所示:

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

每个字符串对象都有不同的大小。这将通过 运算符新 + 放置新。 所以基本上我想自己分配节点并稍后将其推送到容器中。

以下容器不适合:

• std::unordored_set

• boost::multi_index::*

  不能分配不同大小的节点

• boost::intrusive::unordered_set

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

  但是另一个问题更难解决:你只能搜索具有 类型字符串。但是每次查找条目时都分配一个 String 是低效的 你只有一个 std::string 作为输入。

是否有任何其他哈希容器可用于此任务？

Answer 1

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

您可以做的是将指针存储到 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;