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

Subject: Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?
From: Matt Calabrese (rivorus_at_[hidden])
Date: 2014-11-30 22:57:22

On Sun, Nov 30, 2014 at 5:49 PM, Gavin Lambert <gavinl_at_[hidden]>
wrote:
>
> Most containers do not implement ordering relations of the container
> itself.

Yes they do. All of the standard containers provide lexicographical
ordering.

>   String is an exception because people generally think of it as a value
> type rather than as a container of chars.
>
> Why should a std::pair<iterator, bool> have an order?  In what code would
> you ever try to sort by such a thing?  Generically sortable tuples and
> variants are similarly meaningless.
>

Why are you so quick to declare something as meaningless simply because you
personally don't immediately see the use? Putting those objects in a set is
a meaningful use of ordering, and you've even agreed that it's fine to do
so (though you have some kind of arbitrary preference for unordered
containers for these constructs). You also said in this very thread that
you don't use tuples, so why then do you feel as though you are so
qualified as to make an authoritative claim that ordering them is
meaningless? The fact is that all types can be ordered and there is nothing
wrong with using that ordering in generic (or non-generic) code. All a pair
or a tuple is is a container, much in the same way as the standard
containers but with a separate concept. The difference is just that tuples
and pairs are compile-time sized and heterogeneous while the standard
containers are (mostly) run-time sized and homogeneous.

As for why one might take advantage of such an ordering? I already gave you
an example in this thread where I personally used the ordering of variants,
though you mysteriously ignored it and again are make a claim that ordering
is simply "meaningless." I have more examples if you want, since I actually
use variants and tuples pretty much every day. So is ordering meaningful?
Of course it is. It is in my concrete example and it is in more abstract,
generic code where tuples and variants tend to manifest themselves either
internally for storage or when producing results. As someone who actually
uses these types in practice and who uses ordering of them, I am flat out
telling you that ordering them is, in fact useful, and it does, in fact,
make sense.

It's easy to add order comparisons in where required.  It's hard to remove
> them once present.

Prefaced by the reiteration that I'm not talking about the operators, only
std::less/std::order, just so we don't get side-tracked about the specific
meaning of <. I don't really much care if < and the like are defined. I
consider that separate from having a default ordering.

That said, why do you think that it would be hard to remove the ordering
once present? If order here were /actually/ meaningless as you repeatedly
claim, then it would trivial to remove, since nobody would be using it in
meaningful code.

> Define "correctly ordered" for an arbitrary tuple.  If this definition can
> vary from application to application or from context to context, then the
> definition should not be baked in to the tuple itself, but instead supplied
> only where actually needed.
>

"Correctly" meaning that it forms a mathematical order, as in it's not an
erroneous definition and the order is well specified. Also, the ordering
isn't "baked in," it's just a default. You /can/ explicitly specify an
ordering when you need one that's different from the default. In generic
code, having a default is particularly useful because frequently you do not
care what the order is, only that it /is/ ordered so that you can do
something like put it in a set, or sort data and binary search, etc.

> (It sounds like you are arguing that in this case the programmer should
> specify the tuple type specifically with its library-mandated ordering
> characteristics in mind, instead of whatever other logical field order they
> prefer.  Especially if different orderings are required in different
> contexts, the compile-time type seems like the wrong place to be defining
> this.)
>

No, that's not what I'm saying. A user /can/ do that if they choose, and
there's nothing wrong with that (my variant example is a reasonable example
of this). For all types, including built-in arithmetic types, the default
order is not always what is desired. So what? It is a default. That's all.

To reiterate again, code frequently requires order and users don't
necessarily care what that order is. Pointers are a great example of that.
Having a default is useful and it doesn't cause harm.

If the programmer does not require ordering, then why use a container that
> requires it, instead of one that does not?  Unless there is some other
> deficiency of unordered_set vs. set (other than relative newness and
> unfamiliarity) that I am unaware of, this seems obvious to me, and I'm not
> sure why you seem to oppose it so strongly.
>

They are entirely different datastructures with different complexities and
practical implementation implications both in terms of storage and
run-time. The unordered containers are not "deficient," they are just
different datastructures entirely and you should not base your decision on
which container to use just because someone chose there to not be a default
ordering for a given type. Not only should you not "just" make the choice
based on the lack of a default, but it shouldn't ever be a part of the
consideration at all whether there is a default or not.

Also, it's not simply a matter of choosing between two containers where one
has more strict requirements than another as you seem to have just implied
by "If the programmer does not require ordering, then why use a container
that requires it, instead of one that does not?". The unordered containers
don't have a subset of the requirements of the ordered ones, the
requirements are just different. Specifically, unordered containers require
a hashing function while ordered containers require an ordering function. I
could very easily just say "why would someone use a container that requires
a hashing function instead of one that does not?" but I wouldn't because
that would be just as flawed reasoning.

