c++ - 使用 map 实现Trie

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

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

最佳答案

我喜欢你的主意尝试是重要的数据结构，我对map 作为有效容器有愉快的经验。

请注意以下几点:如果编译器支持，则可以避免为每个节点分配单独的内存，从而浪费内存。

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成员更改为可复制构造的对象:在这里使用引用对我来说似乎是错误的设计...