Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Cosmin Boaca (boost.cosmin.boaca_at_[hidden])
Date: 2015-02-22 12:29:30

Hello,

> As a temporary workaround operator*() could return pair<const std::vector<Key>,
Value& > by value.

Operator*() works fine and is already returning that, the problem is with
operator->. Also, I don't know what do you mean when you tell me to return
it by value.

Thank you,
Cosmin

On 22 February 2015 at 18:58, Antony Polukhin <antoshkka_at_[hidden]> wrote:

> 2015-02-22 16:23 GMT+03:00 Cosmin Boaca <boost.cosmin.boaca_at_[hidden]>:
>
> > Hello,
> >
> > I have performed the modifications required in order to use
> > std::reverse_iterator instead of trie_iterator. [0]. Also, I have
> optimized
> > the get_key function [1]. The overall diff can be found here [2]. Please
> > give me some feedback about the code when you have time.
> >
>
> Good, added a few minor comments.
>
>
> >
> > Also, it seems to be a problem with trie_iterator::operator->. It doesn't
> > work and I think it may cause memory corruption. I think the problem is
> > that it returns &(operator *()) which is a value allocated on stack that
> > gets destroyed when it goes out of scope. However, I don't know how it
> > should be implemented. Please tell me what do you think about this
> > operator. As a workaround, instead of using this operator I have used
> > operator * and the code passes the tests.
>
>
> As a temporary workaround operator*() could return pair<const
> std::vector<Key>, Value& > by value.
>
> Ideal hard to implement solution would be to use Boost intrusive's slist or
> develop own slist and use slist in node and instead of std::vector:
>
> // pseudocode
> template <class Key>
> class slist: public slist_base_hook<> {
>   slist* parent_;
>   Key key_;
>
>   slist_iterator begin() { return this; }
>   slist_iterator end() { return 0; }
>   // ...
>
>   std::vector<Key> to_vector() {
>     std::vector<Key> key_path;
>     key_path.reserve(this->size());
>
>     std::copy(this->begin(), this->end(), std::back_inserter(key_path));
>
>     return key_path;
>   }
> };
>
> template <class Key, class Value>
> class node: public pair<const slist<const Key>, Value> {};
>
> class trie_iterator {
>     node* vnode;
>
>     reference operator*() { return static_cast<pair<const slist<const Key>,
> Value>>(*vnode); }
> }
>
>
> But this can wait...
> Simple task: trie_iterator accepts 4 template parameters, while Key and
> Value types seem enough. Try to remove two template parameters, take care
> of almost identical iterator_type and iter_type typedefs,
>
> --
> Best regards,
> Antony Polukhin
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>