In this article Adam introduces a very sophisticated and useful data structure for string processing, while at the same time revealing some interesting features of C++.

http://www.artima.com/cppsource/catenator.html

ok, it *seems* to be a tree -- a multiway tree, or some variant -- with a particular search. right? can these two layers of structure be separated: general tree + manipulator/reader? and also have that visitor/manipulator polymorphic instead of template -- possible to share general tree with multiple visitors. in fact, here is an example! -- http://www.hxa7241.org/articles/content/octree-general-cpp_hxa7241_2005.html . if not, how is the manipulation bonded to the tree-ness?

and how is ap/pre-pending really different from insertion at the end?

(if method definitions are inside the class definition they get inlined, don't they?, which is usually probably not a good idea.)

I believe that in the first example in the article (the crossword clue-solving algorithm), the second for loop should read:
j < csyns->size();
instead of
j < csyns.size();

There are many problems where the best solution is to adapt either a generic tree you previously created yourself (such as the link to your own code you give as an example) or, I would suggest, the Boost graph library: http://www.boost.org/libs/graph/doc/index.html. However, this isn't one of them.

You mention appending/insertion at the end. This is an example of an invariant that profoundly affects both the data structure and the algorithms that use it. You couldn't just slot in your own algorithms for this data structure using the visitor pattern, for instance, without risking this and other invariants. Take the search routines. They rely on the properties of the data structure. You might want to modify their behaviour through the templates provided, but the algorithm itself is tied intimately to the data structure.

What I think is more interesting is the 'skin' that you put on top of your creation, manipulation and search routines: what they are called and how you use them. This is where there is some separation between layers. It leads to the structural conformance issues that I discuss in the text.

Other issues:
Could you use polymorphism instead of templates?
Yes, but why would you want to?

Are method defns inlined if inside class defn?
Not necessarily. If you feel strongly about this, you can generally prevent your compiler from doing it.

Is this usually not a good idea?
No, it usually is a good idea. But you should test whether it helps or not on a case-by-case basis.

> I believe that in the first example in the article (the
> crossword clue-solving algorithm), the second for loop
> should read:
> j < csyns->size();
> instead of
> j < csyns.size();

Thanks for pointing this out. I will arrange for it to be changed.

> but why would you want to? (use polymorphism)

Lots of templates (and inlining too) can increase the compiled code size a fair amount. Smaller programs draw less resources.

Depending on the compiler, specialising on the manipulation might generate a whole class for each, whereas polymorphism has different code generated only where the behaviour is different.

This was a rough guide for choosing a means for generalisation. Templates for when behaviour is the same, polymorphism when behaviour is different. I think from Stroustrup or Meyers. There are more uses for templates, but that distinction often makes sense.

Another cause for polymorphism over templates is that code, and concepts, translate easier between languages. Rather marginal of course, but somewhat reassuring. (Although getting some templates working between different compilers certainly can be a substantial matter.)

But maybe polymorphism in C++ is old-fashioned (and I with it), as everyone seems to do everything with templates now...