Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at