[STLInterfaces] only three operations?

Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

[STLInterfaces] only three operations?

Boost - Dev mailing list
Hi,
While the formal review of STLInterfaces has not yet started, some early
feedback may be of help.

The idea to implement relational operators from binary operator- for
random_access_iterator looks too clever for me. Maybe this deserves a
mention in the documentation it is from operator- that the library will
generate all relational ops.

For non-contiguous random_access_iterators (like in deque) it might be
suboptimal to do it this way: a directly provided operator== might be
faster than the one synthesized from operator-. Of course, I can provide
the 6 relops operators myself, but I could have only 2 if the facade were
capable of generating operator!= from operator== (and similar). Could
operator!= for random_access_iterator be generated from operator!= ?

Regards,
&rzej;

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list
On Wed, Nov 27, 2019 at 8:38 AM Andrzej Krzemienski via Boost <
[hidden email]> wrote:

> Hi,
> While the formal review of STLInterfaces has not yet started, some early
> feedback may be of help.
>
> The idea to implement relational operators from binary operator- for
> random_access_iterator looks too clever for me.


I don't find that to be so.  All those operations (the relops and op-) go
together semantically.  Could you elaborate on why you don't like the
approach?


> Maybe this deserves a
> mention in the documentation it is from operator- that the library will
> generate all relational ops.
>

Quite right.  I'll add this if it's not already documented, or call it out
if it's not obvious enough.


> For non-contiguous random_access_iterators (like in deque) it might be
> suboptimal to do it this way: a directly provided operator== might be
> faster than the one synthesized from operator-. Of course, I can provide
> the 6 relops operators myself, but I could have only 2 if the facade were
> capable of generating operator!= from operator== (and similar). Could
> operator!= for random_access_iterator be generated from operator!= ?
>

It's true that the deque case will be suboptimal.  Here are my
considerations though:

- The point of the library is to reduce the amount of code you must write
to the bare minimum, and basing all the relops on op-  and op== does not
serve that goal.
- Any generated operation (not just the relops) can be replaced by the user
at will, just be having the user define that operation.  In the deque case,
that means defining op-, op==, and op!=.  Deque is not the common case --
most random-access containers are also contiguous.  I want to maintain the
brevity of the common case.  That means the solution is clear
documentation, IMO.

Zach

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list

> On 27. Nov 2019, at 15:55, Zach Laine via Boost <[hidden email]> wrote:
>
> On Wed, Nov 27, 2019 at 8:38 AM Andrzej Krzemienski via Boost <
> [hidden email]> wrote:

>> For non-contiguous random_access_iterators (like in deque) it might be
>> suboptimal to do it this way: a directly provided operator== might be
>> faster than the one synthesized from operator-. Of course, I can provide
>> the 6 relops operators myself, but I could have only 2 if the facade were
>> capable of generating operator!= from operator== (and similar). Could
>> operator!= for random_access_iterator be generated from operator!= ?
>
> It's true that the deque case will be suboptimal.  Here are my
> considerations though:
>
> - The point of the library is to reduce the amount of code you must write
> to the bare minimum, and basing all the relops on op-  and op== does not
> serve that goal.
> - Any generated operation (not just the relops) can be replaced by the user
> at will, just be having the user define that operation.  In the deque case,
> that means defining op-, op==, and op!=.  Deque is not the common case --
> most random-access containers are also contiguous.  I want to maintain the
> brevity of the common case.  That means the solution is clear
> documentation, IMO.

I think Andrzej made a good point, it should be possible to override automatically generated operators by adding a minimal number of extra operators, minimal demo:

https://godbolt.org/z/zaFpBU

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list
On Wed, Nov 27, 2019 at 9:45 AM Hans Dembinski <[hidden email]>
wrote:

>
> > On 27. Nov 2019, at 15:55, Zach Laine via Boost <[hidden email]>
> wrote:
> >
> > On Wed, Nov 27, 2019 at 8:38 AM Andrzej Krzemienski via Boost <
> > [hidden email]> wrote:
>
> >> For non-contiguous random_access_iterators (like in deque) it might be
> >> suboptimal to do it this way: a directly provided operator== might be
> >> faster than the one synthesized from operator-. Of course, I can provide
> >> the 6 relops operators myself, but I could have only 2 if the facade
> were
> >> capable of generating operator!= from operator== (and similar). Could
> >> operator!= for random_access_iterator be generated from operator!= ?
> >
> > It's true that the deque case will be suboptimal.  Here are my
> > considerations though:
> >
> > - The point of the library is to reduce the amount of code you must write
> > to the bare minimum, and basing all the relops on op-  and op== does not
> > serve that goal.
> > - Any generated operation (not just the relops) can be replaced by the
> user
> > at will, just be having the user define that operation.  In the deque
> case,
> > that means defining op-, op==, and op!=.  Deque is not the common case --
> > most random-access containers are also contiguous.  I want to maintain
> the
> > brevity of the common case.  That means the solution is clear
> > documentation, IMO.
>
> I think Andrzej made a good point, it should be possible to override
> automatically generated operators by adding a minimal number of extra
> operators, minimal demo:
>
> https://godbolt.org/z/zaFpBU


Sure, that's easy.  Modifying sequence_container to generate overloads
based on op== and/or op- is not so easy. :)   As I said, if you find the
op==/op!= case to be less optimal when implemented in terms of op-, it's
just a matter of adding your own op==, and a one-liner op!=.  That's not a
great deal of burden on the user.

Zach

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
śr., 27 lis 2019 o 15:54 Zach Laine <[hidden email]>
napisał(a):

> On Wed, Nov 27, 2019 at 8:38 AM Andrzej Krzemienski via Boost <
> [hidden email]> wrote:
>
>> Hi,
>> While the formal review of STLInterfaces has not yet started, some early
>> feedback may be of help.
>>
>> The idea to implement relational operators from binary operator- for
>> random_access_iterator looks too clever for me.
>
>
> I don't find that to be so.  All those operations (the relops and op-) go
> together semantically.  Could you elaborate on why you don't like the
> approach?
>

I am sorry. I was writing that mail in a hurry an I failed to communicate
my thoughts clearly. I do like your approach. In fact, I find it really
illuminating. It is just that I find it so novel, that it could easily be
taken for a mistake. I was staring at the docs for a long while, where it
said the only operations I need for random access iterator was *, -, and
+=, and I concluded that there must be some some error in the script that
produces the documentation and the guy surely wanted to type operator== as
well. Only after looking at the implementation did I realize that it was
not a mistake.

Hence my suggestion: make it very clear in the documentation that relops
are generated from operator- for random access iterators.


>
>
>> Maybe this deserves a
>> mention in the documentation it is from operator- that the library will
>> generate all relational ops.
>>
>
> Quite right.  I'll add this if it's not already documented, or call it out
> if it's not obvious enough.
>
>
>> For non-contiguous random_access_iterators (like in deque) it might be
>> suboptimal to do it this way: a directly provided operator== might be
>> faster than the one synthesized from operator-. Of course, I can provide
>> the 6 relops operators myself, but I could have only 2 if the facade were
>> capable of generating operator!= from operator== (and similar). Could
>> operator!= for random_access_iterator be generated from operator!= ?
>>
>
> It's true that the deque case will be suboptimal.  Here are my
> considerations though:
>
> - The point of the library is to reduce the amount of code you must write
> to the bare minimum, and basing all the relops on op-  and op== does not
> serve that goal.
> - Any generated operation (not just the relops) can be replaced by the
> user at will, just be having the user define that operation.  In the deque
> case, that means defining op-, op==, and op!=.  Deque is not the common
> case -- most random-access containers are also contiguous.  I want to
> maintain the brevity of the common case.  That means the solution is clear
> documentation, IMO.
>

I agree with aiming at the minimum boilerplate from the user, and I agree
that non-contiguous random access iterators are so rare that they could be
sacrificed. However, I believe that what I propose does not compromise your
goals. As Hans pointed demonstrated, if you implement operator== using
operator-, and then implement operator!= using operator== (rather than
using operator-), then all your use cases work as before, but the
additional gain is that if I additionally volunteer to provide my own
operator== (because it is faster) you can give me operator!= for free.

Does this make sense?

Regards,
&rzej;


> Zach
>
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list
On Wed, Nov 27, 2019 at 3:49 PM Andrzej Krzemienski <[hidden email]>
wrote:

>
> śr., 27 lis 2019 o 15:54 Zach Laine <[hidden email]>
> napisał(a):
>
>> On Wed, Nov 27, 2019 at 8:38 AM Andrzej Krzemienski via Boost <
>> [hidden email]> wrote:
>>
>>> Hi,
>>> While the formal review of STLInterfaces has not yet started, some early
>>> feedback may be of help.
>>>
>>> The idea to implement relational operators from binary operator- for
>>> random_access_iterator looks too clever for me.
>>
>>
>> I don't find that to be so.  All those operations (the relops and op-) go
>> together semantically.  Could you elaborate on why you don't like the
>> approach?
>>
>
> I am sorry. I was writing that mail in a hurry an I failed to communicate
> my thoughts clearly. I do like your approach. In fact, I find it really
> illuminating. It is just that I find it so novel, that it could easily be
> taken for a mistake. I was staring at the docs for a long while, where it
> said the only operations I need for random access iterator was *, -, and
> +=, and I concluded that there must be some some error in the script that
> produces the documentation and the guy surely wanted to type operator== as
> well. Only after looking at the implementation did I realize that it was
> not a mistake.
>
> Hence my suggestion: make it very clear in the documentation that relops
> are generated from operator- for random access iterators.
>

Got it, thanks.  Based on your original email, I've made this clear in the
docs (though that change is not live on the website yet).

[snip]

It's true that the deque case will be suboptimal.  Here are my

>> considerations though:
>>
>> - The point of the library is to reduce the amount of code you must write
>> to the bare minimum, and basing all the relops on op-  and op== does not
>> serve that goal.
>> - Any generated operation (not just the relops) can be replaced by the
>> user at will, just be having the user define that operation.  In the deque
>> case, that means defining op-, op==, and op!=.  Deque is not the common
>> case -- most random-access containers are also contiguous.  I want to
>> maintain the brevity of the common case.  That means the solution is clear
>> documentation, IMO.
>>
>
> I agree with aiming at the minimum boilerplate from the user, and I agree
> that non-contiguous random access iterators are so rare that they could be
> sacrificed. However, I believe that what I propose does not compromise your
> goals. As Hans pointed demonstrated, if you implement operator== using
> operator-, and then implement operator!= using operator== (rather than
> using operator-), then all your use cases work as before, but the
> additional gain is that if I additionally volunteer to provide my own
> operator== (because it is faster) you can give me operator!= for free.
>
> Does this make sense?
>

Yes, it does.  I'll try this, but I vaguely remember that I tried things
this way and got an ambiguity.  Hopefully I'm misremembering.

Zach

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [STLInterfaces] only three operations?

Boost - Dev mailing list
On Mon, Dec 9, 2019 at 12:55 PM Andrzej Krzemienski <[hidden email]>
wrote:

>
>
> pon., 9 gru 2019 o 17:32 Zach Laine <[hidden email]>
> napisał(a):
>
>>
>>
>>
>>> Same with the iterator in the flight map:
>>>
>>>
>>>> https://github.com/tzlaine/flat_map/blob/master/implementation/flat_map#L266
>>>>
>>>
>>> According to C++17 requirements this shouldn't have been a
>>> random_access_iterator.
>>>
>>> Also, std::ranges::sort() will not work with it. But this is not
>>> directly related to `iterator_interface`
>>>
>>
>> I don't know why you think that.  ranges::sort() is designed to work with
>> std::random_access_iterator, which is designed explicitly to support proxy
>> iterators.  Casey and Eric have assured me that this "just works".  Do you
>> know of a reason why it does not?  If so, you've spotted a defect, and we
>> should file an LWG issue immediately.
>>
>
> Not sure if it is a defect. An iterator that returns a proxy as
> ::reference can be a valid random_access_iterator. However,
> std::ranges::sort(), apart from a random_access_iterator requirement, has
> one more requirement: sortable<>: (http://eel.is/c++draft/sort) which
> boils down to indirectly_writable (
> http://eel.is/c++draft/iterator.concept.writable). This last concepts
> puts severe restrictions on proxy types. For instance you should be able to
> assign to them when they are const-qualified. So a type like std::tuple<>
> of references will not work. But you will be able to design a sufficiently
> bizarre proxy type that will work with std::ranges::sort(), So in a way it
> will work with *some* reference proxies.
>

Ok, I just realized this somehow drifted off-list.  Re-adding the list...

This is the definition of indirectly_writable:

template<class Out, class T>
  concept indirectly_writable =
    requires(Out&& o, T&& t) {
      *o = std::forward<T>(t);  // not required to be equality-preserving
      *std::forward<Out>(o) = std::forward<T>(t);   // not required to
be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*o) =
        std::forward<T>(t);     // not required to be equality-preserving
      const_cast<const iter_reference_t<Out>&&>(*std::forward<Out>(o)) =
        std::forward<T>(t);     // not required to be equality-preserving

};

All you need to make this work is a reference type for which all those are
well-formed.  If you pick std::tuple, it all just works.  If you pick
std::pair, only the first two expressions in the requires expression work.
You can easily define UDTs for which this concept works too, of course.

Zach

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost