具有最快 "Exists"查找的 C++ 容器( vector/数组/等)

Question

我不确定这里使用的最佳 C++ 数据容器....我正在构建一个对延迟非常敏感的应用程序(因此我需要绝对最快的实现)。

我需要一次性存储大约 300,000 个字符串(仅一次写入)，然后经常检查某个元素是否存在于该数据存储中(多次读取)。除了检查其中是否存在值外，我不需要对这个数据集做任何其他事情，而且我需要每秒检查数百次。如果重要的话，大多数查找将导致找不到 key 。

我考虑过使用 vector 或数组，但它们似乎都只是简单地扫描整个列表并一对一地检查值......这会起作用......但由于我们正在索引字符串，不是没有任何数据容器为值构建某种树索引，所以当搜索值“apple”时，它将首先查看以“a”开头的键，然后是下一个字符“p”，然后它没有找到任何“ap ...”，它立即返回未找到。对我来说，这似乎比每次都搜索整个海量集合要快。我真的希望 native 容器具有这种功能。

如果有帮助的话，这个项目确实编译了 Boost。

非常感谢!

Answer 1

有了 Boost，答案显然是 boost::unordered_set .

它也作为 C++11 标准的一部分作为 std::unordered_set 提供。在 <unordered_set> .

它们都建立在哈希表上，因此一旦计算出哈希，查找本身的复杂度为 O(1)。