Using std::less_equl predicate with std::min()

[Vladimir Grigoriev]

When I use std::less_equal predicate with the std::min() algorithm (tu
change the order of returned elements in case they are equal) the Visual C++
2005 EE abort my program in the internal function

bool __CLRCALL_OR_CDECL _Debug_lt_pred()

reporting the following



_DEBUG_ERROR2("invalid operator<", _Where, _Line);

Is it correct behaviour of the compiler? Does the Standard forbid to use
std::less_equal with std::min?



Vladimir Grigoriev:

[Igor Tandetnik]

Post by Vladimir Grigoriev
When I use std::less_equal predicate with the std::min() algorithm

You can't. std::min requires its predicate to be a strict weak ordering. Among other things, it means !pred(a, a) (no element can be less than itself). <= is not a strict weak ordering.

STL implementation shipped with VC has a debug mode where it tries to detect this kind of violation. Indeed, it caught the problem in your case.

[Vladimir Grigoriev]

Thanks, Igor.

However logically it is not clear why for the std::min such strict
requirements are needed. For example, if I would want that in case of
equality the second argument of the std::min would be returned instead of
the first I could use the std::less_equal predicate.

Vladimir Grigoriev

Post by Vladimir Grigoriev
When I use std::less_equal predicate with the std::min() algorithm

You can't. std::min requires its predicate to be a strict weak ordering.
Among other things, it means !pred(a, a) (no element can be less than
itself). <= is not a strict weak ordering.

STL implementation shipped with VC has a debug mode where it tries to detect
this kind of violation. Indeed, it caught the problem in your case.

[Igor Tandetnik]

Post by Vladimir Grigoriev
However logically it is not clear why for the std::min such strict
requirements are needed. For example, if I would want that in case of
equality the second argument of the std::min would be returned
instead of the first I could use the std::less_equal predicate.

I don't quite see how this follows. Why exactly would you logically expect the algorithm to prefer the second argument in this case?

In any case, if you have a and b and you want the smallest of the two, but want b in case they are equal, why not just do std::min(b, a) ?

[Vladimir Grigoriev]

Post by Vladimir Grigoriev
However logically it is not clear why for the std::min such strict
requirements are needed. For example, if I would want that in case of
equality the second argument of the std::min would be returned
instead of the first I could use the std::less_equal predicate.

I don't quite see how this follows. Why exactly would you logically expect
the algorithm to prefer the second argument in this case?

It follows from the form of min

template <typename T, typename BinaryPredicate>
const T & min( const T &a, const T &b, BinaryPredicate pred )
{
return ( pred( b, a ) ? b : a );
}

I.e. in case of using the std::less_equal the predicate returns true if b
and a are equal and the std::min will return b indeed.
If it would be allowed I could change behaviour of the std::min on the fly.

In any case, if you have a and b and you want the smallest of the two, but
want b in case they are equal, why not just do std::min(b, a) ?

[Igor Tandetnik]

Post by Igor Tandetnik

Post by Vladimir Grigoriev
However logically it is not clear why for the std::min such strict
requirements are needed. For example, if I would want that in case of
equality the second argument of the std::min would be returned
instead of the first I could use the std::less_equal predicate.

I don't quite see how this follows. Why exactly would you logically
expect the algorithm to prefer the second argument in this case?
It follows from the form of min
template <typename T, typename BinaryPredicate>
const T & min( const T &a, const T &b, BinaryPredicate pred )
{
return ( pred( b, a ) ? b : a );
}

Ok, now imagine an official language in the standard that would capture this behavior:

min(a, b, comp): returns the smaller of a and b as defined by comp. If a and b are "equal" (that is, !comp(a, b) && !comp(b, a)), then returns a if comp is a less-than type of predicate, but b if it's less-than-or-equal type of predicate. Insert the formal definition of the two types here.

I suspect had you seen something like the above before you encountered your specific issue, you would be thinking: "What a mess! Whoever came up with this monstrosity?" And you'd be right.

If you really need the behavior described above, it should be trivial to write your own mymin() function the way you want it.

[Vladimir Grigoriev]

"Igor Tandetnik" <***@mvps.org> wrote in message news:uZER%***@TK2MSFTNGP05.phx.gbl...

Ok, now imagine an official language in the standard that would capture this
behavior:

min(a, b, comp): returns the smaller of a and b as defined by comp. If a and
b are "equal" (that is, !comp(a, b) && !comp(b, a)), then returns a if comp
is a less-than type of predicate, but b if it's less-than-or-equal type of
predicate. Insert the formal definition of the two types here.


I have imagined that! But I have formulated this another way. If a binary
predicate has value of true then 'b' is returned. Otherwise 'a' is
returned. So I do not see a problem. Moreover including std::less_equal into
std::min makes code readable and clear.

std::min( a, b, std::less_equal<T>() );

It is funny to note that the compiler allows to use std::greater instead of
std::less in the std::min in spite of that this looks strange.
Moreover I can show another example when applying std::less_equal is useful.
For example you want to find the last minimum element in a sequence. Then
you could use std::less_equal instead of std::less.

int a[] = { 6, 1, 7, 1, 8 };


int *p = std::min_element( a, a + sizeof( a ) / sizeof( *a ),

std::less_equal() );


In fact without any serious reason the Microsoft compiler prevents from
compiling of a valid code. In my opinion it is one mode serious bug of the
Microsoft compiler. I have not seen any reasonable explanation why this code
may not be compiled. It seems that Microsoft inserted this check everywhere
in its library without any thought about consequences

Vladimir Grigoriev.

[Ulrich Eckhardt]

Post by Vladimir Grigoriev
But I have formulated this another way. If a binary
predicate has value of true then 'b' is returned. Otherwise 'a' is
returned. So I do not see a problem. Moreover including std::less_equal
into std::min makes code readable and clear.
std::min( a, b, std::less_equal<T>() );
It is funny to note that the compiler allows to use std::greater instead
of std::less in the std::min in spite of that this looks strange.

Yes, strange indeed. However, it only gives you the first element according
to the given order. Using less in ascending order, otherwise descending
order.

Post by Vladimir Grigoriev
Moreover I can show another example when applying std::less_equal is
useful. For example you want to find the last minimum element in a
sequence. Then you could use std::less_equal instead of std::less.
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element( a, a + sizeof( a ) / sizeof( *a ),
std::less_equal() );

Use a reverse iterator to search from the end. All search functions return
the first match, not the last.

Post by Vladimir Grigoriev
In fact without any serious reason the Microsoft compiler prevents from
compiling of a valid code. In my opinion it is one mode serious bug of the
Microsoft compiler. I have not seen any reasonable explanation why this
code may not be compiled.

Look again, someone mentioned the C++ standard. ;)

Post by Vladimir Grigoriev
It seems that Microsoft inserted this check
everywhere in its library without any thought about consequences

Nope, the strict ordering comes from the C++ standard which in turn took it
from the STL. You're barking up the wrong tree. BTW: I'd ask this on
comp.lang.c++.moderated, you have typically more C++ experts there.

Uli

[Vladimir Grigoriev]

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
But I have formulated this another way. If a binary
predicate has value of true then 'b' is returned. Otherwise 'a' is
returned. So I do not see a problem. Moreover including std::less_equal
into std::min makes code readable and clear.
std::min( a, b, std::less_equal<T>() );
It is funny to note that the compiler allows to use std::greater instead
of std::less in the std::min in spite of that this looks strange.

Yes, strange indeed. However, it only gives you the first element according
to the given order. Using less in ascending order, otherwise descending
order.

Yes, using std::greater reverse std::min to std::max and std::max to
std::min. It is funny but it is an interesting possibility. However using
std::less_equal looks more natural with using std::min than using for
example std::greater with std::min.

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
Moreover I can show another example when applying std::less_equal is
useful. For example you want to find the last minimum element in a
sequence. Then you could use std::less_equal instead of std::less.
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element( a, a + sizeof( a ) / sizeof( *a ),
std::less_equal() );

Use a reverse iterator to search from the end. All search functions return
the first match, not the last.

How to use reverse iterators with arrays?

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
In fact without any serious reason the Microsoft compiler prevents from
compiling of a valid code. In my opinion it is one mode serious bug of the
Microsoft compiler. I have not seen any reasonable explanation why this
code may not be compiled.

Look again, someone mentioned the C++ standard. ;)

Post by Vladimir Grigoriev
It seems that Microsoft inserted this check
everywhere in its library without any thought about consequences

Nope, the strict ordering comes from the C++ standard which in turn took it
from the STL. You're barking up the wrong tree. BTW: I'd ask this on
comp.lang.c++.moderated, you have typically more C++ experts there.

Yes, I do not know the standard but I think that strict ordering requirments
is applied not to all algorithms. Otherwise the existence of std::less_equal
and std::greater_equal in C++ have no any greate sense.

Vladimir Grigoriev

[Vladimir Grigoriev]

"Vladimir Grigoriev" <***@mail.ru> wrote in message news:***@TK2MSFTNGP06.phx.gbl...
Otherwise the existence of std::less_equal

Post by Vladimir Grigoriev
and std::greater_equal in C++ have no any greate sense.
Vladimir Grigoriev

If to follow the logic it means that in fact the std::less_equal and
std::greater_equal themselves contradict the requirement of the standard and
should be excluded from the standard!:)

Vladimir Grigoriev

[Igor Tandetnik]

Post by Vladimir Grigoriev
Otherwise the existence of std::less_equal

Post by Vladimir Grigoriev
and std::greater_equal in C++ have no any greate sense.
Vladimir Grigoriev

If to follow the logic it means that in fact the std::less_equal and
std::greater_equal themselves contradict the requirement of the standard and
should be excluded from the standard!:)

No, that doesn't follow at all. The standard doesn't require that every binary predicate in existence must be a strict weak ordering. It says that certain algorithms should only be invoked with predicates that are strict weak orderings (and thus cannot be called with less_equal or greater_equal).

[Vladimir Grigoriev]

Igor,
Do you mean that according to the standard std::min and std::min_element are
among those algorithms?
And one more question: is weak ordering the same as partial ordering in
mathematics (usually this term can be often met in mathematics)?

"Igor Tandetnik" <***@mvps.org> wrote in message news:***@TK2MSFTNGP06.phx.gbl...
No, that doesn't follow at all. The standard doesn't require that every
binary predicate in existence must be a strict weak ordering. It says that
certain algorithms should only be invoked with predicates that are strict
weak orderings (and thus cannot be called with less_equal or greater_equal).

[Igor Tandetnik]

Post by Vladimir Grigoriev
Do you mean that according to the standard std::min and std::min_element are
among those algorithms?

Yes I do.

Post by Vladimir Grigoriev
And one more question: is weak ordering the same as partial ordering in
mathematics (usually this term can be often met in mathematics)?

No, it's stronger than partial ordering (but weaker than total ordering). The precise definition can be found in 25.3p4 in C++98.

[Igor Tandetnik]

Post by Vladimir Grigoriev

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element( a, a + sizeof( a ) / sizeof( *a ),
std::less_equal() );

Use a reverse iterator to search from the end. All search functions return
the first match, not the last.

How to use reverse iterators with arrays?

typedef std::reverse_iterator<int*> rev_it;
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element(
rev_it(a + sizeof( a ) / sizeof( *a )), rev_it(a), std::less() ).base();

Post by Vladimir Grigoriev

Post by Ulrich Eckhardt
Nope, the strict ordering comes from the C++ standard which in turn took it
from the STL. You're barking up the wrong tree. BTW: I'd ask this on
comp.lang.c++.moderated, you have typically more C++ experts there.

Yes, I do not know the standard

You can get a copy of C++98 here:

http://www-d0.fnal.gov/~dladams/cxx_standard.pdf

C++03 here:
http://openassist.googlecode.com/files/C%2B%2B%20Standard%20-%20ANSI%20ISO%20IEC%2014882%202003.pdf

and the most recent draft of C++0x here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n3000.pdf

Post by Vladimir Grigoriev
but I think that strict ordering requirments
is applied not to all algorithms.

Perhaps, but it does apply to std::min and std::min_element.

[Vladimir Grigoriev]

Thanks, Igor.
This is very useful information. I did not even know till now that I can use
reverse iterators directly without their connection with containers.
However in your example p points to 8. So I need to do additional
manipulations with the reverse iterator to get correct pointer. With using
std::less_equal directly in the std::min_element I have not such
difficulties and can use raw integer pointer directly.:)
Why to make things complicated when a direct simple method may be used?

Vladimir Grigoriev

Post by Vladimir Grigoriev

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element( a, a + sizeof( a ) / sizeof( *a ),
std::less_equal() );

Use a reverse iterator to search from the end. All search functions return
the first match, not the last.

How to use reverse iterators with arrays?

typedef std::reverse_iterator<int*> rev_it;
int a[] = { 6, 1, 7, 1, 8 };
int *p = std::min_element(
rev_it(a + sizeof( a ) / sizeof( *a )), rev_it(a), std::less() ).base();

Post by Vladimir Grigoriev

Post by Ulrich Eckhardt
Nope, the strict ordering comes from the C++ standard which in turn took it
from the STL. You're barking up the wrong tree. BTW: I'd ask this on
comp.lang.c++.moderated, you have typically more C++ experts there.

Yes, I do not know the standard

You can get a copy of C++98 here:

http://www-d0.fnal.gov/~dladams/cxx_standard.pdf

C++03 here:
http://openassist.googlecode.com/files/C%2B%2B%20Standard%20-%20ANSI%20ISO%20IEC%2014882%202003.pdf

and the most recent draft of C++0x here:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n3000.pdf

Post by Vladimir Grigoriev
but I think that strict ordering requirments
is applied not to all algorithms.

Perhaps, but it does apply to std::min and std::min_element.

[Igor Tandetnik]

Post by Vladimir Grigoriev
This is very useful information. I did not even know till now that I can use
reverse iterators directly without their connection with containers.
However in your example p points to 8.

Yes, I guess I need min_element(...).base() - 1. I haven't actually tested this.

Post by Vladimir Grigoriev
So I need to do additional
manipulations with the reverse iterator to get correct pointer. With using
std::less_equal directly in the std::min_element I have not such
difficulties

Other than the fact that your code exhibits undefined behavior, that is.

[Igor Tandetnik]

Post by Vladimir Grigoriev
In fact without any serious reason the Microsoft compiler prevents from
compiling of a valid code.

Yours is not a valid code, it exhibits undefined behavior. The C++ standard requires that the predicate be a strict weak ordering, and less_equal isn't.

Post by Vladimir Grigoriev
In my opinion it is one mode serious bug of the
Microsoft compiler.

It's not a bug, it's a feature.

Post by Vladimir Grigoriev
I have not seen any reasonable explanation why this code
may not be compiled.

To be precise, it compiled - it failed at run time. Anyway, MSVC's STL implementation is doing you a favor by turning an instance of undefined behavior into a hard error, so you can find and fix your bug more easily.

Post by Vladimir Grigoriev
It seems that Microsoft inserted this check everywhere
in its library without any thought about consequences

No - it inserted this check _because_ it thought about consequences.

[Vladimir Grigoriev]

Igor, in context of what you have said I do not understand existence of
std::less_equal and std::greater_equal in C++. If I may not to use them with
algorithms why do they exist? And I do not see any reasonable explanation
why they may not be used for example in std::min or in std::min_element.

Vladimir Grigoriev
.

Post by Vladimir Grigoriev
In fact without any serious reason the Microsoft compiler prevents from
compiling of a valid code.

Yours is not a valid code, it exhibits undefined behavior. The C++ standard
requires that the predicate be a strict weak ordering, and less_equal isn't.

Post by Vladimir Grigoriev
In my opinion it is one mode serious bug of the
Microsoft compiler.

It's not a bug, it's a feature.

Post by Vladimir Grigoriev
I have not seen any reasonable explanation why this code
may not be compiled.

To be precise, it compiled - it failed at run time. Anyway, MSVC's STL
implementation is doing you a favor by turning an instance of undefined
behavior into a hard error, so you can find and fix your bug more easily.

Post by Vladimir Grigoriev
It seems that Microsoft inserted this check everywhere
in its library without any thought about consequences

No - it inserted this check _because_ it thought about consequences.

[Jeff Flinn]

Post by Vladimir Grigoriev
Igor, in context of what you have said I do not understand existence of
std::less_equal and std::greater_equal in C++. If I may not to use them with
algorithms why do they exist? And I do not see any reasonable explanation
why they may not be used for example in std::min or in std::min_element.

They certainly are usable with algorithms not requiring strict weak
ordering such as std::find_if.

Jeff

[Vladimir Grigoriev]

Jeff, it seems that apart from the code itself of an algorithm one must know
also much additional information to use the code.:)

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

Vladimir Grigoriev

Post by Jeff Flinn

Post by Vladimir Grigoriev
Igor, in context of what you have said I do not understand existence of
std::less_equal and std::greater_equal in C++. If I may not to use them
with algorithms why do they exist? And I do not see any reasonable
explanation why they may not be used for example in std::min or in
std::min_element.

They certainly are usable with algorithms not requiring strict weak
ordering such as std::find_if.
Jeff

[Igor Tandetnik]

Post by Vladimir Grigoriev
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.

Post by Vladimir Grigoriev
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.

[Vladimir Grigoriev]

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

Post by Vladimir Grigoriev
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.

Post by Vladimir Grigoriev
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.

[Stephen Howe]

Post by Vladimir Grigoriev
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

it is oversights sometimes. Some snippets:

1) We can now guarantee that std::sort() can always do O(N * log N) (written using introsort - Dave Musser)

2) I think the requirements of std::stable_sort() are too strict, bidirectional iterators are all that is required.

3) Likewise std::stable_partition() and std::partition() can be implemented using Forward Iterators, therefore the requirements
are too severe.

4) The wording in C++0x for std::lower_bound(), std:upper_bound() & std::equal_range() is changing to make it clear that
assymetrical < operators can be used.

Stephen Howe

[Stephan T. Lavavej [MSFT]]

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).
return pred(x, y) ? x : y; works for std::less_equal but not for std::less.
And there's no way to tell at compiletime whether an arbitrary predicate
will behave like std::less or std::less_equal. (Requiring an annotation
would complicate the Standard, STL implementations, and user
implementations, for no benefit.)

Unless I'm confusing myself, return pred(x, y) ? x : pred(y, x) ? y : x
would work for both std::less-like and std::less_equal-like predicates. But
that would be lethal to performance.

This is why the STL standardized on requiring std::less-like predicates for
min/max and sorting.

Stephan T. Lavavej
Visual C++ Libraries Developer

Post by Vladimir Grigoriev
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

Post by Vladimir Grigoriev
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.

Post by Vladimir Grigoriev
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

[Igor Tandetnik]

Post by Stephan T. Lavavej [MSFT]
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
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.

[Stephan T. Lavavej [MSFT]]

Post by Igor Tandetnik
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

Post by Igor Tandetnik
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
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.

[Vladimir Grigoriev]

Post by Stephan T. Lavavej [MSFT]

Post by Igor Tandetnik
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.

I do not see here any problem. He may use the min as he are going to use it.
What is the problem?

Post by Stephan T. Lavavej [MSFT]
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.

Does sort uses the min algorithm? And one more it is your choice how you are
going to sort your sequence. Nobody to fource you to use the less_equal
predicate? Bu its using gives new opportunities.

Vladimir Grigoriev

[Bo Persson]

Post by Igor Tandetnik

Post by Stephan T. Lavavej [MSFT]
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

[Vladimir Grigoriev]

"Igor Tandetnik" <***@mvps.org> wrote in message news:%***@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

[Vladimir Grigoriev]

Sorry, I have not seen why I can not use the less_equal for min. If I use
the less_equal I do that intestinally for example to get the second argument
in the case of arguments equality. No annotation in the Standard is
required. It is enough that the min may use a predicate. It a user choice
which predicate to use in his code.

Vladimir Grigoriev

Post by Stephan T. Lavavej [MSFT]
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). return pred(x, y) ? x : y; works for std::less_equal but not for
std::less. And there's no way to tell at compiletime whether an arbitrary
predicate will behave like std::less or std::less_equal. (Requiring an
annotation would complicate the Standard, STL implementations, and user
implementations, for no benefit.)
Unless I'm confusing myself, return pred(x, y) ? x : pred(y, x) ? y : x
would work for both std::less-like and std::less_equal-like predicates.
But that would be lethal to performance.
This is why the STL standardized on requiring std::less-like predicates
for min/max and sorting.
Stephan T. Lavavej
Visual C++ Libraries Developer

Post by Vladimir Grigoriev
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

Post by Vladimir Grigoriev
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.

Post by Vladimir Grigoriev
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

[Ulrich Eckhardt]

Post by Vladimir Grigoriev
Sorry, I have not seen why I can not use the less_equal for min.

...because the standard says that it requires a strict-weak ordering as
predicate?

Post by Vladimir Grigoriev
If I use the less_equal I do that intestinally for example to get the
second argument in the case of arguments equality.

The standard allows use of greater for max, maybe that could help you
achieve what you want in a conforming way?

Post by Vladimir Grigoriev
No annotation in the Standard is required. It is enough that the min
may use a predicate. It a user choice which predicate to use in his
code.

So what? You say the standard imposes requirements that aren't actually
necessary. File a defect report with the C++ standards committee then, but
don't say implementations should support your code that is - according to
the standard - broken.

I don't understand why this issue is still being discussed here, all points
above (except perhaps the greater/max suggestion) were already mentioned
here.

Uli

[TOFU removed]

[Vladimir Grigoriev]

Thanks, Ulrich.

I know already what the Standard says relative the std::min, however I do
not see any reasonable explanation of why it says so.

Vladimir Grigoriev

Post by Ulrich Eckhardt

Post by Vladimir Grigoriev
Sorry, I have not seen why I can not use the less_equal for min.

...because the standard says that it requires a strict-weak ordering as
predicate?

Post by Vladimir Grigoriev
If I use the less_equal I do that intestinally for example to get the
second argument in the case of arguments equality.

The standard allows use of greater for max, maybe that could help you
achieve what you want in a conforming way?

Post by Vladimir Grigoriev
No annotation in the Standard is required. It is enough that the min
may use a predicate. It a user choice which predicate to use in his
code.

So what? You say the standard imposes requirements that aren't actually
necessary. File a defect report with the C++ standards committee then, but
don't say implementations should support your code that is - according to
the standard - broken.
I don't understand why this issue is still being discussed here, all points
above (except perhaps the greater/max suggestion) were already mentioned
here.
Uli
[TOFU removed]
--
C++ FAQ: http://parashift.com/c++-faq-lite
Sator Laser GmbH
Geschaftsfuhrer: Thorsten Focking, Amtsgericht Hamburg HR B62 932

[Igor Tandetnik]

Post by Vladimir Grigoriev
Igor, in context of what you have said I do not understand existence of
std::less_equal and std::greater_equal in C++.

Here's an example that uses less_equal:

http://www.cplusplus.com/reference/std/functional/less_equal/

Post by Vladimir Grigoriev
If I may not to use them with algorithms why do they exist?

You cannot use them with _some_ algorithms, but can with others.

Post by Vladimir Grigoriev
And I do not see any reasonable explanation
why they may not be used for example in std::min or in std::min_element.

Suppose we want to relax the specification, and not require strict weak ordering. On the other hand, you can't just allow any odd predicate: at the very least, you would need transitivity (otherwise, if a < b and b < c and c < a, which of the three is smallest? ) So now you have to think of the minimal set of requirements, and define a new class of predicates just for min/max family of algorithms. Yes, it's all possible - but is it worth the trouble? What precisely do you gain from this added complexity that you can't achieve by other means?

In any case, if you feel strongly about it, please feel free to submit a formal proposal to the C++ standardization committee.