Re: [Boost-users] [mpl] a few questions about set and map

From: David Abrahams (dave_at_[hidden])
Date: 2006-06-29 14:36:04

Yuval Ronen <ronen_yuval_at_[hidden]> writes:

> David Abrahams wrote:
>>>> Well, there's a default implementation that works for anything
>>>> providing begin, so I suppose it doesn't need to be part of the
>>>> concept from that point of view.  However, some sequences might
>>>> provide a more efficient one, and generic code that wants to use front
>>>> should be able to count on it.
>>> More efficient than constant time?
>>> If 'begin' is required to have constant time, and 'deref' is constant 
>>> time (deref is not documented to be constant time, but I assume it is - 
>>> is this assumtion wrong?), and front can be implemented using begin and 
>>> deref, then front is also constant time. Can any sequence beat it?
>> 
>> Sure, with a smaller constant.  one instantiation instead of two or
>> more, for example.
>
> But in such cases the meta-function that should specialized/optimized is 
> 'begin', not 'front', isn't it?

No.  The default version of front always takes at least two
instantiations (begin<...> and deref<...>).  If you can do front in
one instantiation and you want the optimization, you'd better
specialize it.

> When I said "there's no first element", I meant "there's no meaning to 
> the term 'first element', which is *different* from the meaning of 
> 'deref< begin< > >'". 

I think the placement of a comma above and other subtleties make that
not say what you mean.  Do you mean,

    The meaning of the term 'first element' is not distinct from that
    of 'deref< begin< > >'

?

If so, I have no argument with it.

> My point was that if the meaning is the same, there's no need for it
> (unless we're talking about options for performance gain,

But that's exactly what we're talking about.

> which is what we talked about in the previous 
> paragraph), and a different meaning just doesn't exist.

Yes.

> I never found myself wishing I had a singly-linked-list. Maybe I just 
> don't have enough experience...

Maybe not.  Some people really don't want to pay for the extra pointer
per node.  The SGI STL (and many other real-world implementations)
come with a singly-linked list.

>>> so I don't see why they should be re-introduced in MPL.
>> 
>> Um, it's a little late for that.  Type lists (mpl::list) are one of
>> the most basic kinds of type sequences.
>
> And what is mpl::list good for? I tried to find an answer to this in the 
> docs, but found nothing.

For one thing, it's infinitely extensible (up to compiler limits).
Except on implementations with nonstandard extensions, vectors have a
fixed maximum number of elements set by the library.

The efficiency tradeoffs are somewhat different.  It isn't
unreasonable to think that on some implementations, a series of
pop_front operations on a list would be much faster than it would be
on a vector.

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com