C++中用于在字典中查找字符串的最佳数据结构

Question

我是C++的初学者.有人可以告诉我C++中最好的数据结构,将所有单词存储在字典中,并查找字典中是否存在单词.我知道哈希表是最好的,但我不知道哪个数据结构使用它们？

非常感谢你提前.

Answer 1

您的C++实现的标准库可能有unordered_set或hash_set.它们基本上是一回事; 前者是即将推出的C++ 0x标准的一部分,并得到一些最新编译器的支持,后者来自最初的SGI STL,并包含在许多标准库实现中.

Answer 2

哈希非常好，但最好的结构是trie。你可以从<ext/pb_ds/assoc_container.hpp>GCC 中得到一个尝试。请参阅在线参考。

#include <ext/pb_ds/assoc_container.hpp>
#include <string>
#include <iostream>

int main() {
        pb_ds::trie< std::string, int > dict;

        dict.insert( std::make_pair( "hello", 3 ) );

        std::cerr << ( dict.find( "hello" ) != dict.end() ) << std::endl;
        std::cerr << ( dict.find( "goodbye" ) != dict.end() ) << std::endl;
}

仅提供map类似功能，而不是纯set。在上面的示例中，我添加了一个虚拟对象int作为要映射到的数据......它应该不会受到太大伤害。

伤害的是这在 GCC 之外是行不通的。

另一方面，非标准哈希表（不是std::或ext::任何）将允许您只找到近似匹配，即在单词的校验和中搜索而不是单词本身。那将是最快、最紧凑的解决方案。基于Bloom 过滤器的词典可以在几千字节中包含数千个单词。