------=_Part_1033_10536123.1384176968257
Content-Type: text/plain; charset=ISO-8859-1

I frequently find myself needing to iterate over a container and get an
iterator to the element that maximizes or minimizes some fairly expensive
function, and I don't think there's a good algorithm in the standard
library to do this as well as possible. Here's what I mean:

template<class ForwardIterator, class UnaryFunction>
ForwardIterator argmax(ForwardIterator first, ForwardIterator last,
UnaryFunction func)
{
  if( first == last ) return last;

  auto best_score_so_far = func(*first);
  ForwardIterator best = first;

  for(auto i = first + 1; i != last; i++)
  {
    const auto current_score = func(*i);

    if( current_score > best_score_so_far )
    {
      best_score_so_far = current_score;
      best = i;
    }
  }

  return best;
}

This implementation uses O(1) space and exactly N calls to func. All the
implementations that I can think of that use calls to standard algorithms
either use more space or make more calls to func. If func is some
hellaciously-expensive function, then the extra calls can be
problematic.  If you're running in a memory-constrained environment or are
just working with very long lists, the extra memory used can be problematic
(or could blow out your cache).


Here are two solutions I can see to use. The first one is a pretty naive
implementation using max element that calls func 2(N-1) times:

template<class ForwardIterator, class UnaryFunction>
ForwardIterator argmax(ForwardIterator first, ForwardIterator last,
UnaryFunction func)
{
  return std::max_element(first, last,
    [&](typename ForwardIterator::reference a, typename ForwardIterator::reference
b)
    {
      return func(a) < func(b);
    }
  );
}


Since the problem is that the implementation calls func too many times, we
could use std::transform to get a vector of all of the results of func in
the range [first, last), and then use max_element over that vector, but now
we're using O(N) space, traversing the range twice (once for std::distance
and the other for std::transform), and we have a dynamic allocation (for
std::vector):

template<class ForwardIterator, class UnaryFunction>
ForwardIterator argmax_spacehog(ForwardIterator first, ForwardIterator last,
UnaryFunction func)
{
  typedef decltype(func(*first)) return_t;

  std::vector<return_t> scores(std::distance(first, last));

  std::transform(first, last, scores.begin(), func);

  auto highest_score = std::max_element(scores.begin(), scores.end());

  return first + std::distance(scores.begin(), highest_score);
}


The upshot is, I've found that an argmax function has been a bottleneck in
a few of my projects, and I've ended up including the hand-rolled code
snippet quite a few times. Is this something that the library working group
might be interested in or has considered before? I know this is pretty
trivial compared to move constructors, xvalues, and threading libraries,
but it's something that I would use a bunch! As far as other languages and
implementations (and the title of the post), this is how Python deals with
its max function (as well as min and sort).

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_1033_10536123.1384176968257
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I frequently find myself needing to iterate over a contain=
er and get an iterator to the element that maximizes or minimizes some fair=
ly expensive function, and I don't think there's a good algorithm in the st=
andard library to do this as well as possible. Here's what I mean:<div><br>=
</div><div style=3D"font-family: arial; font-size: small;"><div class=3D"pr=
ettyprint" style=3D"background-color: rgb(250, 250, 250); border: 1px solid=
 rgb(187, 187, 187); word-wrap: break-word;"><code class=3D"prettyprint"><d=
iv class=3D"subprettyprint"><span style=3D"color: #008;" class=3D"styled-by=
-prettify">template</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">&lt;</span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">class</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIter=
ator</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span s=
tyle=3D"color: #008;" class=3D"styled-by-prettify">class</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #606;" class=3D"styled-by-prettify">UnaryFunction</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #606;" =
class=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> argmax</span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">(</span><span style=3D"color: #606;" class=
=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> first</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-pre=
ttify">ForwardIterator</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><spa=
n style=3D"color: #606;" class=3D"styled-by-prettify">UnaryFunction</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> func</span><span =
style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color:=
 #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"color: #008;" =
