min and max running values

[Kai-Uwe Bux]

Sure3, if that's what the application's design requires. But since we
don't have a design specification, it's not possible to choose the most
appropriate approach.

You are misunderstanding my point. What I argued is actually quite
independent of any particular application. I maintain that the definitions
above are _natural_ and not arbitrary as they may seem at first glance.
Insofar as your criticism of the implementation proposed up-thread is based
upon the assumption that the implementation uses arbitrary, unmotivated
magic numbers, it is ill-founded. Quite contrary, the proposed return
values for an empty sequence are perfectly natural. They have exactly the
properties that one should expect. Moreover, no other possible return value
has those properties.

You are, however, right that it may depend on the specifics of the
application, whether an implementation with undefined behavior could have
an advantage compared to an implementation based upon the above proposal
(e.g., performance-wise). On the other hand, I doubt that I will see an
application where the undefined behavior solution is superior any time
soon.


Best

Kai-Uwe Bux

 

[Clark Cox]

Yes, because min_element takes iterators and follows the conventions of
STL algorithms. There are other ways to design functions, and in the
absence of any requirements, it's not possible to decide whether one
approach is better than another.

Indeed, so saying that "asking for the minimum of no values is not a
sensible request" isn't sensible

 

[Pete Becker]

You are misunderstanding my point. What I argued is actually quite
independent of any particular application. I maintain that the definitions
above are _natural_ and not arbitrary as they may seem at first glance.

You are putting words in my mouth. I didn't say they were arbitrary,
just that they weren't necessarily the best possible solution for all cases.

Insofar as your criticism of the implementation proposed up-thread is based
upon the assumption that the implementation uses arbitrary, unmotivated
magic numbers, it is ill-founded. Quite contrary, the proposed return
values for an empty sequence are perfectly natural. They have exactly the
properties that one should expect. Moreover, no other possible return value
has those properties.

You are, however, right that it may depend on the specifics of the
application, whether an implementation with undefined behavior could have
an advantage compared to an implementation based upon the above proposal
(e.g., performance-wise). On the other hand, I doubt that I will see an
application where the undefined behavior solution is superior any time
soon.

You are misunderstanding my point, which was about designing in a
vacuum. Don't do it. If you don't know exactly what the requirements
are, you cannot choose among various possible solutions. So the
assertion that my original suggestion was somehow inferior or misguided
has no sound basis.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Pete Becker]

Indeed, so saying that "asking for the minimum of no values is not a
sensible request" isn't sensible

It depends on the context, a concept that seems to be hard for most
participants in this thread to grasp.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Kai-Uwe Bux]

You are putting words in my mouth. I didn't say they were arbitrary,
just that they weren't necessarily the best possible solution for all
cases.

You said they are "artificial":

std::min_element is a good example of a context where the most
straightforward implementation doesn't use an artificial minimum value.

(elsethread, contrasting std::min_element with the proposed implementation
up-thread)


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

It depends on the context, a concept that seems to be hard for most
participants in this thread to grasp.

Where is the context qualification in your statement:

After all, asking for the minimum of no values is not a sensible request.

Your statement did not read:

asking for the minimum of no values is not always a sensible request.


Best

Kai-Uwe Bux

 

[Pete Becker]

You said they are "artificial":

Yes. "Artificial" is not "arbitrary".

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Pete Becker]

Where is the context qualification in your statement:


Your statement did not read:

asking for the minimum of no values is not always a sensible request.

Sigh. The context was all of the quoted material.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Kai-Uwe Bux]

Yes. "Artificial" is not "arbitrary".

True, and your point is taken.

However, "artificial" is the opposite of "natural". I argued there are
natural return values for these cases. If you consider them artificial,
then that still is a point of disagreement.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

Sigh. The context was all of the quoted material.

I feel, now you are using the word "context" in two different meanings:

(a) in the line

"It depends on the context, a concept that seems to be hard for most
participants in this thread to grasp."

I understood you to refer to the particular target application.

(b) In the line

"The context was all of the quoted material."

you seem to refer to the context of your statement within this thread.

Should I have misunderstood you, I apologize.


In any case, I still don't buy your claim that "asking for the minimum of no
values is not a sensible request." I don't see that the context of the
quoted material provided any reason to interpret that statement as a modest
claim that _sometimes_ asking for such a value is not sensible. I still
think the only possible reading is that such a request is _never_ sensible.
If you meant the former you could have saved a lot of bandwith if you had
qualified the claim accordingly.

To me, it appears that you started with strong, unqualified, and quite
general statements:

But it's also reasonable to simply say that calling a
function that returns the minimum value in a range of values with an
empty range produces undefined behavior.

Note that this does _not: say "depending on the application, it may also be
reasonable to simply say ...". Instead it makes a quite general statement
that simply introducing undefined behavior for this case is also a
reasonable option. Since the claim is not further qualified, the standard
interpretation is that this option is always or at least generally
reasonable. The rational for this advice is also worded quite general:

After all, asking for the minimum of no values is not a sensible request.

