Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-02-21 12:46:45

2015-02-20 23:17 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:

> 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<Key, Value> 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<const std::vector<Key>, Value>. 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