Re: [lmi] Unexpected gcc diagnostic

[Vadim Zeitlin]

On Sat, 10 Apr 2021 00:22:00 +0000 Greg Chicares <gchicares@sbcglobal.net> 
wrote:

GC> On 4/7/21 10:27 AM, Vadim Zeitlin wrote:
GC> > On Wed, 7 Apr 2021 10:00:19 +0000 Greg Chicares <gchicares@sbcglobal.net> 
wrote:
GC> > 
GC> > GC> On 4/6/21 6:59 PM, Greg Chicares wrote:
GC> [...]
GC> > GC> The question is when it's okay to dereference this iterator:
GC> > GC>   LowestBft = *std::min_element(Bfts.begin(), 
last_bft_in_test_period);
GC> > GC> The answer is not whenever
GC> > GC>   Bfts.begin() < last_bft_in_test_period
GC> > GC> but, rather, whenever both
GC> > GC>   Bfts.begin() < Bfts.end()               [the vector is not empty], 
and
GC> > GC>   Bfts.begin() <= last_bft_in_test_period [the range is not insane]
GC> > 
GC> >  IMO the answer is whenever either
GC> > 
GC> >   Bfts.begin() < last_bft_in_test_period
GC> > 
GC> > or
GC> > 
GC> >   last_bft_in_test_period < Bfts.end()
GC> > 
GC> > I.e., by construction of last_bft_in_test_period we know that
GC> > 
GC> >   Bfts.begin() ≤ last_bft_in_test_period ≤ Bfts.end()
GC> > 
GC> > and we need at least one of these inequalities to be strict and I would
GC> > assert that this is true.
GC> 
GC> Agreed.
GC> 
GC> What I did in commit 79741b1ed3d17 is similar, though not
GC> identical. The reason is that I wanted to add a !empty()
GC> conditional before every call to std::min_element(), here
GC> and elsewhere; and here, adding that is enough.

 FWIW I did see this commit and it indeed looks like the best thing to do
here, thanks.

GC> > GC> Maybe it's just the aftereffects of yesterday's surgery, but somehow
GC> > GC> it troubles me to think that we have different empty sets that have
GC> > GC> different minimums: if a≠b, then min [a,a) ≠ min [b,b) .
GC> > 
GC> >  I don't think it's correct to say that these sets have different 
minimums.
GC> > min_element() returns different iterators for them, but neither of these
GC> > iterators can be dereferenced, so the actual value of the minimum is the
GC> > same for both empty sets: undefined/undetermined/none.
GC> 
GC> #include <algorithm>
GC> #include <iostream>
GC> #include <vector>
GC> 
GC> int main(int, char*[])
GC> {
GC>     std::vector<int> v {1729};
GC>     std::cout << *std::min_element(v.begin(), v.begin()) << std::endl;
GC>     return 0;
GC> }
GC> 
GC> That's defined to print "1729\n".

 I think I finally see what you mean, thanks for the example. I still
disagree with your main statement however, because while you're, of course,
correct in claiming that the program above is well-formed and guaranteed to
output "1729", some of its assumptions are not made explicit here. In
particular, you can only dereference the returned iterator because you know
that it is always _strictly_ less than v.end() which is only the case when
the vector is not empty which is hidden in plain sight in the code above.

GC> Thus, C++ ranges are not always half-open intervals.

 So from the point of view of std::min_element() the range is still
half-open and actually empty. Its caller, however, possesses additional
information which allows it to extend this empty half-open range beyond its
right end.

 I.e. I think the confusion stems from the fact that you're conflating two
different ranges: the empty (and, of course, half-open) range inside
min_element() and a bigger (but still half-open) range outside it.

GC> Assume that this
GC>   (v.begin(), v.begin())
GC> (above) is a half-open interval. Then it has no minimum.

 This is true.

GC> But its minimum is 1729.

 This is true only with extra assumptions allowing to extend the range and
in this case you're not speaking about the range (v.begin(), v.begin()) any
longer but about a larger range containing it. Or, to put it more bluntly,
without extra assumptions this last statement is false.
 
GC> Therefore, C++ doesn't adhere strictly to the set-theoretic
GC> definitions. It treats a range with identical endpoints
GC> as a closed interval
GC>   [a,a]
GC> or, following
GC>    [alg.min.max/26] ("Returns last if first == last")
GC> exactly, as {a}.

 No, sorry, I completely disagree with this. It's perfectly fine, from
set-theoretic definition, to "return last if first == last". In fact, it's
the only correct thing to do. The only thing which is confusing here is
that you actually can dereference "last", but this has nothing to do with
std::min_element() or the standard library and is only due to the fact that
the code you call it from knows that the actual interval is strictly larger
than what you pass to std::min_element().

 But it is simply not correct to say that std::min_element() treats "[a,
b[" as "[a, b]" because in the latter case it would guarantee that you can
dereference the returned iterator when it's equal to "b", but in the
former, and actually happening, case it doesn't guarantee this.

GC> I had thought C++ iterator ranges were always half-open
GC> intervals.

 I still see nothing here impinging on this. The argument given seems
similar to saying that you can access N-th element of an array of size N
because you can pass an array of size M > N into the function doing it.


GC> That's not rigorously true. The [alg.min.max/26]
GC> behavior is reasonable, but it doesn't follow rigorously
GC> from set theory; rather, it's just a convention, like
GC> defining 0/0 to be zero, or one, as you please.

 No, again, I don't think this is true at all, sorry. This is not just a
convention, it's the only well-defined thing to do (the function simply
can't return anything else in this case) and it is perfectly compatible
with the half-open range convention.

 Regards,
VZ

pgphLppUOwqPp.pgp
Description: PGP signature