Anyway, even if we really were dealing with with a superset of
requirements, I don't buy that you should prefer the container that has
fewer requirements on principle. in practice, you usually want to do the
opposite and favor the implementation with more-strict requirements, since
that usually means for a more specialized implementation. This is because
the implementation can take advantage of more functionality and/or more
specific semantics. A good example of that for an algorithm is
std::advance, and for datastructures, see any datastructure that can take
advantage of triviality.

The thing is, absolutely none of this talk of requirements really applies
here, though, since as I pointed out, the ordered and unordered containers
are completely different datastructures and so comparison of their
requirements is misleading. In the case at hand, the types /can/ be
ordered, so whether or not those types have a /default/ order should have
no bearing on whether you use an ordered or unordered set. Both of those
choices are perfectly valid and the decision to choose one or the other has
nothing to do with defaults.

> Except that where this whole discussion began was where someone was using
> it unintentionally.  If it wasn't there (unless specifically requested),
> that wouldn't be an issue.
>

No, people were misusing /operators/ not std::less -- particularly the
mixed-type operators. We are not talking about operators here as I've tried
to restate in several replies just to be clear. We are talking about
default ordering for a type (I.E. specifying a std::less specialization or
some proposed std::order). Since we're on the topic now, though, at some
point a claim was made that the mixed-type comparisons can come about due
to there being implicit conversions and it derailed into removing the
homogeneous operators because of that. As I mentioned earlier, this
conversion issue isn't actually true since when you define your operator as
a template and you are not explicitly specifying a template argument when
invoking it (as few people would rarely do, unless perhaps they want such a
conversion), you will /not/ get the implicit conversion. That overload will
not be picked. If people were seeing such conversions, I assume that the
operators were defined as friend functions inline to the class. If that is
the only issue that people have, then simply changing the operators to be
templates and defining them outside of the class would fix that issue.

Perhaps your domain is different, but in my experience wanting to sort
> things (particularly in a single way) is the exception rather than the
> rule.  Requiring types to be internally sortable therefore seems like an
> unnecessary burden.
>

No, there is nothing different here and I agree entirely. You should always
minimize requirements. Perhaps what you're missing is that we're /not/
requiring anything at the container level (I.E. tuple or optional or
variant). The requirements are only on the ordering function. Your types do
not need to have a default order to put them in a std::vector or a
std::tuple or an optional or a variant. The ordering function is what has
the requirement, not the container itself. This has always been true in the
standard library with respect to the standard containers (it's even true
with respect to equality, not just ordering). If your contained types don't
have a well-defined < that provides a total order then the container type
doesn't have a well-defined order either and that's fine. For instance, you
can put stuff in a std::vector if it doesn't have a well-defined == or <.
If you choose to use the operators, that's another story, but that set of
requirements is separate from the container requirements.

> This is starting to get quite far afield from the original issue though.
> The fundamental point was that using op< on distinct types (in this case
> optional<T> and T) is more likely to be a bug than it is to be intentional
> code.

I agree that use is generally suspect.

>   My generalisation was that even op< on two optional<T>s is suspicious as
> some people don't seem to agree where "none" sorts, or even what "none"
> means in some cases -- and because others were arguing that it was
> inconsistent to define one op< without the other.
>

Here's where I tend to disagree (I'll go back to talking about order in
general, though, so that we don't get derailed regarding operators that
should or should not exist). Specifying ordering for any type at all is
always a subjective decision. If someone sees an order comparison with an
optional, no matter how that function is spelled, should that programmer A)
make an assumption about ordering and not look it up or B) look up the
ordering? Whether the function is spelled operator< or std::less or
std::order seems unimportant to me in that particular respect. In every one
of those cases the programmer would have to look up what the order is if
they wanted to use it in a specific way. Because of that, I don't think
it's a valid rationale to exclude the function. You always need to know
what any function does when you use it. A default ordering function isn't
particularly special.

> My further generalisation was that it's probably also a bug to try to
> order two variant<X,Y> where one was X and the other Y.  (Sure, there are
> occasions where it is useful to be able to do so.  But the programmer
> should do that explicitly rather than using op<, due to the principle of
> least surprise, and because the required sort order may be different in
> different contexts.)
>

Again, the required sort order being different in different contexts is
always true. This is not special to optional or variant or tuple or
anything else. It's true for integers just the same. So what? If the
default order is sensible for your use then use it. If it's not then don't
use it.

-- 
-Matt Calabrese