Re: [boost] Re: MPL containers and algorithms

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2002-07-30 16:06:44

> However, there's something far more fundamental here, the advantage of
> decoupling containers from algorithms is the same as in STL. So you may ask,
> are there other useful containers? Well, Dave replied to that, using a tree
> structure as an example.
>
> Imagine this: You make a tree structure (like a binary tree), which supplies
> iterators for pre-, post- and in-order traversal. Then you may use that tree
> directly with any of the algorithms and metafunctions in MPL. As he said,
> you may find the size of the tree, the largest element, or whatever. All
> without rewriting any of the algorithms. Powerful, indeed.

Powerful, yes, but this doesn't answer Andrei's standing request for a concrete
real-world example.

> This is _not_ what you would call a balanced tree. It's very heavy on one
> side, so travelsal is O(N), with N being the number of elements, as we know.
>
> If you used this, as a tree, in a search-algorithm, for example, you'd get
> O(N), rather than O(log N), for a balanced tree. Loki's IndexOf is O(N), for
> this reason.

If you process each element, the entire thing is still going to have linear
qualities.  The only times that this makes any sense is when you are directly
processing many elements at one time (i.e. one per 'iteration') or when you are
using a sequence of types to hold unrelated arbitrary types.  Otherwise, element
access is the same.  It takes O(1) to go from element A to element B in both a
cons-style typelist and a vector (i.e. tuple-style list).

> Now, consider what's called "s-expressions" (which I recently looked up, as
> it was mentioned in this thread. :) ), where you may store different
> structures in such a list.
>
> Using that, you may store a different tree, using the same Typelist
> template:
>
> typedef Typelist<Typelist<char,int>,Typelist<double,NullType> > Tree;
>
> This is no longer a cons-list; this is a balanced binary tree:
>
>                Typelist
>                 /          \
>      Typelist        Typelist
>       /         \           /        \
>  char       int    double   NullType
>
> We now have O(log N) traversal to all nodes. If you had some kind of
> comparison criteria, you could store it as a sorted tree, and have O(log N)
> search.
>
> mpl::map, anyone? :) It was asked about other possible containers, how about
> an assosiative one? :)
>
> Dave Abrahams' point was that Loki's algorithms would work for the first
> kind of list, but not the second. To use any of the Loki algorithms for the
> second list, here, then, as he said, you'd either have to flatten it (making
> it a linear list, like the first one), or have tailor-made algorithms for
> each kind of container. That would be like the pre-STL era, where algorithms
> only worked on one type of container.
>
> However, if you provide the right iterators for the container or sequence,
> you may use it in any algorithm, unchanged, and without changing the
> algorithms.

You can't gloss over this part so easily.  Iterators are just a fancy way to
"flatten" some kind of structure into a sequence.  This means that you are
already providing the algorithm to flatten it, but you are doing it _all over
the place_ instead of in a single place.

> This means, like with STL, that with M containers and N algorithms, you can
> get M x N combinations, with M+N code. In addition, you may tailor it with
> metafunction classes, quoted metafunctions, whatever they are called, just
> like function objects in STL. This means you may, for example, for a
> compile-time accumulate/fold/reduce function (like STL's std::accumulate),
> get very different behaviour, depending on the metafunction passed to it.

It also means that, like the STL, you get M containers, N algorithms, _and_ M
iterators.  This is versus M containers, N algorithms, and M sequence convertors
implied by writing algorithms to operate on some *standard* sequence type.

>
> Then, there's function composition, bind, lambda, etc.

I think that the MPL is very interesting piece of work, and more importantly,
there are other Boost libraries that are waiting (or already using) some of the
metaprogramming facilities present in the MPL.  *However*, I don't buy (and
never have) the comparison to the STL.  Andrei is simply asking for a real-world
example where this kind of abstraction is actually *useful* (rather than just
*neat*) in template metaprogramming (without an assumptive reference to runtime
performance).  He is asking that the MPL prove the usefulness of its design
purely in the context of template metaprogramming.

Despite my differences of opinion about some of the core design, I vote
yes--primarily because Boost doesn't offer enough metaprogramming facilities,
and if the MPL doesn't get accepted, it will be even longer before a similar
library is added to Boost.

Paul Mensonides