0

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

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 个字符串比较似乎很多。

4

5 回答 5

2

为了摆脱 的O(log n)性能set，您可以使用unordered_setwhich 使用散列（和 is 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;
}

测试。

于 2013-02-23T14:24:03.850 回答
1

优化总是可能的，有时也非常值得，但对于 50,000 个条目，我猜它可能没有必要。假设它实际上是必要的，你可以尝试一些事情。

首先，如果某些词条比其他词条更常用，您可以将它们存储在单独的流行词词典中，您首先搜索该词典。要查看这是否值得，请针对每个字典条目存储一个计数器，每次访问条目时将其递增，并在长时间的测试期间查看这些计数器。

另一件值得拥有的是一个固定大小的字典数组，比如 26^3 = 17576，其中条目的前三个字母用于选择要搜索的字典。对于三个或更少字母的单词，这会将您降低到 o(1)，并大大减少您对剩余条目的搜索时间。

于 2013-02-23T14:08:24.673 回答
0

我可能只是使用std::set，可能将它的迭代器包装在一个检查失效的小类中，这样你就可以保留迭代器而不是指针。

不要过早优化。您是否分析了该代码？您是否 100% 确定这是瓶颈？

于 2013-02-23T13:50:21.710 回答
0

使用地图。您不必搜索您的数组/列表。

于 2013-02-23T13:50:24.870 回答
-1

std::hash_set 我想是要走的路

于 2013-02-23T13:52:43.207 回答