Boost logo

Boost :

Subject: Re: [boost] Prefix Trie
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-01-15 06:42:26

On 14 Jan 2014 at 17:04, Michael Conlen wrote:

> I recently discovered that there seems to be a lack of good Prefix Tries
> in C++. There are many basic ones and I think a C implementation ran all
> of 12 lines of code, but something with a nice interface and iterator
> seemed lacking. (Stop me if I'm missing something here)

GSoC 2013 implemented a Prefix Trie container. I was one of the
mentors. AFAIK it was not peer review ready last time I looked.

> So I'm interested in developing Prefix (and possibly a Radix) Trie
> containers in C++. I could see a use for both sequence and map
> containers; however this would be a learning experience for me. If
> there's interest in such a creature I'm happy to go through the review
> process as necessary.
> Having said that, is there interest in having such a library and if so
> what are the pointers on what would be expected (particularly any
> boost-isms)?

Almost certainly you want to implement it via Boost.Intrusive, and
from there into a concrete STL type implementation.

I would not underestimate the difficulty of getting an implementation
up to peer review quality.

Still, if you're game, you'll get a lot of moral support here. You're
right that C++ needs that container, it's one of the final classes of
STL container C++ is still missing.


Currently unemployed and looking for work.
Work Portfolio:

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