class=3D"styled-by-prettify">if</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> first </span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">=3D=3D</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">last=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #008;" class=3D"styled-by-prettify">return</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">last</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"><br><br>&nbsp; </span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">auto</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"> best_score_so_far </span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> func</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">(*</span><span style=3D"color: #000;" class=3D"styled-by-prettify">fi=
rst</span><span style=3D"color: #660;" class=3D"styled-by-prettify">);</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </sp=
an><span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterato=
r</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> best </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> first</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"><br><br>&nbsp; </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">for</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #008;=
" class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> i </span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"> first </span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">+</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #066;" class=3D"styled-by-prettify">1</span><s=
pan style=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> i </span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">!=3D</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" clas=
s=3D"styled-by-prettify">last</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">;</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> i</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">++)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&=
nbsp; </span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &n=
bsp; </span><span style=3D"color: #008;" class=3D"styled-by-prettify">const=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><s=
pan style=3D"color: #008;" class=3D"styled-by-prettify">auto</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"> current_score </span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> func</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">(*</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify">i</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"><br>&nbsp; &nbsp; &nbsp; &nbsp; <br>&nbsp; &nbsp; </span>=
<span style=3D"color: #008;" class=3D"styled-by-prettify">if</span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> current_score </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">&gt;</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> best_score_so_far </span><span st=
yle=3D"color: #660;" class=3D"styled-by-prettify">)</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp; &nbsp; best_score=
_so_far </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> curren=
t_score</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &=
nbsp; &nbsp; best </span><span style=3D"color: #660;" class=3D"styled-by-pr=
ettify">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
> i</span><span style=3D"color: #660;" class=3D"styled-by-prettify">;</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; &nbsp=
; </span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"><br><br>&nbsp; </span><sp=
an style=3D"color: #008;" class=3D"styled-by-prettify">return</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> best</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">}</span></div></code></div><div><br></div><=
/div><div>This implementation uses O(1) space and exactly N calls to&nbsp;f=
unc. All the implementations that I can think of that use calls to standard=
 algorithms either use more space or make more calls to&nbsp;func.&nbsp;If&=
nbsp;func&nbsp;is some hellaciously-expensive function, then the extra call=
s can be problematic.&nbsp;&nbsp;If you're running in a memory-constrained =
environment or are just working with very long lists, the extra memory used=
 can be problematic (or could blow out your cache).</div><div><br></div><di=
v><br></div><div>Here are two solutions I can see to use. The first one is =
a pretty naive implementation using max element that calls&nbsp;func&nbsp;2=
(N-1) times:</div><div><br></div><div style=3D"font-family: arial; font-siz=
e: small;"><div class=3D"prettyprint" style=3D"background-color: rgb(250, 2=
50, 250); border: 1px solid rgb(187, 187, 187); word-wrap: break-word;"><co=
de class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color=
: #008;" class=3D"styled-by-prettify">template</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">&lt;</span><span style=3D"color: #008;"=
 class=3D"styled-by-prettify">class</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styl=
ed-by-prettify">ForwardIterator</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">class</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #606;" class=3D"styled-by-prettify">UnaryFuncti=
on</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&gt;</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></span><sp=
an style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> argmax</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span styl=
e=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterator</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> first</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;=
" class=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color: =
#000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" cl=
ass=3D"styled-by-prettify">last</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-prettif=
y">UnaryFunction</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> func</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">{</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"><br>&nbsp; </span><span=
 style=3D"color: #008;" class=3D"styled-by-prettify">return</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #=
000;" class=3D"styled-by-prettify">max_element</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">first</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pret=
tify">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <br>&nbs=
p; &nbsp; </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
[&amp;](</span><span style=3D"color: #008;" class=3D"styled-by-prettify">ty=
pename</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </s=
pan><span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardIterat=
or</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">reference a</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span s=
tyle=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">typename</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #606;=
" class=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify">reference b</span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #660;" c=
lass=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br>&nbsp; &nbsp; &nbsp; </span><span style=3D"color: #0=
08;" class=3D"styled-by-prettify">return</span><span style=3D"color: #000;"=
 class=3D"styled-by-prettify"> func</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">a</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> func</span><span=
 style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D=
"color: #000;" class=3D"styled-by-prettify">b</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">);</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br>&nbsp; &nbsp; </span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">}</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"><br>&nbsp; </span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">}</span></div></code></div><div><font face=3D"Arial, Helvetica=
, sans-serif"><br></font></div></div><div><br></div><div>Since the problem =
is that the implementation calls&nbsp;func&nbsp;too many times, we could us=
e std::transform to get a vector of all of the results of&nbsp;func&nbsp;in=
 the range [first, last), and then use max_element over that vector, but no=
