Boost logo

Boost :

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
> >
> > >
> > > 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
> > > 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
> >MPL?
> Good question. Let's explore this.
> Before starting, I don't think the efficiency issue can be ignored. It
> be similar to ignoring it for STL containers and algorithms, only that for
> metaprogramming, the execution time is during compilation, not at
> Disregarding bad compilers is one thing, disregarding complexity
> 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.
> that case, if you have an algorithm that does a lot of random access, it
> 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
> 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
> are there other useful containers? Well, Dave replied to that, using a
> structure as an example.
> Imagine this: You make a tree structure (like a binary tree), which
> iterators for pre-, post- and in-order traversal. Then you may use that
> 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
> 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),
> this reason.
> Now, consider what's called "s-expressions" (which I recently looked up,
> 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
> search.
> mpl::map, anyone? :) It was asked about other possible containers, how
> 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
> second list, here, then, as he said, you'd either have to flatten it
> 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
> 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
> 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:

Boost list run by bdawes at, gregod at, cpdaniel at, john at