Trying Favorite Tries: Radix, Suffix, and Hash! Even Ternaries, oh my!

Question

So, I'm trying to pull together a collection of excellent datastructure implementations, partly for my personal collection, partly to try and build a larger set of highly optimized structures for somewhat specialized purposes. Part of this stems from the agony that deque and set inflicted with unexpected overheads and surprisingly painful deletion costs, respectively. Part of it stems from hackish curiosity.

However, I haven't been able to settle on a trie that I like, under a license that is permissive enough for potential commercial use. Ideally, I'd like some help finding a superb and exception safe suffix trie implementation in C++, and a similarly robust prefix trie. Bonus round includes a solid hashed trie.

In the interest of sharing, here's what I got so far:
Ned!
RLC Suffix Array

But I'm looking for more options.
If we get a few good ones, I'll hack up some benchmarking code too.

Answer 1

You can try also my TommyDS library at http://tommyds.sourceforge.net/

It contains both hashtables and tries.

I also did an extensive benchmarks comparing it with the major competitors, with very interesting results. See the benchmarks page on the site.