Again, no restrictions are mentioned. So, we still have no reason to
interpret these statements in a weak or restricted way.

Later, you reverted to the position that all depends on the specs of the
particular application. That is quite different from how you started and
does not provide any justification for the claims you actually made. It
argues much weaker claims (essentially it argues existence statements where
universal statements were made). Maybe, I am misreading your claims, but I
feel its just the way they are worded that makes me read them the way I do.


Best

Kai-Uwe Bux

 

[Pete Becker]

However, "artificial" is the opposite of "natural". I argued there are
natural return values for these cases.

With such a return value, how does the caller distinguish between a
value that means that there were no elements, and the same value being
the actual minimum?

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Victor Bazarov]

With such a return value, how does the caller distinguish between a
value that means that there were no elements, and the same value being
the actual minimum?

When a single value is returned, there is no way. When two values are
expected (however it's done), it's easy to judge: min > max. *If* the
search for min and max is wrapped into a function, we can discuss the
design of that function, if you'd like.

V

 

[Pete Becker]

When a single value is returned, there is no way. When two values are
expected (however it's done), it's easy to judge: min > max. *If* the
search for min and max is wrapped into a function, we can discuss the
design of that function, if you'd like.

No, thanks, I understand it quite well. But it wasn't the original
question, despite having far too many words devoted to it.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Kai-Uwe Bux]

With such a return value, how does the caller distinguish between a
value that means that there were no elements, and the same value being
the actual minimum?

For an empty sequence, the returned value _is_ the _actual minimum_ (by the
proposed definition), in the very same way that 0 is the actual value of an
empty sum and 1 is the actual value of an empty product.

In general, the minimum of a sequence does not tell you anything about its
length. Why would you expect/want it to tell you that the sequence was
non-empty? _If_ the caller wants to know whether an empty sequence was
passed, the caller can check that by comparing the two iterators defining
the range (assuming that the signature reads something like:

template < typename IntIter >
int min_value ( IntIter from, IntIter to );

A difference between an implementation that introduces undefined behavior
for from==to and an implementation that does not is that the former
requires you to (a) always check unless you can prove from!=to and (b)
perform the check before the call. An implementation not introducing
undefined behavior allows you to skip the check in cases you don't need to
care whether the range is empty (a natural return value may very well
eliminate the necessity for such a check), and even if you need to know you
can check after the call to min_value at your convenience.


Best

Kai-Uwe Bux

 

[Pete Becker]

However, "artificial" is the opposite of "natural". I argued there are
natural return values for these cases. If you consider them artificial,
then that still is a point of disagreement.

"Natural" means "existing in or caused by nature; not made or caused by
humankind." Isn't numeric_limits<int>::min() made by humankind? Or are
we both using words a bit loosely, in order to convey meaning more clearly?

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Pete Becker]

For an empty sequence, the returned value _is_ the _actual minimum_ (by the
proposed definition), in the very same way that 0 is the actual value of an
empty sum and 1 is the actual value of an empty product.

No, they're not the same. The sum and the product of a sequence are
statements about the cumulative effect of an operation. The minimum
value in a set is a statement about a particular value, and if that
value isn't present in the set then there's something mighty fishy about
calling it the minimum value.

In general, the minimum of a sequence does not tell you anything about its
length. Why would you expect/want it to tell you that the sequence was
non-empty?

I don't want it to. Asking for the minimum value of an empty sequence is
meaningless, and returning a value that masquerades as an element of
that sequence doesn't make it meaningful. If you've got a set<int> and
you look for its minimum value, you ought to be able to find that value
in the set. That's not the case for sum and product.

_If_ the caller wants to know whether an empty sequence was

passed, the caller can check that by comparing the two iterators defining
the range (assuming that the signature reads something like:

template < typename IntIter >
int min_value ( IntIter from, IntIter to );

Or, even better, don't pretend that there's a value. Do what min_range
does, and return an iterator to the value, with end-of-sequence
designating that there was no minimum (i.e. the sequence was empty).

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Pete Becker]

No, they're not the same. The sum and the product of a sequence are
statements about the cumulative effect of an operation. The minimum
value in a set is a statement about a particular value, and if that
value isn't present in the set then there's something mighty fishy about
calling it the minimum value.

To put that a little more clearly: for a non-empty set, the sum and the
product of the elements is not necessarily a member of the set. The
minimum, on the other hand, is always a member of that set.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

 

[Kai-Uwe Bux]

"Natural" means "existing in or caused by nature; not made or caused by
humankind." Isn't numeric_limits<int>::min() made by humankind?

Well, numeric_limits<int>::min() is made by man. However, that it is the
natural / right / non-artificial <g> / ... choice for

int max_value ( int* from, int* to );

to return is not really that dependent on man. Whenever you have a partially
ordered set (such as the possible values of type int), its maximum element,
should it have one, is the right / natural / canonical / most convenient
minimum value of the empty sequence of elements. It is the only choice that
makes certain formula hold in general (i.e., without the need of treating
the empty sequence separately). To some degree, it is of course a
convention (as is any definition). However, as often in mathematics, there
are better and worse conventions. It just proves very useful to define
empty sums, products, min, max, union, and intersection accordingly so that
theorems just come out right and can be stated in full generality. That's
why it feels so natural to do that.

As for programming, I would go with the same convention because I would
expect that there are cases where the right return value will eliminate the
need for extra code handling the empty sequence case separately. Whether
that holds in a particular application, depends of course on the specs. You
are right in that regard.


However, if I had to design a _library_ version of max_value(), I would go
with the math-inspired convention. I.e., I would prefer something like

template < typename T >
struct find_min {

T const & operator() ( T const & lhs, T const & rhs ) const {
return ( std::min( lhs, rhs ) );
}

};

template < typename IntIter >
typename std::iterator_traits< IntIter >::value_type
min_value_a ( IntIter from, IntIter to ) {
typedef typename std::iterator_traits< IntIter >::value_type value_type;
return
( std::accumulate( from, to,
std::numeric_limits< value_type >::max(),
find_min<value_type>() ) );
}

to

template < typename IntIter >
typename std::iterator_traits< IntIter >::value_type
min_value_b ( IntIter from, IntIter to ) {
return ( *min_element( from, to ) );
}

An additional reason is that I tend to avoid introducing undefined behavior
in library code unless there is a clear performance rational to do so.

I agree that the version a only applies to arithmetic types. Now, I would
consider that a GoodThing(tm) since in general there might be no maximum
value for a given type, in which case min_value() does indeed not allow for
a meaningful return value when confronted with an empty sequence. In those
cases, I would recommend min_element() anyway.

Or are we both using words a bit loosely, in order to convey meaning more
clearly?

That is very likely. At least, I plead guilty to that charge. I would
contend, there is nothing wrong with that as long as one is prepared to
work things out in the case of miscommunication.


Best

Kai-Uwe Bux

 

[Kai-Uwe Bux]

No, they're not the same. The sum and the product of a sequence are
statements about the cumulative effect of an operation. The minimum
value in a set is a statement about a particular value, and if that
value isn't present in the set then there's something mighty fishy about
calling it the minimum value.


I don't want it to. Asking for the minimum value of an empty sequence is
meaningless, and returning a value that masquerades as an element of
that sequence doesn't make it meaningful. If you've got a set<int> and
you look for its minimum value, you ought to be able to find that value
in the set. That's not the case for sum and product.

Ok, let me try again by recalling some Calculus. The infimum x of a set A of
numbers is the greatest lower bound for its elements characterized by

(a) x <= a for each a in A
(b) y <= x for each y satisfying (a) instead of x.

Sets may or may not have an infimum, and even if they have an infimum they
may not contain it as an element. Finite non-empty sets always have an
infimum and contain it as an element. The notion of infimum extends in a
natural way the notion of minimum, which after the fact can be defined as
an infimum that happens to be an element of the set.

The empty std::set<int> has an infimum, and this infimum is INT_MAX: to see
this, one just needs to let range x and y above range over all possible
values of type int. One finds that any value for x satisfies (a). Thus,
INT_MAX is the unique x satisfying (b). There is nothing meaningless about
it.

In view of your criticism, may I propose to change the name of the function
in order to avoid confusion:

int infimum ( int* from, int* to );

I have argued elsethread why I prefer this semantics for a library method to
undefined behavior. Note that I do not say this is better than
std::min_element().


As for whether this is the same as with + and *, I reiterate my previous
post: min(-,-) is a binary, associative operation. Whenever one is faced
with such an operation, the identity element with respect to this operation
is the formally correct choice for the iterated operation value of the
empty sequence, i.e., the unique value that makes concatenation of input
sequences commute with applying the iterated operation. In this formal
sense, it truly is the same convention as the one for empty sums and
products.

_If_ the caller wants to know whether an empty sequence was

Or, even better, don't pretend that there's a value. Do what min_range
does, and return an iterator to the value, with end-of-sequence
designating that there was no minimum (i.e. the sequence was empty).

That is undeniably a viable option. At least it does not invoke undefined
behavior. However, I fail to see how it is _better_ and an absolute sense.
I see that it is more generic in that is applies to types that do not have
a maximum admissible value. However, that does not apply to built-in
arithmetic types for which a meaningful return value (greatest lower bound)
exists in all cases. The function does not pretend anything. It just has
well-defined and natural semantics for all inputs and that's all.


Best

Kai-Uwe Bux

 

[Pete Becker]

That is undeniably a viable option. At least it does not invoke undefined
behavior. However, I fail to see how it is _better_ and an absolute sense.

Sheesh. Again: there is no better in an absolute sense. The best choice
of algorithm depends on what the desired result is, and there isn't
enough information in the original post, nor in any of the responses to
it, to choose a "best" algorithm for finding the minimum value of a set
of integers. Nevertheless, the response to the approach I initially
suggested has been to assert that other approaches are better. Nonsense.
End of discussion.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)