Re: [boost] [ boost ] [ Trie ]

Subject: Re: [boost] [ boost ] [ Trie ]
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2015-02-22 11:58:06

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