w we're using O(N) space, traversing the range twice (once for std::distanc=
e and the other for std::transform), and we have a dynamic allocation (for =
std::vector):</div><div><br></div><div><div class=3D"prettyprint" style=3D"=
background-color: rgb(250, 250, 250); border: 1px solid rgb(187, 187, 187);=
 word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"subprett=
yprint"><span style=3D"color: #008;" class=3D"styled-by-prettify">template<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">&lt;</span>=
<span style=3D"color: #008;" class=3D"styled-by-prettify">class</span><span=
 style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D=
"color: #606;" class=3D"styled-by-prettify">ForwardIterator</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">,</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;=
" class=3D"styled-by-prettify">class</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify"> </span><span style=3D"color: #606;" class=3D"sty=
led-by-prettify">UnaryFunction</span><span style=3D"color: #660;" class=3D"=
styled-by-prettify">&gt;</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"><br></span><span style=3D"color: #606;" class=3D"styled-by-pr=
ettify">ForwardIterator</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> argmax_spacehog</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">(</span><span style=3D"color: #606;" class=3D"styled-by-=
prettify">ForwardIterator</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> first</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #606;" class=3D"styled-by-prettify">Forward=
Iterator</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> <=
/span><span style=3D"color: #008;" class=3D"styled-by-prettify">last</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"col=
or: #606;" class=3D"styled-by-prettify">UnaryFunction</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> func</span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"><br></span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br>&nbsp; </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">typedef</span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pretti=
fy">decltype</span><span style=3D"color: #660;" class=3D"styled-by-prettify=
">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">func</s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">(*</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify">first</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">))</span><span style=3D"co=
lor: #000;" class=3D"styled-by-prettify"> return_t</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"><br><br>&nbsp; std</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify">vector</span><span style=3D"color: #080;" cl=
ass=3D"styled-by-prettify">&lt;return_t&gt;</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> scores</span><span style=3D"color: #660;"=
 class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify">std</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">distance</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">first=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #008;" class=3D"styled-by-prettify">last</span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">));</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br><br>&nbsp; std</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">transform</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify">first</span><span style=3D"color: #660;" class=3D"s=
tyled-by-prettify">,</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify"=
>last</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> scores</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">begin</span><span style=3D=
"color: #660;" class=3D"styled-by-prettify">(),</span><span style=3D"color:=
 #000;" class=3D"styled-by-prettify"> func</span><span style=3D"color: #660=
;" class=3D"styled-by-prettify">);</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"><br><br>&nbsp; </span><span style=3D"color: #008;" =
class=3D"styled-by-prettify">auto</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> highest_score </span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> std</span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">::</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify">max_element</span><span style=3D"color: #660;" class=3D"styled-by=
-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
">scores</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.<=
/span><span style=3D"color: #008;" class=3D"styled-by-prettify">begin</span=
><span style=3D"color: #660;" class=3D"styled-by-prettify">(),</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> scores</span><span sty=
le=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=3D"col=
or: #008;" class=3D"styled-by-prettify">end</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">());</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br><br>&nbsp; </span><span style=3D"color: #008=
;" class=3D"styled-by-prettify">return</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> first </span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">+</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><font color=3D"#666600" size=3D"2"><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify">std</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify">distance</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">scores</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">.</span><span style=3D"color: #008;" class=3D"styled-by-prettif=
y">begin</span><span style=3D"color: #660;" class=3D"styled-by-prettify">()=
,</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> highest_=
score</span><span style=3D"color: #660;" class=3D"styled-by-prettify">);</s=
pan></font><span style=3D"color: #000;" class=3D"styled-by-prettify"><br></=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span></di=
v></code></div><div style=3D"font-family: arial; font-size: small;"><font f=
ace=3D"Arial, Helvetica, sans-serif"><br></font></div></div><div><br></div>=
<div>The upshot is, I've found that an argmax function has been a bottlenec=
k in a few of my projects, and I've ended up including the hand-rolled code=
 snippet quite a few times. Is this something that the library working grou=
