Re: std::max_element iterators
On 21.10.2010 05:53, tf wrote:
Daniel Kr??gler wrote:
Am 19.10.2010 10:53, schrieb tf:
Why does std::max_element need a ForwardIterator? Couldn't it get
by with just an InputIterator?
... okay nevermind, google answered that, but leaves another
question open. The above seems like a silly requirement to impose
on the caller. Why not just define it to return *iter instead of
iter?
This would not help either. Once you have applied any increment
operation on an object that corresponds to an input iterator, you
cannot dereference any copies of it. The only thing that you could
reasonably do with input-iterator-only types is to copy *every*
element of the iterated range into a local variable and to ensure
that your current max value is also a local variable (you can rid
of one of these locals, but not of both) and you need to copy the
result as well.
Uhh... what? What implementation are you envisioning?
I'm referring to an implementation equivalent to that you are
discussing, ignoring usage of numeric_limits for a momment. It
*requires* to copy each element from the sequence:
This is what I ended up with for my minmax, mentally adjust for just
one or the other, please ;)
[..]
I didn't copy every element there. I did use a local... but so what?
Why is it at all desirable, in this case, to avoid locals?
You needed to copy each element. This is fine, if your value types are
small and you are not interested in identity, but the provided
algorithms usually attempt to prevent unnecessary copies of
elements of the range and to keep the identity information where
possible. It's not all "int and double" ;-).
Secondly, this is an algorithm that does an O(n) operation over a
chunk of data. Why should one care about the O(1) overhead of copying
a pair for the retval?
This can be a very considerable amount, if your value element is itself
a container.
Then there would be no need to save the iterator. I can't recall
ever using std::???_element without immediately dereferencing it
w/in the RHS anyway. What use is it to know the index?
Often it is sufficient to know the position of the maximum. This
allows to transport this as a usually much cheaper information than
the actual value.
Example? Maybe searching for pivots or something?
I'm referring to situations where you want to keep the element
identity and where copying each element is an unacceptable option. This is among
the reasons why min/max (w/o initializer_list)
do return a reference, not a copy. Further-on minmax_element guarantees
a maximum call of your ordering function object of
1.5 * (N ??? 1), which is not satisfied by your naive implementation above.
I'm willing to admit that there are algorithms for which you need to
know the *index* of a value which satisfies some property. As my
question hints at though, it is extremely rare for me to implement
said algorithms, and thus I am quite surprised at your "often". My
implication was that the value matching the property is *much* more
commonly desired, so I feel that the std alg should probably cater to
that, and let people who need the index write their own function.
The algorithms are a collection of operations for general purpose.
Any user-code may have very specific requirements, which can usually
be realized via these functions from the Standard Library. If not,
you should write your own on, as you already did. If this is also
generally useful you may consider to propose it for the next
standard revision.
I can already hear a counterargument though: that's not C++, where
we'd like functionality to be as general as possible, even if that
makes them a pain in 90% of the uses it gets. I don't have a
counter-counterargument ;)
I don't think that there is anything special related to the programming
language C++. No-one is enforcing you to harm yourself. There is also
no marketing division that attempts to convince you to reuse existing
code from the library or from anywhere else.
I guess one must agree to disagree at some point.
There is no much room to argue about this assertion ;-)
I needed the minimum *and* maximum, so I had to define my own
function anyway. This would've been nice for testing, though.
It would be interesting to know why it is important to work with input
iterators here.
Greetings from Bremen,
Daniel Kr??gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]