Boost logo

Boost :

Subject: Re: [boost] [GSOC] proposal for Trie
From: Antony Polukhin (antoshkka_at_[hidden])
Date: 2013-04-23 08:59:01

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:

Best regards,
Antony Polukhin

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