Re: [boost] Re: MPL containers and algorithms

From: Christophe Avoinne (christophe.avoinne_at_[hidden])
Date: 2002-07-31 11:08:17

I don't know if I can vote. But if I have the right to do so, I vote : YES.

----- Original Message -----
From: "Terje Slettebø" <tslettebo_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Tuesday, July 30, 2002 9:51 PM
Subject: Re: [boost] Re: MPL containers and algorithms

> >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. :)
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost