Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?

Subject: Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?
From: Gottlob Frege (gottlobfrege_at_[hidden])
Date: 2014-11-28 14:01:50

On Thu, Nov 27, 2014 at 5:44 PM, Gavin Lambert <gavinl_at_[hidden]> wrote:
>
> I'm not sure I understand the meaning of having an order that isn't implied
> by op<.  If op< is omitted because comparison is meaningless or otherwise
> confusing, how could it be well-defined how to sort them?  If there is not a
> single well-defined sort order, then the library should not just pick one
> arbitrarily, and if there is, then why would it not be appropriate as an
> op<?
...
>
> I don't agree with any of that.  If you want to use it as a key for
> something map/set-like, use unordered_map/set.  I can think of multiple
> possible orderings of std::complex depending on application need, and I
> don't think any one of them is inherently "better" than any other.  So this
> should be left to the application to define the sort order, in the rare case
> that this would actually be needed.
>

Maybe unordered_map has lessened the need for "representational
ordering"[*], but it hasn't eliminated it.

[*] like representational equality, see Stepanov's Elements of
Programming.  People like Sean Parent and Stepanov suggest
specializing std::less with a representational ordering when a
"meaningful" op< doesn't exist.

There are still reasons to use std::map over unordered_map.  Lack of a
cryptographically safe hash is one of them.  There are others (that
I've forgotten, but I've asked the same question to committee members
before, and there were a few reasons that sounded valid to me.)

Basically, people still want complex (for example) as a key in
std::map. Maybe that is becoming rare enough that they can just pass
in an explicit comparison when needed, but not always easy in generic
code (more on that below).

>>
>> optional<T> is Regular if T if Regular.  The more that optional<T>
>> "just works" like int works, the better.   Particularly for generic
>> code.
>
>
> The first part sounds like a definition I am unfamiliar with.

Regular is a concept. See Stepanov's Elements of Programming.  Or just
think "int".  ie assignable, copyable, copies are disjoint, etc.
Stepanov includes ordering as part of Regular (IIRC).

>  I agree with
> the second part, but I don't think it's relevant to this discussion.  Nobody
> is talking about removing op<(optional<T>,optional<T>),

well, I am including it as a suggestion, with only retaining std::less.

>  which is what generic code would use.

Generic code (like STL) uses std::less. And if T might be a pointer,
you should too, technically.

>>
>> 1 - op<(optional<T>, optional<T>) is "sensible" but somewhat arbitrary
>> 2 - op<(optional<T>, T) is questionable, often (usually?) wrong
>> 3 - in general, func(optional<T>, optional<T>) should work if passed
>> T's (ie implicit conversion is important)
>> 4 - op<(optional<T>, optional<T>) *is* of the form func(optional<T>,
>> optional<T>) - ie why should it be different?
>
>
> All true.
>
>> 2 and 3, to me, are the strongest, but directly opposed.
>> How do you solve that?
>> Either say
>>
>> A1. "well operators are special, not typical functions" so we can
>> poison them while keeping general functions implicit
>> A2. 1 is on shaky ground, so let's remove both 1 and 2, but keep
>> std::less/std::order, which was the main reason for having op<.
>
>
> Of these, I prefer A1.  I think it really is a special case.  But I can
> understand why the present behaviour is as it is.
>
> I suspect those who dislike "none" having a defined order would go for A2
> though.  I would be ok with that as well, but I don't have a problem with
> this definition.
>
> But you're leaving out A3: remove 1+2 AND std::less/std::order.  This means
> that optional types can't be used in map keys, only in unordered_map.  I
> actually think that this is the best option, except that it has a greater
> potential to break existing code.  Perhaps a predicate could be defined
> specific to optional giving the current ordering, so that users who do want
> that ordering or to continue using a map could just specify that predicate
> as a minimal fix.  But I don't think that the predicate should be spelled
> "std::less".
>

I agree A3 is the other option, and I should have listed it.  However,
I think it is a non-starter.  Even though we have unordered_map, the
committee strongly felt that optional should have some form of
std::less (either through op< or directly).  Maybe that is just "old
school thinking" because we are too use to using std::map instead of
unordered_map, but, as I mentioned above, there were other reasons
given, and, IIRC, the committee was pretty set on having std::less
work somehow.

Tony