Boost logo

Geometry :

Subject: [ggl] spacial index construction interface
From: Bruno Lalande (bruno.lalande)
Date: 2011-03-08 04:50:46


> 1. Full run-time polimorphism.

This is the classic way, and the technique I was proposing allows to keep
going that way along with playing with child-class-specific functions... see

> 2. One virtual function is_leaf()

This should really be avoided as much as possible. Type testing is the most
common antipattern is dynamic polymorphism, for known reasons.

I should have been clearer in my previous email about double-dispatch. First
just to clarify, this has nothing to do with tag dispatching. It's a
dynamic, runtime mechanism. Second, the specific application of multiple
dispatching I was talking about was the Visitor pattern. Typically in your
program you will need to traverse your tree, doing different things
depending on whether you are on a node or a leaf, potentially calling
specific non virtual functions on them. Visitor allows a class to visit each
instance of a class hierarchy and do specific things of each specific class
of that hierarchy. The design you are describing is clearly a Composite
pattern, and if I refer to the schema at the end of the GoF book showing how
patterns relate to each other, there's a "adding operations" relation from
Composite to Visitor. I fully agree with that view: the standard way to add
operations (algorithms, whatever you call that) on a composite structure is
to use a Visitor. We should really try to stick to that before going

> 3. No virtuals. Unused data.

That's the other solution I had described, but only possible if your node
and leaf classes have no specific operation. Is that the case? (my
understanding was that no)

Besides that, the pros and cons I can see are:
- Pro: faster. Testing for vector<T>::empty() is faster than a v-table
- Cons: space in memory. An empty vector<T> is larger than a v-table (in my
GCC: 24 bytes vs 7 bytes). BUT the internal nodes will necessarily be
smaller (because in the virtual approach they have both a vector AND a
v-table). So it mostly depends on the proportion of nodes vs leaves in the

Let me be clear: I am NOT asking you to avoid virtuality (Visitor is all
about virtuality). Just asking to use it properly by going for the
"state-of-the-art" way about manipulating composite structures, and to avoid
making virtual some functions which are only supposed to live in one
specific child class.

Another possible way is to use Boost::Variant and its static_visitor (didn't
study that in depth though, and I don't remember the details).

-------------- next part --------------
An HTML attachment was scrubbed...

Geometry list run by mateusz at