Yuval Ronen writes:

Yuval Ronen wrote:

...

I spent some time reading the mpl docs, and I have a few questions about mpl::set and mpl::map.

I'm reading the Boost mailing lists using the Gmane NNTP gateway, which just came back to life after being dead for a day or two. This (along with the fact the users ML is not archived)

It's not? http://lists.boost.org/boost-users/ -- Dave Abrahams Boost Consulting www.boost-consulting.com

Yuval Ronen writes:

David Abrahams wrote:

...

Yuval Ronen writes:

...

Yuval Ronen wrote:

...

I spent some time reading the mpl docs, and I have a few questions about mpl::set and mpl::map. I'm reading the Boost mailing lists using the Gmane NNTP gateway, which just came back to life after being dead for a day or two. This (along with the fact the users ML is not archived)

It's not?

http://lists.boost.org/boost-users/

Well well, it seems I was wrong. And so is http://www.boost.org/more/mailing_lists.htm which contain a "Archives for Boost developers list" section, but no "Archives for Boost users list" or a more general "Archives for Boost lists".

Now if only someone had some answers to my questions (archived at http://lists.boost.org/boost-users/2006/06/20252.php)...

I don't, or I'd have answered. This is strictly Aleksey's bailiwick. -- Dave Abrahams Boost Consulting www.boost-consulting.com

Aleksey Gurtovoy 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'? What is it good for?

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, everything I say is analogous to std containers, and should sound familiar.

'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. Providing 'front' without 'back' sounds stridently asymmetric to me.

...

3. The docs say that the size of joint_view is the arithmetic sum of the sizes of the sequences of which it's composed.

Yep.

...

Is that true also in the case of set/map?

Yes.

...

For an mpl newbie it sounds reasonable that it will removed duplicates and might end up with a size that is smaller than the sum of its components. If it's not, then it sounds quite useless to use it for set/map.

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

HTH

Yes it does! Thanks.

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.

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?

...

...

...

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::type, end<S>::type) and never encounter that value again.

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< > >'". 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, which is what we talked about in the previous paragraph), and a different meaning just doesn't exist.

...

...

...

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.

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

...

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.

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.

If this single instantiation you save is important (which sounds to me like too small a thing to mess with, but if you claim otherwise, I'll take your word for it), then wouldn't you want to specialize 'back' as well as 'front', if possible? You might be able save an instantiation there as well... Moreover, if this single instantiation saving is important, should it be specialized for *all* sequences, including those already present in mpl?

...

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.

Yes, that's what I meant. That comma probably was misplaced, as it managed to confuse even me trying to read my own text again... :-)

David Abrahams wrote:

Yuval Ronen writes:

...

...

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. If this single instantiation you save is important (which sounds to me

David Abrahams wrote: like too small a thing to mess with, but if you claim otherwise, I'll take your word for it),

It's at least a 50% savings, and quite possibly more than 50%.

It's at most 50%, not at least. Remember that I compare specializing 'front' to using the default 'front' + specializing 'begin'. Any optimization you put in 'front' you can also put in 'begin', so you save exactly one instantiation saved, which is at most 50%. But again, if you say that it's important, then I'll accept it.

...

then wouldn't you want to specialize 'back' as well as 'front', if possible? You might be able save an instantiation there as well...

You might want to do that, yes... "if possible" being key words here.

...

Moreover, if this single instantiation saving is important, should it be specialized for *all* sequences, including those already present in mpl?

I don't have an opinion on it, and I don't see where you're going with that question.

Where I was going (or was trying to go - we'll see if I'll actually get there) is to show that there is a contradiction between two things. The first is the claim that a single instantiation is worth saving. The second is Forward Sequence requiring 'front' and not 'back'. If we're that much into saving, then it should require back for the same reason as it requires front. And also all sequences should take advantage of this, and actually specialize front and back to save this instantiation. The other option is to declare that an extra single instantiation s not that bad, not require front/back, and leave all possible optimizations to begin/end. The default front/back will work fine. I hope I could explain myself better this time.

David Abrahams wrote:

Yuval Ronen writes:

...

David Abrahams wrote:

...

Yuval Ronen writes:

...

...

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. If this single instantiation you save is important (which sounds to me

David Abrahams wrote: like too small a thing to mess with, but if you claim otherwise, I'll take your word for it), It's at least a 50% savings, and quite possibly more than 50%. It's at most 50%, not at least. Remember that I compare specializing 'front' to using the default 'front' + specializing 'begin'. Any optimization you put in 'front' you can also put in 'begin',

No. Producing an iterator can be arbitrarily more expensive than producing the first element, and can't necessarily be done with a single specialization.

OK, I didn't know that producing an iterator can be arbitrarily more expensive than producing the first element (while still maintaining constant time). That's definitely new information for me, and I'll have to take it into account.

...

so you save exactly one instantiation saved, which is at most 50%.

This sentence of mine is obviously wrong, in light of this new information.

...

Where I was going (or was trying to go - we'll see if I'll actually get there) is to show that there is a contradiction between two things. The first is the claim that a single instantiation is worth saving. The second is Forward Sequence requiring 'front' and not 'back'.

You'll never get there with me; they're unrelated questions.

I was trying to show that they are in fact related, unsuccessfully.

...

If we're that much into saving, then it should require back for the same reason as it requires front.

Sorry, I'll never agree to that. It's like saying that all iterators need to be bidirectional just because they should be incrementable.

I disagree with the validity of the comparison. It's not the same thing. Supplying 'back', in order to allow for sequences to specialize and optimize it (to save producing an iterator, which is "arbitrarily more expensive"), is not comparable to the incrementable/bidirectional iterators issue. The latter is about capabilities, while the former is about performance improvement possibilities.

That's one other option. Another option is just to work with the concepts as they are and stop trying to convince us they're ill-conceived. What's wrong with that one? I don't mean to be facetious, but you seem to be grasping at straws to show that there's something wrong here, but I don't see what major problems the status quo is causing.

I was hoping to get to the bottom of this, to fully understand what's going on, and why, to convince or be convinced. However, if you are unwilling to continue this discussion, then, well, you have every right to do so. We'll just go our separate ways, each maintaining his original opinion, one of us (me) is wrong.

David Abrahams wrote:

Yuval Ronen writes:

...

...

That's one other option. Another option is just to work with the concepts as they are and stop trying to convince us they're ill-conceived. What's wrong with that one? I don't mean to be facetious, but you seem to be grasping at straws to show that there's something wrong here, but I don't see what major problems the status quo is causing. I was hoping to get to the bottom of this, to fully understand what's going on, and why, to convince or be convinced. However, if you are unwilling to continue this discussion, then, well, you have every right to do so.

Well, it doesn't seem all that productive. At some point, which requirements to make part of a concept is a judgement call. There are guidelines that ought to be followed, but some decisions fall into a gray area. You might legitimately choose differently from Aleksey, but I don't think the validity of your choice delegitimizes his choice, which is what you seem to be arguing.

I never meant to delegitimize anyone or anything, so help me God. It doesn't mean we can't have a discussion, or even an argument, about which of several options is better. And I believe that's true even if we're talking about code already written, used and appreciated. If it sounded like I was delegitimizing, then I'm truly sorry. My sincere apologies to you, to Aleksey, and to the queen of England, if necessary.

...

We'll just go our separate ways, each maintaining his original opinion, one of us (me) is wrong.

I don't see why you would maintain your original opinion if you were convinced it was wrong.

Now I'm facetious...