c++ - 高效的字符串字典

Question

我有一个数据结构问题。我有一个字符串集合，它在整个过程的生命周期中不断增长。我希望能够以不同的持续时间在程序周围传递对这些字符串的引用。我不想向集合中添加重复项，所以当我传入一个时，我希望返回对现有条目的引用，因此:

const std::string& add_new_entry(const std::string&)
{
    // Check if string exists
    // Return reference if it does
    // Otherwise add to collection
    // Return reference to it
}

最天真的实现是一个字符串列表和每次调用 std::find，但我不禁觉得这不是最理想的，特别是因为我正在向上处理50,000 个字符串。我创建了一个扩展数组容器，因此我可以任意添加元素而无需强制调整大小和移动，并且我使用 std::set 的 std::string*< 对它们进行索引 使用取消引用比较谓词按字母顺序排列:还有人能做得更好吗？ 15 次字符串比较似乎很多。

Answer 1

摆脱O(log n) set的性能, 你可以使用 unordered_set 它使用散列(并且是 O(1) )(或 hash_set 本质上相同，但仅受某些编译器支持)。

鉴于您正在进行(最多)15 次字符串比较，您不会一直达到这个最大值，并且其中许多只能比较一个或两个字符，很有可能为 unordered_set 生成哈希(并处理哈希冲突)比在 set 中查找值花费的时间更长.

此外，为什么不去掉数组而只使用 std::set<std::string>反而？你仍然可以返回一个引用:

const string& add_new_entry(const string& str)
{
    set<string>::iterator iter = yourSet.find(str);
    if (iter == yourSet.end())
      return *yourSet.insert(str).first;
    return *iter;
}

Test .