{"id":51,"date":"2011-05-18T21:10:10","date_gmt":"2011-05-19T01:10:10","guid":{"rendered":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/?p=51"},"modified":"2011-10-02T00:00:19","modified_gmt":"2011-10-02T04:00:19","slug":"the-curiously-recurring-template-pattern","status":"publish","type":"post","link":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/2011\/05\/18\/the-curiously-recurring-template-pattern\/","title":{"rendered":"The curiously recurring template pattern"},"content":{"rendered":"

Related to my previous post on expressive engine design<\/a>, I found myself using the curiously recurring template pattern (CRTP) today. I say related because I believe the CRTP to be one of those beautiful and expressive templates out there in the c++ world.
\n<\/p>\n

I’ve been doing a fair bit of thought lately (literally days worth) trying to come up with a good general scenegraph structure and what kinds of relationships I want to have. One of the things I likely (obviously) need is a tree structure of nodes. Let’s work through the requirements.
\n– tree structure to walk through
\n– need to be able to attach child nodes
\n– need to be able to push values up the tree (like dirty flags)
\n– want things to be fast of course
\n– not likely that I’ll need random access, simple straight through walks are good.<\/p>\n

First solution to pop into mind is to just use the typical tree structure and add in nodes. But that doesn’t work with pushing values up the tree cause each node has to knowledge of the tree. Next idea is for each renderable node to be a node in the tree, with a parent and a link to the first child so there’s a linked list of children. Wait that means a node must know about their siblings and that doesn’t quite seem right (plus this actually gives a bit of a weird walk for later and not exactly consistent dependency access to other nodes). But I want to use the nodes as a linked list to save on memory (ie no predeclared vector arrays), and cause I only needed a straight through walk, and can get quick access to add (but remove will be slow). So we’re close. Let’s try just giving each node the linked list of the children instead of making the children the linked list. Very important difference here. Well this works now cause it’s more like a down-up walk through each child to push and pop stacks (you could do the same before, but seems a bit weirder), and everyone has the same access to parents and children as you walk through.<\/p>\n

So that was the plan, make the Renderable a tree node and give it parents and children directly. I start coding and very quickly realize I don’t like the fact that my Renderable now has this tree structure code directly in the class when it’s really a different concept. Yes the Renderable IS a tree node but the TreeNode is really a separate component that should be maintained separately instead if possible. Again, this goes along with my beliefs about engines being expressive and lots of separate components should get strung together.<\/p>\n

Now we want to keep all tree related stuff in TreeNode, so we must have to add this as a member or parent class. Well if we add it as a member variable then a Renderable doesn’t really have the IS-A relationship with the TreeNode, it’s more of a HAS-A relationship. That means parent class. Uhoh, that means a TreeNode must have pointers to other TreeNodes rather than a subclass.<\/p>\n

Enter the curiously recurring template pattern. With this pattern you subclass from a template based on the subclass type. Huh? OK let me show you some code instead, cause it’s probably easier to understand.<\/p>\n

template <typename T>
\nclass TreeNode {
\nprotected:
\nT* parent;
\nstd::list<T*> children;
\n...
\n};<\/p>\n

class Renderable : public TreeNode<Renderable> {
\n...
\n};<\/code><\/p>\n

Yep that actually compiles and gives you exactly what’s needed here. The TreeNode implementation is kept separate, Renderable’s implementation doesn’t really have any kludges in it and you still have direct access to parent<\/code> and children<\/code>, and the types on your tree nodes are Renderable. Bonus: that TreeNode class is looking pretty general and it’s a template so it can likely be used over again somewhere else. Now that is some expressive code!<\/p>\n

I actually highly suggest you read up more on this pattern cause I haven’t really even used much of the even cooler stuff you can do with it, like compile time class polymorphism without virtuals. I love telling those pure c-ists that think vtables add too much slowdown from lookups that you can still get polymorphic abilities without sacrificing their precious time to look up a function pointer. I swear their heads blow up!<\/p>\n","protected":false},"excerpt":{"rendered":"

Related to my previous post on expressive engine design, I found myself using the curiously recurring template pattern (CRTP) today. I say related because I believe the CRTP to be one of those beautiful and expressive templates out there in the c++ world.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":17,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/posts\/51\/revisions"}],"predecessor-version":[{"id":130,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/posts\/51\/revisions\/130"}],"wp:attachment":[{"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/media?parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/categories?post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/GetOffMyLawnEntertainment.com\/blog\/wp-json\/wp\/v2\/tags?post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}