Subject: Re: [boost] [ boost ] [ Trie ]
From: Cosmin Boaca (boost.cosmin.boaca_at_[hidden])
Date: 2015-03-04 18:55:36
I have modified the directory strucure. I think it's ok right now.
> 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
> 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
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<key, int>, 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
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk