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

From: David Abrahams (dave_at_[hidden])
Date: 2006-06-28 08:47:53

Yuval Ronen <ronen_yuval_at_[hidden]> writes:

> David Abrahams wrote:
>>>>>1. The docs assert there is a 'front' algorithm for set and
>>>>>map. This sounds weird to me, as the order of the types is them
>>>>>unspecified.
>>>>
>>>>The 'front's availability is dictated by the Forward Sequence concept
>>>>requirements
>>>>(http://www.boost.org/libs/mpl/doc/refmanual/forward-sequence.html).
>>>
>>>Then perhaps the Forward Sequence concept should not require
>>>'front'? 
>> 
>> 
>> 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.

>>>What is it good for?
>> 
>> Isn't it obvious?  Getting the first element of the sequence.
>
> But there is no 'first element' in Associative Sequences. From the 
> Associative Sequence doc:
>
> "Unlike associative containers in the C++ Standard Library, MPL 
> associative sequences have no associated ordering relation"

Come on, man, use common sense.  That doesn't mean there's no first
element.  That just means there's no guarantee which of the elements
it will turn out to be.  If it's a set, for example, you can look at
front, then iterate over [next<begin<S>::type>::type, end<S>::type)
and never encounter that value again.

> There are 'begin' and 'end' for iteration, but there's no guaranteed 
> order, as far as I understand, so there's no meaning to 'front'.

Then your understanding is flawed.

>>>Providing 'front' without 'back' sounds stridently asymmetric to me.
>> 
>> See any singly-linked list implementation.
>
> Singly-linked containers were excluded from the standard library, and 
> probably for a good reason, 

Yeah, the committee only had so much time to process what Alex gave them.

> 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.

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