Re: [boost] Re: MPL containers and algorithms

From: Terje Slettebø (tslettebo_at_[hidden])
Date: 2002-07-30 14:51:48

>From: "Andrei Alexandrescu" <andrewalex_at_[hidden]>

> "Aleksey Gurtovoy" <agurtovoy_at_[hidden]> wrote in message
> news:4034600A4760D411B8720001031D84FB010963B2_at_postoffice.office.meta...
> >
> > BTW, I am kind of tired of repeating the same arguments over and over.
If
> > you don't agree with them, it's your right. The separation of algorithms
> > from the sequence implementations is one of these things in MPL design
> that
> > are not going to change, period. I think it has been argumented well
> enough
> > over the time; if you feel that this is a corner issue, feel free to
vote
> > the library down.
>
> My intent was to become convinced, not to vote the library down.

>From the earlier posting:

>Let's think we did not need to support bad compilers for a second. Would
>separation of data structures and algorithms still be a design decision for
>MPL?

Good question. Let's explore this.

Before starting, I don't think the efficiency issue can be ignored. It would
be similar to ignoring it for STL containers and algorithms, only that for
metaprogramming, the execution time is during compilation, not at run-time.

Disregarding bad compilers is one thing, disregarding complexity guarantees
on algorithms is an entirely different thing. Keep in mind that if this is
ignored, it'll be _you_ waiting for the compiler to finish, not the user. :)
So it should be very relevant for developers, too.

In addition, it's the issue of flexibility and generecity.

Therefore, the following will deal with both efficiency, and flexibility.

Having looked at mpl::vector, and its docs, it appears that it may be
possible to get O(1) access to elements, if the compiler supports typeof. In
that case, if you have an algorithm that does a lot of random access, it may
be faster. Another possibility is, if possible, choose an algorithm that
doesn't use random access. Another advantage, besides possibly speed, is
that you save the valuable compile-time resource known as number of template
instantiations, or depth of template recursion, as has been mentioned.

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.

Loki's algorithms, on the other hand, are hardwired to work on cons-lists,
so you can't use e.g. Length on anything else.

Consider Loki's cons-list, with its Lisp-style Head and Tail (which I, by
the way, find as much better names than the cryptic "car" and "cdr" names,
used in e.g. Lisp):

typedef Typelist<char, Typelist<int, Typelist<double, NullType> > >
LinkedList;

It has the structure of a linked list. As a tree, it may be pictured like
this:

   Typelist
    /           \
char    Typelist
               /      \
          int       Typelist
                         /       \
                 double    NullType

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.

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.

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.

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

I vote yes, too.

Regards,

Terje - Halfway expecting an "Et tu, Brutus?" reply from Andrei. :)