Re: [boost] [GSOC] proposal for Trie

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:
> http://www.boost.org/doc/libs/1_53_0/doc/html/container/other_features.html
>

You should be able to meet at least the requirements of Container.

http://en.cppreference.com/w/cpp/concept/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.