用于快速查找名称的容器

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

试试这个:

_{(来源:adrinael.net)}

Answer 3

试试std :: map.