Map implementation of Trie

Question

An easy way to implement the Trie data structure is to use std::map<char,*NodeTrie> . What could happen wrong if I use this. I need to serialize and deserialize Trie. Thus, each map in a node is an AVL tree. Maybe I have overhead? But on the map, I can search faster if I use a list.

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

Answer 1

I like your idea. Errors are important data structures, and I had a pleasant experience working with <> s cards as efficient containers.

Just some notes: if your compiler supports it, you can avoid memory loss with a separate allocation for each node.

 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; }; 

To use this method:

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

I also changed the val element to become a construct for copying: using the link here seems to be the wrong design for me ...

Answer 2

Just FYI, GNU libC ++ has the trie template already in its policy-based data library. You can use it like:

 #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; 

For some examples of using this class, you can refer to this .