c++ - 用于快速名称查找的容器

Question

我想存储字符串并为每个字符串发出一个唯一的 ID 号（索引就可以了）。我只需要每个字符串的一份副本，并且需要快速查找。我经常检查表中是否存在字符串，以至于我注意到性能下降。什么是最好的容器，如果字符串存在，我如何查找？

Answer 1

我建议使用 tr1::unordered_map。它被实现为哈希图，因此它的查找复杂度为 O(1)，最坏情况为 O(n)。如果您的编译器不支持 tr1，那么还有一个 boost 实现。

#include <string>
#include <iostream>
#include <tr1/unordered_map>

using namespace std;

int main()
{
    tr1::unordered_map<string, int> table;

    table["One"] = 1;
    table["Two"] = 2;

    cout << "find(\"One\") == " << boolalpha << (table.find("One") != table.end()) << endl; 
    cout << "find(\"Three\") == " << boolalpha << (table.find("Three") != table.end()) << endl; 

    return 0;
}

Answer 2

试试这个：

_{(source: adrinael.net)}

Answer 3

试试 std::map。

Answer 4

首先，您必须能够量化您的选择。您还告诉我们，您感兴趣的主要使用模式是查找，而不是插入。

让N是您希望在表中具有的字符串数，并让C是所述表中存在的任何给定字符串（或根据表检查的字符串）中的平均字符数。

1. 在基于散列的方法的情况下，对于每次查找，您需要支付以下费用：

   • O(C)- 计算您要查找的字符串的哈希值
   • 在O(1 x C)和之间，您期望根据哈希键遍历存储桶的成本O(N x C)在哪里，这里乘以根据查找键重新检查每个字符串中的字符1..NC
   • 总时间：介于O(2 x C)和O((N + 1) x C)

2. 在std::map基于 - 的方法（使用红黑树）的情况下，对于每次查找，您需要支付以下费用：

   • 总时间：介于O(1 x C)和O(log(N) x C)- 其中O(log(N))是最大树遍历成本，并且O(C)是std::map通用less<>实现在树遍历期间重新检查查找键所需的时间

在大值的情况下N和没有保证小于 log(N) 冲突的哈希函数，或者如果你只是想安全地玩它，你最好使用基于树的 ( std::map) 方法。如果 N 很小，请务必使用基于散列的方法（同时仍确保散列冲突较低。）

但是，在做出任何决定之前，您还应该检查：

• http://meshula.net/wordpress/?p=183
• http://wyw.dcweb.cn/mstring.htm

Answer 5

听起来像数组在索引是数组索引的情况下工作得很好。要检查它是否存在，只需确保索引在数组的范围内并且其条目不为 NULL。

编辑：如果你对列表进行排序，你总是可以使用应该具有快速查找的二进制搜索。

编辑：另外，如果你想搜索一个字符串，你也可以使用 a std::map<std::string, int>。这应该有一些不错的查找速度。

Answer 6

要搜索的字符串是静态可用的吗？你可能想看看一个完美的散列函数

Answer 7

最简单的是使用 std::map。

它是这样工作的：

#include <map>
using namespace std;

...

   map<string, int> myContainer;
   myContainer["foo"] = 5; // map string "foo" to id 5
   // Now check if "foo" has been added to the container:
   if (myContainer.find("foo") != myContainer.end())
   {
       // Yes!
       cout << "The ID of foo is " << myContainer["foo"];
   }
   // Let's get "foo" out of it
   myContainer.erase("foo")

Answer 8

谷歌稀疏哈希可能