Re: [boost] Re: [BGL] MutablePropertyGraph questions

From: Emily Winch (boost_at_[hidden])
Date: 2003-02-03 12:18:32

On Sun, 2003-02-02 at 22:37, Chris Russell wrote:

> Hi Emily, I just read your paper and think it's excellent. A while ago (some
> months past), I think I hacked together a solution to a similar problem and
> made a mental note to post it into the Wiki for analysis by folks who really
> know what they're doing at some point in the future. You post (sorry I was
> not previously following this thread) brings this back to my attention.
> 
> I'm not sure I completely understand your approach (my ignorance). Would you
> please clarify these points for me:
> 
> Your heterogeneous list mechanism employs custom containers that look like
> STL containers? Or can you actually use STL containers? Algorithms must be
> written custom and your paper explains how. Is this correct? Or am I missing
> something?

Yes. I wrote an associative_list class that looks like a heterogenous
STL multimap. It's type-safe in that trying to retrieve the wrong type
results in a compile-time error. Yes, custom algorithms are required,
and the paper explains how. The intent is for several algorithms to be
provided with the associative_list, and these algorithms would also work
on a hypothetical tuple_iterator, or on iterators into any similar
container, for example, a heterogenous set.

> Let me first describe my heterogeneous container hack and perhaps you could
> point why it's poor (your feel better on a quick read of your paper and this
> is a good way to help us all understand this a bit better).
> 
> My goal was to be able to use standard STL containers and iterators with
> heterogeneous collections of objects. My hack was to declare a class
> CMoniker that takes a pointer to some CMonikerBase-derived class through a
> templated constructor. This constructor does two things: it casts the
> pointer to a void * and stores it in a private member. Additionally it uses
> RTTI to record the type. CMonikerBase is invasive; it provides reference
> counting for the object and operator overloads for STL containers. Any class
> that derives from CMonikerBase can then be stuffed into a CMoniker, and I
> then use the standard STL containers/iterators to work with homogenous
> collections. A CMoniker has a templated operator: template <typename Type>
> operator Type&() that internally uses RTTI to test Type and throw an
> exception if it doesn't match the internal type squirreled away in the
> constructor. Ugly - yes. The filtering operation you propose in your paper
> is similar to little helper classes I write to enumerate elements in my
> some_stl_container<CMoniker> to produce another container full of objects of
> a given type - again this is inelegant but it does seem to work.

As someone already pointed out, this is quite similar to Boost.Any. My
approach is fairly different in that the list of types is fixed at
compile-time, like a typelist. I should point out that the
typelist-equivalent of your container would be Boost.Tuple, which is not
an associative container like mine.

> What I use this for (question: can I use your approach to achieve these ends
> better?):

If you know the set of types at compile time, the typelist approach is
a) more efficient and b) typesafe. If you don't, this approach simply
doesn't work.

> In your paper "section 7: Where varlist can be useful" you discuss using
> your technique to work with heterogeneous collections of classes containing
> different settings. I use my CMoniker hack similarly. I pass around
> references to my some_stl_container<CMoniker> and let the called method
> determine which elements in the container they "know" how to deal with -
> effectively I enumerate the CMoniker's and dispatch on type.

Similar to mine, except one would always know the type at compile-time, 
so no runtime dispatch would be required. You fish the object out of the 
container and it already is the correct type.

> Another place where I use CMoniker (and this is directly related to the
> mutable property graph I think), is in BGL property maps. This effectively
> lets me associate any CMonikerBase-derived class with an edge or vertex
> using an unmodified version of Mr. Siek's property map. What's it good for?
> File this under "this is cool": I use BGL directed graphs, specifically
> forests, to abstract expressions. Vertices are operands, edges are
> operators. I use a topological sort and a variant of Alexandrescu's double
> dispatch idea to evaluate the entire graph as an expression generically.
> Specifically I use this approach to deserialize XML streams but I think it's
> generally useful.

This is something that my class is not any use for: your expressions, I
assume, are built up at runtime. In fact, my class _is_ a BGL property
map (I mean that it does the same thing, not that it necessarily
conforms to the required interface), and you are deliberately subverting
the compile-time type checking of the property map to achieve your
run-time dispatch. 

> So do you think I can use your varlist idea instead of my CMoniker? That
> would be excellent as I don't really like CMoniker but haven't had time to
> fix it. If so, I'm interested in trashing my CMoniker and working your stuff
> into the mix instead.

For runtime stuff, I'd have a good look at Boost.Any. For compile time
stuff, I think the type-checking advantage is a strong argument for
going with an associative_list (or in your case, probably a tuple).

Emily