Re: [boost] Re: MPL containers and algorithms

From: David Abrahams (dave_at_[hidden])
Date: 2002-07-28 23:00:04

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

> > Hi Andrei,
> >
> > Just a few comments:
> >
> > 1. Which experience are you talking about?
>
> I was talking about my own experience. For example, MWCW handles
> dot-typelists so fast, I had doubts it compiled the code correctly :o).

MWCW is just wicked fast at template instantiation, period. That doesn't
show a preference for one or the other structure, though.

> Even
> in cases where dot-lists are not supposed to be as efficient as vectors.
>
> > 2. It's not just about compilation speed, although that's a real factor
> > also. There are other compilation resources which count as well, such
as
> > depth of template instantiation. Some compilers have internal limits on
> how
> > much nesting they will allow... and this too affects speed on some
> > compilers.
>
> That is true, and I believe that by and large, a library for compile-time
> processing would be concerned with that (although to some compile time is
in
> a sense "free"). The way C++'s template engine is structured, however,
leads
> me to think that dot-lists are just fine.

It's structured differently in different implementations.

Until very recently, MWCW had a hard-coded limit on template nesting depth.
If you want to support CWPro 7.2, you might need to use long type vectors
in lieu of type lists just to avoid running into those limits. You can do
as much loop unrolling as you want to; it won't help if you can't even
represent your inputs or results.

> > 3. Data structures offer more than just linear constructions. For
example,
> > given the right iterators we can treat a tree as a sequence. I realize
you
> > can represent a tree using dot typelists, but without iterators you
need a
> > special algorithm to flatten the tree before you can use it in sequence
> > algorithms.
>
> An s-expression is a tree alright. You wouldn't have to flatten it in
order
> to process it. LISP provides many examples of elegant tree processing,
and
> all it uses as data structures is the dot list.

Yes, but you need to flatten it in order to *treat it as a sequence* if all
of your sequence algorithms are hard-coded to work on slists.

In other words, if you want to process the following

        A
       / \
      B   C
     / \
    D   E

as an in-order sequence:

    D B E A C

You need either need to

    a. flatten it
or
    b. rewrite the algorithm which processes it so that it operates
specifically on trees.

Hmm, either way you now you have support for different data structures...

-Dave

-----------------------------------------------------------
           David Abrahams * Boost Consulting
dave_at_[hidden] * http://www.boost-consulting.com