[Qi][Symbols][TST] A more STL-compliant ternary search tree implementation?

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hello folks,

  As I'm sure most of you know, qi::symbols is typically backed by a
ternary search tree implemented by Joel Guzman and hkaiser (e.g.
boost::spirit::qi::tst<Char, T>).

  Recently, I've had a need for an associative container with tst's
performance traits and STL-esque interface. qi::tst performs superbly in
it's role, and I believe that with some clever hacking it could give
birth to a general purpose tst structure that fulfills the Associative
Container concepts.

  I spent some time today working on this, and I'm about halfway done
implementing what I had in mind. A portion of the work is boilerplate
code (e.g., STL typedefs and what not). Implementing size() was pretty
easy as the underlying tst_node objects use allocator methods on the tst
container.

  Additionally, I modified tst to take an allocator template parameter,
added an instance of that template parameter as a data member, and
rewrote the tst allocator methods to use the user-supplied allocator.

  The aforementioned changes are a nice prelude to my planned
implementation of iterators for the tst. This problem has irked me for
quite awhile, but I now realize that the memory allocation pattern used
by the tst will make the addition of iterators possible, without
significantly affecting performance.

  As I mentioned, the implementation of the ternary search tree,
tst_node, uses the tst interface to allocate and deallocate. If tst
controls the allocation, then iterators can be implemented without
touching tst_node by using a memory pool of some sort in tst.

  Thoughts? I'm thinking about using Boost.Pool, but I have heard that
it has performance issues (I've used it before, and it seems to be
alright). It might not be suited to this, though. I'd appreciate some
feedback regarding possible pool implementations.

- --
Bryce Lelbach, aka wash
http://groups.google.com/group/ariel_devel
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkyhkYsACgkQO/fqqIuE2t4oWgCffQwpYYH0xmpHfyxLI7vFhfND
sIkAn3Ep5qDW1HCocV6ie7nh/03aIOHJ
=awDH
-----END PGP SIGNATURE-----

------------------------------------------------------------------------------
Start uncovering the many advantages of virtual appliances
and start using them to simplify application deployment and
accelerate your shift to cloud computing.
http://p.sf.net/sfu/novell-sfdev2dev