Subject: Re: [boost] [GSOC] proposal for Trie
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2013-04-23 12:26:00
On 4/23/2013 7:59 AM, Antony Polukhin wrote:
> 2013/4/23 Hardy <hzithlony_at_[hidden]>:
>> "A good addition to proposal will be some sketch of trie interface:
>> methods and constructors that Trie class will contain."
>> Could you give me some examples or more advices on that?
>> What I think out now are something like STL set, map, and with some specific
>> methods and variables of Trie.
> You are right, it is better to be as close to STL interface as
> possible. You may also say something like:
> Trie interface will have all the typedefs and methods of std::set excluding:
> iterator insert (const_iterator position, const value_type& val);
> It will additionally have the following methods:
> pair<const_iterator,const_iterator> prefix_range (const value_type&
> prefix) const; - returns range of elements starting from `prefix`.
> You may also add some notes that you think will be interesting or just
> affect design, like "trie implementation will be storing it's size as
> a separate field to allow getting size in constant time" or "won't be
> storing it's size leading to liner complexity of size() function"...
> Some more examples of containers features:
You should be able to meet at least the requirements of Container.
Other than that it depends. I think a trie is usually an associative
container I'm not sure if it is ordered.
If you can directly fit a more refined C++ container concept many more
algorithms will just work for it.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk