Prev: volatile keyword and memory barriers
Next: Can not deduse template arguments std::rel_ops
From: Vladimir Grigoriev on 12 Jan 2010 10:48
Well, I can conclude that in fact there is no a reason to prevent to use
std::less_equal with std::min or std::min_element. The standard forbid its
using however I do not see an explanation of the reason.

Vladimir Grigoriev

"Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message
news:uWSEPc5kKHA.2132(a)TK2MSFTNGP05.phx.gbl...
Vladimir Grigoriev wrote:
> Jeff, it seems that apart from the code itself of an algorithm one must
> know
> also much additional information to use the code.:)

This is the case for any function in any library: you must know and satisfy
the function's prerequisites when calling it.

> However as for find_if it uses a comparison operator/predicate. So with
> find_if there is no such problem.

Which is precisely the point: less_than is usable with some, but not all,
algorithms.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not necessarily
a good idea. It is hard to be sure where they are going to land, and it
could be dangerous sitting under them as they fly overhead. -- RFC 1925


From: Igor Tandetnik on 15 Jan 2010 17:01
Stephan T. Lavavej [MSFT] <stl(a)microsoft.com> wrote:
> There's a fundamental reason.
>
> #1: When x is "smaller" than y, min(x, y) is required to return x.
> #2: When x is "equivalent" to y, min(x, y) is required to return x.
> #3: When x is "larger" than y, min(x, y) is required to return y.
>
> For std::less-like predicates, there's a very simple implementation
> that achieves this: return y < x ? y : x; and return pred(y, x) ? y :
> x; for the generalized implementation.
>
> Now suppose that min() allowed std::less_equal-like predicates.
> return pred(y, x) ? y : x; doesn't work for std::less_equal (it
> returns y for #2).

Ah, but Vladimir _wants_ it to return y for #2. He wants to use less_equal specifically for this purpose, trying to take advantage of an implementation detail. His complaint is about the debugging feature in MSVC STL implementation whereby less_equal is explicitly checked for and rejected (well, not specifically less_equal, but any predicate that violates strict weak ordering requirements).

Basically, his argument is that, instead of mandating that min() return the smaller of the two elements, the standard should have just stated that min(x, y, pred) returns (pred(y, x) ? y : x). Then std::less and std::less_equal would behave the way he wants (but not necessarily the way that obeys the principle of least surprise).

It's not quite clear how min_element should be specified in this new world, nor what restrictions should be placed on the predicate passed to it.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not necessarily a good idea. It is hard to be sure where they are going to land, and it could be dangerous sitting under them as they fly overhead. -- RFC 1925

From: Stephan T. Lavavej [MSFT] on 15 Jan 2010 18:49
> Ah, but Vladimir _wants_ it to return y for #2.

Then Anti-Vladimir would complain that #2 should return x, because returning
the first of two equivalent arguments is the natural choice. It's "stable"
in the sense of stable_sort(), which preserves the relative order of
equivalent elements.

The Standard's opinion is that Anti-Vladimir has the more powerful argument.
sort() had to choose between accepting std::less-like and
std::less_equal-like predicates (because it has to know when elements are
equivalent, and my previous reply explained why determining equivalency
without knowing whether the predicate is std::less-like or
std::less_equal-like without compromising performance is impossible). It
chose std::less due to simplicity. Therefore, requiring std::less-like
predicates for min/max is very simple to explain, and unsurprising once
you've learned sort()'s convention.

There are problems in the Standard but this is not one of them.

STL

"Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message
news:%23wNHV5ilKHA.5128(a)TK2MSFTNGP05.phx.gbl...
Stephan T. Lavavej [MSFT] <stl(a)microsoft.com> wrote:
> There's a fundamental reason.
>
> #1: When x is "smaller" than y, min(x, y) is required to return x.
> #2: When x is "equivalent" to y, min(x, y) is required to return x.
> #3: When x is "larger" than y, min(x, y) is required to return y.
>
> For std::less-like predicates, there's a very simple implementation
> that achieves this: return y < x ? y : x; and return pred(y, x) ? y :
> x; for the generalized implementation.
>
> Now suppose that min() allowed std::less_equal-like predicates.
> return pred(y, x) ? y : x; doesn't work for std::less_equal (it
> returns y for #2).

Ah, but Vladimir _wants_ it to return y for #2. He wants to use less_equal
specifically for this purpose, trying to take advantage of an implementation
detail. His complaint is about the debugging feature in MSVC STL
implementation whereby less_equal is explicitly checked for and rejected
(well, not specifically less_equal, but any predicate that violates strict
weak ordering requirements).

Basically, his argument is that, instead of mandating that min() return the
smaller of the two elements, the standard should have just stated that
min(x, y, pred) returns (pred(y, x) ? y : x). Then std::less and
std::less_equal would behave the way he wants (but not necessarily the way
that obeys the principle of least surprise).

It's not quite clear how min_element should be specified in this new world,
nor what restrictions should be placed on the predicate passed to it.
--
With best wishes,
Igor Tandetnik

With sufficient thrust, pigs fly just fine. However, this is not necessarily
a good idea. It is hard to be sure where they are going to land, and it
could be dangerous sitting under them as they fly overhead. -- RFC 1925

From: Bo Persson on 15 Jan 2010 21:12
Igor Tandetnik wrote:
> Stephan T. Lavavej [MSFT] <stl(a)microsoft.com> wrote:
>> There's a fundamental reason.
>>
>> #1: When x is "smaller" than y, min(x, y) is required to return x.
>> #2: When x is "equivalent" to y, min(x, y) is required to return x.
>> #3: When x is "larger" than y, min(x, y) is required to return y.
>>
>> For std::less-like predicates, there's a very simple implementation
>> that achieves this: return y < x ? y : x; and return pred(y, x) ?
>> y : x; for the generalized implementation.
>>
>> Now suppose that min() allowed std::less_equal-like predicates.
>> return pred(y, x) ? y : x; doesn't work for std::less_equal (it
>> returns y for #2).
>
> Ah, but Vladimir _wants_ it to return y for #2. He wants to use
> less_equal specifically for this purpose, trying to take advantage
> of an implementation detail. His complaint is about the debugging
> feature in MSVC STL implementation whereby less_equal is explicitly
> checked for and rejected (well, not specifically less_equal, but
> any predicate that violates strict weak ordering requirements).
>
> Basically, his argument is that, instead of mandating that min()
> return the smaller of the two elements, the standard should have
> just stated that min(x, y, pred) returns (pred(y, x) ? y : x). Then
> std::less and std::less_equal would behave the way he wants (but
> not necessarily the way that obeys the principle of least
> surprise).
>

The problem with this is that he wants the standard to specify
implementation details, instead of the required result. Had it done
that for std::sort, we would have had quicksort forever and made
introsort impossible.

Therefore the standard tries to avoid specifying coding details.


Bo Persson


From: Vladimir Grigoriev on 20 Jan 2010 11:26

"Igor Tandetnik" <itandetnik(a)mvps.org> wrote in message
news:%23wNHV5ilKHA.5128(a)TK2MSFTNGP05.phx.gbl...

It's not quite clear how min_element should be specified in this new world,
nor what restrictions should be placed on the predicate passed to it.


As for me there is nothing unclear! For example if you use the less_equal
predicate with the min_element you will get the last minimum element in a
sequence. It is very useful behavior. One more it is a choice of the user.

Vladimir Grigoriev


First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: volatile keyword and memory barriers
Next: Can not deduse template arguments std::rel_ops