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.
+1
I have done this task. Also I have done refactoring and cleanup on the
whole project. I have decided to change a couple of things:
1. I have removed all the methods from trie class that created / destroyed
nodes. I have replaced them with calls to new and delete.
2. I have removed the node_allocator / value_allocator from trie class. I
think something like a node factory that would handle only creation /
destruction of nodes is more appropriate if we plan to allow custom
allocators.
3. I have added some methods to the trie_node class in order to share a
common interface between template specializations. Now operations that
query the node internal state (adding / removing values / no_value()) is
now done using those methods.
4. Because the iterator needed to be specialized too in order to handle
trie_node specialization I have decided to delegate the erasure of the
iterator to the iterator itself. This was the only way that could handle
the strucutral difference in terms of members between the specializations.
5. The iterator class now has another template parameter called Enable. I
needed to specialize the iterator for both void / const void and i used
boost::enable_if in order to achieve this with less code. const void
specialization is needed too because of the erase methods from trie. In
trie class there are two erase methods, erase(iterator),
erase(const_iterator). The const iterator coresonding for iterator