Re: [boost] [ boost ] [ Trie ]

Another significant and hard task: trie_node structure looks too heavy: there are too many member variables. Try to simplify trie_node and value_list_node structures. Think of a possible optimizations of the trie_node structure for

Hello, I have modified the directory strucure. I think it's ok right now. trie_set|trie_map|trie_multiset|trie_multimap.

For example all the sets do not require values, so pointers to value list nodes can be removed from trie_set in that case.

I have thought of this task too. I will share with you some ideas in order to get some feedback about them. 1. Value = void specialization for trie_node which would remove pointers to value_list_head/tail, self_value_count. 2. Another specialization or something like this would be ok for trie_map also. The map_node should only contain a member value_type value. value_list_head/tail, self_value_count should be removed in this case to but I don't know how to specialize the template (for which key, value) type. 3. Considering 2, trie_multiset could be easily implemented in terms of trie_map, maybe using private inheritance. The int would keep track of the frequency of the key prefix. 4. value_count could be completely removed but this would greatly reduce the performance of count_prefix function. In my opinion this shouldn't be removed. I don't know too much about pred_node, next_node, and the child_iter_of_parrent. I need to take some more time to look at those things to see if any of them could be removed. I see that pred_node and next_node are used in trie_iterator and child_iter_of_parrent is used to maintain the values of pred_node and next_node. However, I don't know which would be the tradeofs of the removal for each of them. Looking forward to your feedback about the ideas above. Thank you, Cosmin