The Artima Developer Community
Sponsored Link

Articles Forum
Introducing the Catenator

5 replies on 1 page. Most recent reply: Sep 30, 2005 1:00 PM by Chuck Allison

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 5 replies on 1 page
Chuck Allison

Posts: 63
Nickname: cda
Registered: Feb, 2003

Introducing the Catenator Posted: Sep 30, 2005 1:00 PM
Reply to this message Reply
Advertisement
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


Harrison Ainsworth

Posts: 57
Nickname: hxa7241
Registered: Apr, 2005

Re: Introducing The Catenator Posted: Oct 1, 2005 11:33 AM
Reply to this message Reply
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.)

Amit Schreiber

Posts: 1
Nickname: gnobal
Registered: Dec, 2003

Re: Introducing The Catenator Posted: Oct 1, 2005 10:41 PM
Reply to this message Reply
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();

Adam Sanitt

Posts: 2
Nickname: adamsanitt
Registered: Oct, 2005

Re: Introducing The Catenator Posted: Oct 3, 2005 1:20 AM
Reply to this message Reply
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.

Adam Sanitt

Posts: 2
Nickname: adamsanitt
Registered: Oct, 2005

Re: Introducing The Catenator Posted: Oct 3, 2005 1:21 AM
Reply to this message Reply
> 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.

Harrison Ainsworth

Posts: 57
Nickname: hxa7241
Registered: Apr, 2005

polymorphism, rather than templating Posted: Oct 3, 2005 8:43 AM
Reply to this message Reply
> 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...

Flat View: This topic has 5 replies on 1 page
Topic: Modern C++ Style Previous Topic   Next Topic Topic: As Simple As Possible?

Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use