使用地图的Trie实现

实现Trie数据结构的简单方法是使用std::map<char,*NodeTrie>。如果我使用它，会发生什么错误。我需要序列化和反序列化Trie。所以节点中的每个映射都是AVL树。也许我会有开销？但在地图上我可以更快地搜索，如果我使用列表。使用地图的Trie实现

template < typename T > 
struct NodeTrie{ 
    std::map<char,*NodeTrie>` 
    bool isWord; 
    T & val; 
};

来源

2013-08-30 YYY

你有一些类似于hashmap的数据结构吗？你可以使用它来减少开销。或者如果没有，那么考虑将char映射到更易于管理的东西 – dchhetri

我需要完全Trie，用于词汇搜索。 – YYY

而不是使用std :: map使用std :: unordered_map或类似于内部的东西。这就是我所建议的 – dchhetri

我喜欢你的想法。尝试是重要的数据结构，我有愉快的经验与地图<> s作为有效的容器。

只是一些说法：如果您的编译器支持它，您可以避免为每个节点分别分配内存。

template< typename T > 
struct NodeTrie { 
    NodeTrie(const T& val = T(), bool isWord = bool()) : val(val), isWord(isWord) {} 

    std::map<char, NodeTrie> span; 
    T val; 
    bool isWord; 
};

要这样使用：

int main() { 
    typedef NodeTrie<int> iTree; 
    iTree t(0); 
    t.span['a'] = iTree(3); 
    ... 
}

我也改变了val成员成为一个可复制构造的对象：这里使用的参考似乎是错误的设计给我...

来源

2013-08-30 17:58:28 CapelliC

刚仅供参考，GNU libC++在其基于策略的数据结构库中已经有一个trie模板。您可以使用它像：

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/trie_policy.hpp> 
using namespace std; 
using namespace pb_ds; 

trie <string, int> myTrie;

对于一些例子中使用这个类，你可以参考this。

来源

2013-08-30 18:09:12

使用地图的Trie实现

回答

相关问题