p might be interested in or has considered before? I know this is pretty tr=
ivial compared to move constructors, xvalues, and threading libraries, but =
it's something that I would use a bunch! As far as other languages and impl=
ementations (and the title of the post), this is how Python deals with its =
max&nbsp;function (as well as min and sort).&nbsp;</div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_1033_10536123.1384176968257--

.

On 11/11/13 9:36 PM, Andrew Hoelscher wrote:
> I frequently find myself needing to iterate over a container and get an
> iterator to the element that maximizes or minimizes some fairly expensive
> function, and I don't think there's a good algorithm in the standard
> library to do this as well as possible.

Using the Standard as a reference, it's sort of hidden at the end of
25.4.7 under "Sorting and related operations," but you are describing
std::(min|max|minmax)_element.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

On 11/11/13 9:36 PM, Andrew Hoelscher wrote:
> Here are two solutions I can see to use. The first one is a pretty naive
> implementation using max element that calls func 2(N-1) times:

Oh, you want to cache the function result. Never mind my previous message.

Several O(N) algorithms likewise could be computed on "filtered" values.
Not sure this is really the domain of the standard library.

> The upshot is, I've found that an argmax function has been a bottleneck in
> a few of my projects, and I've ended up including the hand-rolled code
> snippet quite a few times. Is this something that the library working group
> might be interested in or has considered before? I know this is pretty
> trivial compared to move constructors, xvalues, and threading libraries,
> but it's something that I would use a bunch! As far as other languages and
> implementations (and the title of the post), this is how Python deals with
> its max function (as well as min and sort).

Perhaps a standard caching facility would be more useful. A map or
hash-map with built-in LRU or pseudo-LRU would generalize the problem
nicely.

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

.

------=_Part_361_9045103.1384265305873
Content-Type: text/plain; charset=ISO-8859-1



> All the implementations that I can think of that use calls to standard
> algorithms either use more space or make more calls to func. If func is
> some hellaciously-expensive function, then the extra calls can be
> problematic.
>

Have you considered a transform iterator? There's two options if you want
to retain the result of the transform: lazy (in which case you'd want to
use std::optional<decltype(func(*first))>> for storage) or eager (in which
case you'd need to track the last iterator to avoid dereferencing a
past-the-end, so it would properly be a transform range).

--

---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/.

------=_Part_361_9045103.1384265305873
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr"><div style=3D"font-family:arial;font-size:small"><div><span style=
=3D"font-family: Arial, Helvetica, sans-serif; font-size: 13px;">All the im=
plementations that I can think of that use calls to standard algorithms eit=
her use more space or make more calls to&nbsp;func.&nbsp;If&nbsp;func&nbsp;=
is some hellaciously-expensive function, then the extra calls can be proble=
matic.</span></div></div></div></blockquote><div><br></div><div>Have you co=
nsidered a transform iterator? There's two options if you want to retain th=
e result of the transform: lazy (in which case you'd want to use std::optio=
nal&lt;decltype(func(*first))&gt;&gt; for storage) or eager (in which case =
you'd need to track the last iterator to avoid dereferencing a past-the-end=
, so it would properly be a transform range).</div></div>

<p></p>

-- <br />
&nbsp;<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_361_9045103.1384265305873--

.