Re: [boost] [ boost ] [ Trie ]

2015-02-20 23:17 GMT+03:00 Cosmin Boaca :

Hello,

I have two observations about the removal of the reverse_iterator.

The trie_reverse_iterator has a methd get_key() which calls the get_key() method from the base iterator. If std::reverse_iterator is used then this method can't be accessed anymore. If I remove it there is no way to retrieve the key of a specific object.

Also, the trie_iterator doesn't act like a standard STL iterator over a mapped data structure. Those iterators return a pair when they're derefferenced. trie_iterator returns only Value.

In order to address the things I have mentioned above, I am thinking at changing the operators *, and -> from the trie_iterator to return pair. Also, I think about adding a new member into the trie_iterator class, named current_path, which would represent the current path in the Trie from the root to the node which the iterator is pointing to. By doing so, std::reverse_iterator can be used instead of trie_reverse_iterator and also the key associated with the current node can be retrieved in better running time.

I would like to know your oppinion about the changes I am proposing.

Good points with reverse_iterator. Returning pair<> is STL like, which is good. I'm just not sure what the first template parameter must be, but std::vector<Key> is OK for first time. current_path looks like an overkill. Iterators must be small and simple to copy, I'd recommend to optimize get_key() instead: * make pass to the tree root, counting elements * resize vector to counted elements count * make one more pass to the root, filling vector from the end with values This algo will reduce memory allocations count and memory consumption. -- Best regards, Antony Polukhin