Re: [boost] [Boost][GSOC] proposal for Trie

On 4/23/2013 7:59 AM, Antony Polukhin wrote:

2013/4/23 Hardy :

...

"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 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.