Glo*_*ior 7 c++ algorithm map trie data-structures
尝试是非常快速的数据结构.查找单词需要O(sizeofword)时间,而std::maps是自我balacing树.为什么不使用try实现标准C++映射模板.有什么具体原因吗？是否有使用trie而不是自平衡树的权衡？
tem*_*def 24
只有当要存储的密钥可以逐位或逐字符处理时,才能使用尝试.C++ std::map和std::set设计用于与任何可比较的元素作为键,因此不能以逐字符处理键的方式实现.它们(通常)使用平衡的二叉搜索树,它不需要对键进行内省,而只需使用比较器来进行快速查找.
如果您确定某些属性适用于您的密钥,则在某些情况下您可以比尝试更好(请参阅van Emde Boas树中的示例).但是,库设计人员必须针对大量用例进行设计,因此可能需要选择比绝对最佳选项慢的选项,因为他们需要处理尽可能多的选项.
此外,实际上完全可能的是,符合标准的C++实现包含特征std::map或std::set在键是字符串时使用特里结构.我不相信任何做,但理论上是可能的.
希望这可以帮助!