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

From: Yuval Ronen (ronen_yuval_at_[hidden])
Date: 2006-06-28 05:21:39

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?

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

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

>>>Personally, I don't think that providing it is any more weird than
>>>providing 'begin'.
>>
>>'begin/end' are needed in order to iterate the sequence, and therefore 
>>required for for any sequence. 'front', as I see it (which I hope is the 
>>right way to see it) is only relevant for sequences where the order of 
>>the elements is user-defined, i.e. vector and list. Where the order is 
>>not guaranteed (set/map), there is no meaning to 'front'.
> 
> Of course there is meaning.

See my previous paragraph.

>>>'front' is a shortcut for 'deref< begin<s>::type >'
>>
>>The fact that 'front' is just a shortcut for 'deref< begin<s>::type >' 
>>is another reason why it's not really needed for Forward Sequence.
> 
> It's not just a shortcut; it can be optimized for specific sequences.

Again, can it be more optimized than constant time?

>>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, so I don't see why they should be 
re-introduced in MPL.

>>>Informally, 'joint_view' provides us a way to iterate through the
>>>elements of two sequences without paying the upfront cost of their
>>>concatenation. While technically it could be specialized for
>>>associative sequences to eliminate duplicates, it would (a) break
>>>genericity of the adaptor and (b) deprive us of the basic,
>>>unspecialized functionality. If I was to implement the suggested
>>>behavior, I'd go for a separate 'unique_view' component which would
>>>have none of the downsides and an advantage of being applicable to
>>>non-associative sequences as well.
>>
>>Then I think a word of warning in the docs about using it with set/map 
>>is a good idea. People like me could get confused...
> 
> 
> The problem is that to me this looks like a one-off confusion.  If the
> joint view docs clearly state that the two sequences are concatenated,
> I don't see why anyone else would be confused.  I never loved the name
> "joint_view" though.  Maybe "concat_view" would be clearer.

OK, I agree that concat_view is a better name.