Topic: arg_min and arg_max
Author: akensler@gmail.com
Date: Wed, 29 Jul 2015 00:49:26 -0700 (PDT)
Raw View
------=_Part_4_1365023186.1438156166031
Content-Type: multipart/alternative;
boundary="----=_Part_5_696550251.1438156166032"
------=_Part_5_696550251.1438156166032
Content-Type: text/plain; charset=UTF-8
Hello all,
I'd like to suggest a small addition to the standard library in the form of
arg min and arg max functions. It's the kind of loop we've probably all
written hundreds of times: scan through a container, transform each element
through some function, and find the element that produces the highest or
lowest result. Among other things, I've written this for finding the
closest point in a set, the closest color in palette, the best individual
in a genetic algorithm, and the next edge to add to a minimum spanning tree.
I'm tired of writing this loop out each time. Regular generic programming
can capture the basic idiom, and anonymous functions make it easy to
express the transformation step. In short, I'd like to suggest adding a
function like this:
template<class ForwardIterator, class UnaryOperation>
ForwardIterator arg_min(ForwardIterator first, ForwardIterator last,
UnaryOperation op)
{
if (first == last)
return last;
auto arg = first;
auto minima = op(*first++);
for (; first != last; ++first) {
auto value = op(*first);
if (value < minima) {
arg = first;
minima = value;
}
}
return arg;
}
to the algorithm section of the library standard, along with the anologous
arg_max() function. As an example of its use, mapping a color to the
nearest palette entry could then be as simple as:
struct rgb { float r, g, b; };
rgb map_to_palette(rgb const from, vector<rgb> const &palette)
{
assert(!palette.empty());
return *arg_min(begin(palette), end(palette), [&](rgb to) {
return ((to.r - from.r) * (to.r - from.r) +
(to.g - from.g) * (to.g - from.g) +
(to.b - from.b) * (to.b - from.b));
});
}
I apologize if this has been proposed before; my searches failed to find
anything. Thanks for your thoughts and consideration.
Cheers,
- Andrew Kensler
--
---
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_5_696550251.1438156166032
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hello all,<br><br>I'd like to suggest a small addition=
to the standard library in the form of arg min and arg max functions.=C2=
=A0 It's the kind of loop we've probably all written hundreds of ti=
mes: scan through a container, transform each element through some function=
, and find the element that produces the highest or lowest result.=C2=A0 Am=
ong other things, I've written this for finding the closest point in a =
set, the closest color in palette, the best individual in a genetic algorit=
hm, and the next edge to add to a minimum spanning tree.<br><br>I'm tir=
ed of writing this loop out each time.=C2=A0 Regular generic programming ca=
n capture the basic idiom, and anonymous functions make it easy to express =
the transformation step.=C2=A0 In short, I'd like to suggest adding a f=
unction like this:<br><br><div class=3D"prettyprint" style=3D"background-co=
lor: rgb(250, 250, 250); border-color: rgb(187, 187, 187); border-style: so=
lid; border-width: 1px; word-wrap: break-word;"><code 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-b=
y-prettify"><</span><span style=3D"color: #008;" class=3D"styled-by-pret=
tify">class</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
> </span><span style=3D"color: #606;" class=3D"styled-by-prettify">ForwardI=
terator</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: #008;" class=3D"styled-by-prettify">class</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"col=
or: #606;" class=3D"styled-by-prettify">UnaryOperation</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: #606=
;" class=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color:=
#000;" class=3D"styled-by-prettify"> arg_min</span><span style=3D"color: #=
660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #606;" cla=
ss=3D"styled-by-prettify">ForwardIterator</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> first</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"> </span><span style=3D"color: #606;" class=3D"styled-by-p=
rettify">ForwardIterator</span><span style=3D"color: #000;" class=3D"styled=
-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-prett=
ify">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,=
</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 </span><span style=3D"color: #606;" class=3D"styled-by-prettify">UnaryO=
peration</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> o=
p</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 s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">{</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><span st=
yle=3D"color: #008;" class=3D"styled-by-prettify">if</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"> </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"=
styled-by-prettify">=3D=3D</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pre=
ttify">last</span><span style=3D"color: #660;" class=3D"styled-by-prettify"=
>)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"style=
d-by-prettify">return</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">;</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =
=C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-prettify">aut=
o</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> arg </sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> first</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>=C2=A0 =C2=A0 </span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">auto</span><span style=3D"=
color: #000;" class=3D"styled-by-prettify"> minima </span><span style=3D"co=
lor: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> op</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">(*</span><span style=3D"color: #000;" class=3D"s=
tyled-by-prettify">first</span><span style=3D"color: #660;" class=3D"styled=
-by-prettify">++);</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">for</span><span style=3D"color: #000;" class=3D"styled-by-p=
rettify"> </span><span style=3D"color: #660;" 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"styled-by-prettify">!=3D</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span sty=
le=3D"color: #008;" class=3D"styled-by-prettify">last</span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">;</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">++</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify">first</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">{</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">auto</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> value </span><span style=3D"color: #660;" class=3D"styled-by-prettify">=
=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> op</sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">(*</span><span=
style=3D"color: #000;" class=3D"styled-by-prettify">first</span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">);</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </s=
pan><span style=3D"color: #008;" class=3D"styled-by-prettify">if</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">value </span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify"><</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify"> minima</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: #660;" class=3D"styled-by-pre=
ttify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><b=
r>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 arg </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> first</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">;</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 minima </sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> value</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>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </s=
pan><span style=3D"color: #660;" class=3D"styled-by-prettify">}</span><span=
style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </sp=
an><span style=3D"color: #008;" class=3D"styled-by-prettify">return</span><=
span style=3D"color: #000;" class=3D"styled-by-prettify"> arg</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></span><span style=3D"color: =
#660;" class=3D"styled-by-prettify">}</span><span style=3D"color: #000;" cl=
ass=3D"styled-by-prettify"><br><br></span></div></code></div><br>to the alg=
orithm section of the library standard, along with the anologous arg_max() =
function.=C2=A0 As an example of its use, mapping a color to the nearest pa=
lette entry could then be as simple as:<br><br><div class=3D"prettyprint" s=
tyle=3D"background-color: rgb(250, 250, 250); border-color: rgb(187, 187, 1=
87); border-style: solid; border-width: 1px; word-wrap: break-word;"><code =
class=3D"prettyprint"><div class=3D"subprettyprint"><span style=3D"color: #=
008;" class=3D"styled-by-prettify">struct</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> rgb </span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">{</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">float</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"> r</span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> g</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"> </span><span style=3D"color: #660;" class=3D"st=
yled-by-prettify">};</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify"><br>rgb map_to_palette</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">rgb </span><span style=3D"color: #008;" class=3D"styled-by-p=
rettify">const</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">from<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">,</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify"> vector</span><span =
style=3D"color: #080;" class=3D"styled-by-prettify"><rgb></span><span=
style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D=
"color: #008;" class=3D"styled-by-prettify">const</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;"=
class=3D"styled-by-prettify">&</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify">palette</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">)</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
<br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styled-by-pr=
ettify">assert</span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">(!</span><span style=3D"color: #000;" class=3D"styled-by-prettify">pale=
tte</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">empty</span><spa=
n style=3D"color: #660;" class=3D"styled-by-prettify">());</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><s=
pan style=3D"color: #008;" class=3D"styled-by-prettify">return</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"=
color: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify">arg_min</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"s=
tyled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-=
prettify">palette</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: #008;" class=3D"styled-by-prettify">end</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">palette</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">),</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;"=
class=3D"styled-by-prettify">[&](</span><span style=3D"color: #000;" c=
lass=3D"styled-by-prettify">rgb to</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: #660;" class=3D"styled-by-pret=
tify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"s=
tyled-by-prettify">return</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> </span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">((</span><span style=3D"color: #000;" class=3D"styled-by-prettify">to=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><s=
pan style=3D"color: #000;" class=3D"styled-by-prettify">r </span><span styl=
e=3D"color: #660;" class=3D"styled-by-prettify">-</span><span style=3D"colo=
r: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;"=
class=3D"styled-by-prettify">from</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">r</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">*</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">to</span><span style=3D"color: #660;"=
class=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D=
"styled-by-prettify">r </span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">-</span><span style=3D"color: #000;" class=3D"styled-by-pretti=
fy"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">from<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">r</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: #660;" =
class=3D"styled-by-prettify">+</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</=
span><span style=3D"color: #000;" class=3D"styled-by-prettify">to</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">g </span><span style=3D"colo=
r: #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">from</span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">.</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">g</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: #660;" class=3D"styled-by-prettify">*</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"color=
: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">to</span><span style=3D"color: #660;" class=3D=
"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"styled-b=
y-prettify">g </span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">-</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </sp=
an><span style=3D"color: #008;" class=3D"styled-by-prettify">from</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">g</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: #660;" class=3D"=
styled-by-prettify">+</span><span style=3D"color: #000;" class=3D"styled-by=
-prettify"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </sp=
an><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span =
style=3D"color: #000;" class=3D"styled-by-prettify">to</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;" cl=
ass=3D"styled-by-prettify">-</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-p=
rettify">from</span><span style=3D"color: #660;" class=3D"styled-by-prettif=
y">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">b</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: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"> </span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">to</span><span style=3D"color: #660;" class=3D"styled-by-pre=
ttify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify">b =
</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">from</span><span style=3D"co=
lor: #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;" class=3D"sty=
led-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">});</span><span style=3D"color: #000;" class=3D"st=
yled-by-prettify"><br></span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">}</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y"><br><br></span></div></code></div><br>I apologize if this has been propo=
sed before; my searches failed to find anything.=C2=A0 Thanks for your thou=
ghts and consideration.<br><br>Cheers,<br>- Andrew Kensler<br><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_5_696550251.1438156166032--
------=_Part_4_1365023186.1438156166031--
.
Author: Erich Keane <erich.keane@verizon.net>
Date: Wed, 29 Jul 2015 10:07:01 -0700 (PDT)
Raw View
------=_Part_1027_586740690.1438189621842
Content-Type: multipart/alternative;
boundary="----=_Part_1028_1778091357.1438189621843"
------=_Part_1028_1778091357.1438189621843
Content-Type: text/plain; charset=UTF-8
On Wednesday, July 29, 2015 at 12:49:26 AM UTC-7, aken...@gmail.com wrote:
>
> Hello all,
>
> I'd like to suggest a small addition to the standard library in the form
> of arg min and arg max functions. It's the kind of loop we've probably all
> written hundreds of times: scan through a container, transform each element
> through some function, and find the element that produces the highest or
> lowest result. Among other things, I've written this for finding the
> closest point in a set, the closest color in palette, the best individual
> in a genetic algorithm, and the next edge to add to a minimum spanning tree.
>
> I'm tired of writing this loop out each time. Regular generic programming
> can capture the basic idiom, and anonymous functions make it easy to
> express the transformation step. In short, I'd like to suggest adding a
> function like this:
>
> template<class ForwardIterator, class UnaryOperation>
> ForwardIterator arg_min(ForwardIterator first, ForwardIterator last,
> UnaryOperation op)
> {
> if (first == last)
> return last;
> auto arg = first;
> auto minima = op(*first++);
> for (; first != last; ++first) {
> auto value = op(*first);
> if (value < minima) {
> arg = first;
> minima = value;
> }
> }
> return arg;
> }
>
>
> to the algorithm section of the library standard, along with the anologous
> arg_max() function. As an example of its use, mapping a color to the
> nearest palette entry could then be as simple as:
>
> struct rgb { float r, g, b; };
> rgb map_to_palette(rgb const from, vector<rgb> const &palette)
> {
> assert(!palette.empty());
> return *arg_min(begin(palette), end(palette), [&](rgb to) {
> return ((to.r - from.r) * (to.r - from.r) +
> (to.g - from.g) * (to.g - from.g) +
> (to.b - from.b) * (to.b - from.b));
> });
> }
>
>
> I apologize if this has been proposed before; my searches failed to find
> anything. Thanks for your thoughts and consideration.
>
> Cheers,
> - Andrew Kensler
>
>
Perhaps I'm reading this wrong, but it seems that it does the same thing as
std::min_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/.
------=_Part_1028_1778091357.1438189621843
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br><br>On Wednesday, July 29, 2015 at 12:49:26 AM UTC-7, aken...@gmail.com=
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.=
8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">Hello =
all,<br><br>I'd like to suggest a small addition to the standard librar=
y in the form of arg min and arg max functions.=C2=A0 It's the kind of =
loop we've probably all written hundreds of times: scan through a conta=
iner, transform each element through some function, and find the element th=
at produces the highest or lowest result.=C2=A0 Among other things, I'v=
e written this for finding the closest point in a set, the closest color in=
palette, the best individual in a genetic algorithm, and the next edge to =
add to a minimum spanning tree.<br><br>I'm tired of writing this loop o=
ut each time.=C2=A0 Regular generic programming can capture the basic idiom=
, and anonymous functions make it easy to express the transformation step.=
=C2=A0 In short, I'd like to suggest adding a function like this:<br><b=
r><div style=3D"background-color:rgb(250,250,250);border-color:rgb(187,187,=
187);border-style:solid;border-width:1px;word-wrap:break-word"><code><div><=
span style=3D"color:#008">template</span><span style=3D"color:#660"><</s=
pan><span style=3D"color:#008">class</span><span style=3D"color:#000"> </sp=
an><span style=3D"color:#606">ForwardIterator</span><span style=3D"color:#6=
60">,</span><span style=3D"color:#000"> </span><span style=3D"color:#008">c=
lass</span><span style=3D"color:#000"> </span><span style=3D"color:#606">Un=
aryOperation</span><span style=3D"color:#660">></span><span style=3D"col=
or:#000"><br></span><span style=3D"color:#606">ForwardIterator</span><span =
style=3D"color:#000"> arg_min</span><span style=3D"color:#660">(</span><spa=
n style=3D"color:#606">ForwardIterator</span><span style=3D"color:#000"> fi=
rst</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> </=
span><span style=3D"color:#606">ForwardIterator</span><span style=3D"color:=
#000"> </span><span style=3D"color:#008">last</span><span style=3D"color:#6=
60">,</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"=
color:#606">UnaryOperation</span><span style=3D"color:#000"> op</span><span=
style=3D"color:#660">)</span><span style=3D"color:#000"><br></span><span s=
tyle=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </=
span><span style=3D"color:#008">if</span><span style=3D"color:#000"> </span=
><span style=3D"color:#660">(</span><span style=3D"color:#000">first </span=
><span style=3D"color:#660">=3D=3D</span><span style=3D"color:#000"> </span=
><span style=3D"color:#008">last</span><span style=3D"color:#660">)</span><=
span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span styl=
e=3D"color:#008">return</span><span style=3D"color:#000"> </span><span styl=
e=3D"color:#008">last</span><span style=3D"color:#660">;</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">auto</s=
pan><span style=3D"color:#000"> arg </span><span style=3D"color:#660">=3D</=
span><span style=3D"color:#000"> first</span><span style=3D"color:#660">;</=
span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"col=
or:#008">auto</span><span style=3D"color:#000"> minima </span><span style=
=3D"color:#660">=3D</span><span style=3D"color:#000"> op</span><span style=
=3D"color:#660">(*</span><span style=3D"color:#000">first</span><span style=
=3D"color:#660">++);</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </s=
pan><span style=3D"color:#008">for</span><span style=3D"color:#000"> </span=
><span style=3D"color:#660">(;</span><span style=3D"color:#000"> first </sp=
an><span style=3D"color:#660">!=3D</span><span style=3D"color:#000"> </span=
><span style=3D"color:#008">last</span><span style=3D"color:#660">;</span><=
span style=3D"color:#000"> </span><span style=3D"color:#660">++</span><span=
style=3D"color:#000">first</span><span style=3D"color:#660">)</span><span =
style=3D"color:#000"> </span><span style=3D"color:#660">{</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color=
:#008">auto</span><span style=3D"color:#000"> value </span><span style=3D"c=
olor:#660">=3D</span><span style=3D"color:#000"> op</span><span style=3D"co=
lor:#660">(*</span><span style=3D"color:#000">first</span><span style=3D"co=
lor:#660">);</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 </span><span style=3D"color:#008">if</span><span style=3D"color:#000"> =
</span><span style=3D"color:#660">(</span><span style=3D"color:#000">value =
</span><span style=3D"color:#660"><</span><span style=3D"color:#000"> mi=
nima</span><span style=3D"color:#660">)</span><span style=3D"color:#000"> <=
/span><span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 arg </span><span style=3D"color:#660=
">=3D</span><span style=3D"color:#000"> first</span><span style=3D"color:#6=
60">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 minima </span><span style=3D"color:#660">=3D</span><span style=
=3D"color:#000"> value</span><span style=3D"color:#660">;</span><span style=
=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color=
:#660">}</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span st=
yle=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </s=
pan><span style=3D"color:#008">return</span><span style=3D"color:#000"> arg=
</span><span style=3D"color:#660">;</span><span style=3D"color:#000"><br></=
span><span style=3D"color:#660">}</span><span style=3D"color:#000"><br><br>=
</span></div></code></div><br>to the algorithm section of the library stand=
ard, along with the anologous arg_max() function.=C2=A0 As an example of it=
s use, mapping a color to the nearest palette entry could then be as simple=
as:<br><br><div style=3D"background-color:rgb(250,250,250);border-color:rg=
b(187,187,187);border-style:solid;border-width:1px;word-wrap:break-word"><c=
ode><div><span style=3D"color:#008">struct</span><span style=3D"color:#000"=
> rgb </span><span style=3D"color:#660">{</span><span style=3D"color:#000">=
</span><span style=3D"color:#008">float</span><span style=3D"color:#000"> =
r</span><span style=3D"color:#660">,</span><span style=3D"color:#000"> g</s=
pan><span style=3D"color:#660">,</span><span style=3D"color:#000"> b</span>=
<span style=3D"color:#660">;</span><span style=3D"color:#000"> </span><span=
style=3D"color:#660">};</span><span style=3D"color:#000"><br>rgb map_to_pa=
lette</span><span style=3D"color:#660">(</span><span style=3D"color:#000">r=
gb </span><span style=3D"color:#008">const</span><span style=3D"color:#000"=
> </span><span style=3D"color:#008">from</span><span style=3D"color:#660">,=
</span><span style=3D"color:#000"> vector</span><span style=3D"color:#080">=
<rgb></span><span style=3D"color:#000"> </span><span style=3D"color:#=
008">const</span><span style=3D"color:#000"> </span><span style=3D"color:#6=
60">&</span><span style=3D"color:#000">palette</span><span style=3D"col=
or:#660">)</span><span style=3D"color:#000"><br></span><span style=3D"color=
:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span st=
yle=3D"color:#008">assert</span><span style=3D"color:#660">(!</span><span s=
tyle=3D"color:#000">palette</span><span style=3D"color:#660">.</span><span =
style=3D"color:#000">empty</span><span style=3D"color:#660">());</span><spa=
n style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008">=
return</span><span style=3D"color:#000"> </span><span style=3D"color:#660">=
*</span><span style=3D"color:#000">arg_min</span><span style=3D"color:#660"=
>(</span><span style=3D"color:#008">begin</span><span style=3D"color:#660">=
(</span><span style=3D"color:#000">palette</span><span style=3D"color:#660"=
>),</span><span style=3D"color:#000"> </span><span style=3D"color:#008">end=
</span><span style=3D"color:#660">(</span><span style=3D"color:#000">palett=
e</span><span style=3D"color:#660">),</span><span style=3D"color:#000"> </s=
pan><span style=3D"color:#660">[&](</span><span style=3D"color:#000">rg=
b to</span><span style=3D"color:#660">)</span><span style=3D"color:#000"> <=
/span><span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#008">return</span><sp=
an style=3D"color:#000"> </span><span style=3D"color:#660">((</span><span s=
tyle=3D"color:#000">to</span><span style=3D"color:#660">.</span><span style=
=3D"color:#000">r </span><span style=3D"color:#660">-</span><span style=3D"=
color:#000"> </span><span style=3D"color:#008">from</span><span style=3D"co=
lor:#660">.</span><span style=3D"color:#000">r</span><span style=3D"color:#=
660">)</span><span style=3D"color:#000"> </span><span style=3D"color:#660">=
*</span><span style=3D"color:#000"> </span><span style=3D"color:#660">(</sp=
an><span style=3D"color:#000">to</span><span style=3D"color:#660">.</span><=
span style=3D"color:#000">r </span><span style=3D"color:#660">-</span><span=
style=3D"color:#000"> </span><span style=3D"color:#008">from</span><span s=
tyle=3D"color:#660">.</span><span style=3D"color:#000">r</span><span style=
=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=3D"c=
olor:#660">+</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#660">(</span><=
span style=3D"color:#000">to</span><span style=3D"color:#660">.</span><span=
style=3D"color:#000">g </span><span style=3D"color:#660">-</span><span sty=
le=3D"color:#000"> </span><span style=3D"color:#008">from</span><span style=
=3D"color:#660">.</span><span style=3D"color:#000">g</span><span style=3D"c=
olor:#660">)</span><span style=3D"color:#000"> </span><span style=3D"color:=
#660">*</span><span style=3D"color:#000"> </span><span style=3D"color:#660"=
>(</span><span style=3D"color:#000">to</span><span style=3D"color:#660">.</=
span><span style=3D"color:#000">g </span><span style=3D"color:#660">-</span=
><span style=3D"color:#000"> </span><span style=3D"color:#008">from</span><=
span style=3D"color:#660">.</span><span style=3D"color:#000">g</span><span =
style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">+</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#660">(</sp=
an><span style=3D"color:#000">to</span><span style=3D"color:#660">.</span><=
span style=3D"color:#000">b </span><span style=3D"color:#660">-</span><span=
style=3D"color:#000"> </span><span style=3D"color:#008">from</span><span s=
tyle=3D"color:#660">.</span><span style=3D"color:#000">b</span><span style=
=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=3D"c=
olor:#660">*</span><span style=3D"color:#000"> </span><span style=3D"color:=
#660">(</span><span style=3D"color:#000">to</span><span style=3D"color:#660=
">.</span><span style=3D"color:#000">b </span><span style=3D"color:#660">-<=
/span><span style=3D"color:#000"> </span><span style=3D"color:#008">from</s=
pan><span style=3D"color:#660">.</span><span style=3D"color:#000">b</span><=
span style=3D"color:#660">));</span><span style=3D"color:#000"><br>=C2=A0 =
=C2=A0 </span><span style=3D"color:#660">});</span><span style=3D"color:#00=
0"><br></span><span style=3D"color:#660">}</span><span style=3D"color:#000"=
><br><br></span></div></code></div><br>I apologize if this has been propose=
d before; my searches failed to find anything.=C2=A0 Thanks for your though=
ts and consideration.<br><br>Cheers,<br>- Andrew Kensler<br><br></div></blo=
ckquote><div><br>Perhaps I'm reading this wrong, but it seems that it d=
oes the same thing as std::min_element. <br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_1028_1778091357.1438189621843--
------=_Part_1027_586740690.1438189621842--
.
Author: David Krauss <potswa@gmail.com>
Date: Thu, 30 Jul 2015 14:50:12 +0800
Raw View
--Apple-Mail=_849E8411-B8DB-4FF8-AAEB-7FBD52418D5C
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset=UTF-8
> On 2015=E2=80=9307=E2=80=9330, at 1:07 AM, Erich Keane <erich.keane@veriz=
on.net> wrote:
>=20
> Perhaps I'm reading this wrong, but it seems that it does the same thing =
as std::min_element.
Sort-of. Doing it with min_element requires performing the transformation i=
nside the comparator, which means running it twice as many times as necessa=
ry (or implementing memoization or caching).
--=20
---=20
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 e=
mail 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-proposa=
ls/.
--Apple-Mail=_849E8411-B8DB-4FF8-AAEB-7FBD52418D5C
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html; charset=UTF-8
<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html charset=
=3Dutf-8"></head><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: s=
pace; -webkit-line-break: after-white-space;" class=3D""><br class=3D""><di=
v><blockquote type=3D"cite" class=3D""><div class=3D"">On 2015=E2=80=9307=
=E2=80=9330, at 1:07 AM, Erich Keane <<a href=3D"mailto:erich.keane@veri=
zon.net" class=3D"">erich.keane@verizon.net</a>> wrote:</div><br class=
=3D"Apple-interchange-newline"><div class=3D""><span style=3D"font-family: =
Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-=
weight: normal; letter-spacing: normal; line-height: normal; orphans: auto;=
text-align: start; text-indent: 0px; text-transform: none; white-space: no=
rmal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; floa=
t: none; display: inline !important;" class=3D"">Perhaps I'm reading this w=
rong, but it seems that it does the same thing as std::min_element.</span><=
/div></blockquote></div><br class=3D""><div class=3D"">Sort-of. Doing it wi=
th <font face=3D"Courier" class=3D"">min_element</font> requires performing=
the transformation inside the comparator, which means running it twice as =
many times as necessary (or implementing memoization or caching).</div><div=
class=3D""><br class=3D""></div></body></html>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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 />
--Apple-Mail=_849E8411-B8DB-4FF8-AAEB-7FBD52418D5C--
.
Author: akensler@gmail.com
Date: Thu, 30 Jul 2015 00:16:53 -0700 (PDT)
Raw View
------=_Part_7017_215032682.1438240614064
Content-Type: multipart/alternative;
boundary="----=_Part_7018_621771904.1438240614065"
------=_Part_7018_621771904.1438240614065
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
[Dave: exactly! Here was what I was about to reply to Erich]
There are some similarities to min_element(), but also some important=20
differences -- namely that the elements are mapped or transformed through a=
=20
function. If I were to rewrite my example of the color matching function=
=20
to use min_element(), I could go about it in a couple of ways though none=
=20
of them are great:
1. Give min_element() a comparator that computes the color difference to=
=20
the input for both the left and right parameters and returns the lesser.=
=20
E.g.,
=20
rgb map_to_palette(rgb const from, vector<rgb> const &palette)
{
assert(!palette.empty());
auto diff =3D [&](rgb to) {
return ((to.r - from.r) * (to.r - from.r) +
(to.g - from.g) * (to.g - from.g) +
(to.b - from.b) * (to.b - from.b));
};
return *min_element(begin(palette), end(palette), [&](rgb left, rgb=
=20
right) {
return diff(left) < diff(right);
});
}
=20
This works, but now the mapping function is called 2N times instead of=
=20
1N. That's not so bad in this case, but may be problematic if the funct=
ion=20
is stateful or particularly expensive to compute. (For example, I've=20
written palette mapping code using the perceptual CIEDE2000=20
color-difference formula.)
=20
2. Use a min_element() with a comparator that memoizes the mappings of=
=20
its last pair of inputs. This gets it back down to 1N invocation of the=
=20
mapping function but now the comparator has to carry around a two-elemen=
t=20
cache and check its inputs against that. This is clumsy and verbose eno=
ugh=20
that one might as well write the usual for-loop instead.
On the other hand, arg_min() is sufficiently powerful that one can express=
=20
min_element() in terms of it by passing in a simple identity function as=20
the operation.
With that in mind, I did consider suggesting these as new overloads of=20
min_element() and max_element(). However, I believe that disambiguating=20
whether the function passed is a comparator or a unary op requires either=
=20
either arbitrarily re-ordering the parameters or else using an empty tag=20
struct (similar to piecewise_constructor for tuples). Neither one strikes=
=20
me as a particularly great option and arg_min() and arg_max() at least have=
=20
the advantage of implying the mapping.
Cheers,
- Andrew
On Wednesday, July 29, 2015 at 11:50:21 PM UTC-7, David Krauss wrote:
>
>
> On 2015=E2=80=9307=E2=80=9330, at 1:07 AM, Erich Keane <erich...@verizon.=
net <javascript:>>=20
> wrote:
>
> Perhaps I'm reading this wrong, but it seems that it does the same thing=
=20
> as std::min_element.
>
>
> Sort-of. Doing it with min_element requires performing the transformation=
=20
> inside the comparator, which means running it twice as many times as=20
> necessary (or implementing memoization or caching).
>
>
--=20
---=20
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 e=
mail 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-proposa=
ls/.
------=_Part_7018_621771904.1438240614065
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">[Dave: exactly!=C2=A0 Here was what I was about to reply t=
o Erich]<br><br>There are some similarities to min_element(), but also some=
important differences -- namely that the elements are mapped or transforme=
d through a function.=C2=A0 If I were to rewrite my example of the color ma=
tching function to use min_element(), I could go about it in a couple of wa=
ys though none of them are great:<br><br><ol><li>Give min_element() a compa=
rator that computes the color difference to the input for both the left and=
right parameters and returns the lesser.=C2=A0 E.g.,<br><br><div class=3D"=
prettyprint" style=3D"background-color: rgb(250, 250, 250); border-color: r=
gb(187, 187, 187); border-style: solid; border-width: 1px; word-wrap: break=
-word;"><code class=3D"prettyprint"><div class=3D"subprettyprint"><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">rgb map_to_palette</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify">rgb </span><span style=3D"c=
olor: #008;" class=3D"styled-by-prettify">const</span><span style=3D"color:=
#000;" class=3D"styled-by-prettify"> </span><span style=3D"color: #008;" c=
lass=3D"styled-by-prettify">from</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify"> vector</span><span style=3D"color: #080;" class=3D"styled-b=
y-prettify"><rgb></span><span style=3D"color: #000;" class=3D"styled-=
by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pretti=
fy">const</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> =
</span><span style=3D"color: #660;" class=3D"styled-by-prettify">&</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify">palette</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"><br></span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"co=
lor: #008;" class=3D"styled-by-prettify">assert</span><span style=3D"color:=
#660;" class=3D"styled-by-prettify">(!</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify">palette</span><span style=3D"color: #660;" cla=
ss=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"sty=
led-by-prettify">empty</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">());</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"><br>=C2=A0 =C2=A0 </span><span style=3D"color: #008;" class=3D"styled=
-by-prettify">auto</span><span style=3D"color: #000;" class=3D"styled-by-pr=
ettify"> diff </span><span style=3D"color: #660;" class=3D"styled-by-pretti=
fy">=3D</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">[&](</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify">rgb to</span><=
span style=3D"color: #660;" class=3D"styled-by-prettify">)</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">{</span><span style=3D"color: #000;"=
class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span =
style=3D"color: #008;" class=3D"styled-by-prettify">return</span><span styl=
e=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">((</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify">to</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">r </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: #008;" class=3D"styled-by-prettify">from</span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><span sty=
le=3D"color: #000;" class=3D"styled-by-prettify">r</span><span style=3D"col=
or: #660;" class=3D"styled-by-prettify">)</span><span style=3D"color: #000;=
" class=3D"styled-by-prettify"> </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: #660;" class=3D"styled-by-pret=
tify">(</span><span style=3D"color: #000;" class=3D"styled-by-prettify">to<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">.</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">r </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: #008;" =
class=3D"styled-by-prettify">from</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">.</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">r</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify"> </=
span><span style=3D"color: #660;" class=3D"styled-by-prettify">+</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #660;" =
class=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"=
styled-by-prettify">to</span><span style=3D"color: #660;" class=3D"styled-b=
y-prettify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettif=
y">g </span><span style=3D"color: #660;" class=3D"styled-by-prettify">-</sp=
an><span style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span =
style=3D"color: #008;" class=3D"styled-by-prettify">from</span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">g</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: #660;" class=3D"styled-by=
-prettify">*</span><span style=3D"color: #000;" class=3D"styled-by-prettify=
"> </span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span=
><span style=3D"color: #000;" class=3D"styled-by-prettify">to</span><span s=
tyle=3D"color: #660;" class=3D"styled-by-prettify">.</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify">g </span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">-</span><span style=3D"color: #000;" clas=
s=3D"styled-by-prettify"> </span><span style=3D"color: #008;" class=3D"styl=
ed-by-prettify">from</span><span style=3D"color: #660;" class=3D"styled-by-=
prettify">.</span><span style=3D"color: #000;" class=3D"styled-by-prettify"=
>g</span><span style=3D"color: #660;" class=3D"styled-by-prettify">)</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify"> </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>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #660;" class=3D"style=
d-by-prettify">(</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify">to</span><span style=3D"color: #660;" class=3D"styled-by-prettify">.<=
/span><span style=3D"color: #000;" class=3D"styled-by-prettify">b </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">from</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"style=
d-by-prettify">)</span><span style=3D"color: #000;" class=3D"styled-by-pret=
tify"> </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: #660;" class=3D"styled-by-prettify">(</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">to</span><span style=3D"colo=
r: #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;" class=3D"style=
d-by-prettify"> </span><span style=3D"color: #008;" class=3D"styled-by-pret=
tify">from</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 st=
yle=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span>=
<span style=3D"color: #660;" class=3D"styled-by-prettify">};</span><span st=
yle=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span>=
<span style=3D"color: #008;" class=3D"styled-by-prettify">return</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">*</span><span style=3D"color=
: #000;" class=3D"styled-by-prettify">min_element</span><span style=3D"colo=
r: #660;" class=3D"styled-by-prettify">(</span><span style=3D"color: #008;"=
class=3D"styled-by-prettify">begin</span><span style=3D"color: #660;" clas=
s=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"styl=
ed-by-prettify">palette</span><span style=3D"color: #660;" class=3D"styled-=
by-prettify">),</span><span style=3D"color: #000;" class=3D"styled-by-prett=
ify"> </span><span style=3D"color: #008;" class=3D"styled-by-prettify">end<=
/span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><sp=
an style=3D"color: #000;" class=3D"styled-by-prettify">palette</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: #=
660;" class=3D"styled-by-prettify">[&](</span><span style=3D"color: #00=
0;" class=3D"styled-by-prettify">rgb left</span><span style=3D"color: #660;=
" class=3D"styled-by-prettify">,</span><span style=3D"color: #000;" class=
=3D"styled-by-prettify"> rgb right</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: #660;" class=3D"styled-by-pret=
tify">{</span><span style=3D"color: #000;" class=3D"styled-by-prettify"><br=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color: #00=
8;" class=3D"styled-by-prettify">return</span><span style=3D"color: #000;" =
class=3D"styled-by-prettify"> diff</span><span style=3D"color: #660;" class=
=3D"styled-by-prettify">(</span><span style=3D"color: #000;" class=3D"style=
d-by-prettify">left</span><span style=3D"color: #660;" class=3D"styled-by-p=
rettify">)</span><span style=3D"color: #000;" class=3D"styled-by-prettify">=
</span><span style=3D"color: #660;" class=3D"styled-by-prettify"><</spa=
n><span style=3D"color: #000;" class=3D"styled-by-prettify"> diff</span><sp=
an style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">right</span><span style=3D"c=
olor: #660;" class=3D"styled-by-prettify">);</span><span style=3D"color: #0=
00;" class=3D"styled-by-prettify"><br>=C2=A0 =C2=A0 </span><span style=3D"c=
olor: #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"=
styled-by-prettify"><br></span></div></code></div><br>This works, but now t=
he mapping function is called 2N times instead of 1N.=C2=A0 That's not =
so bad in this case, but may be problematic if the function is stateful or =
particularly expensive to compute.=C2=A0 (For example, I've written pal=
ette mapping code using the perceptual CIEDE2000 color-difference formula.)=
<br><br></li><li>Use a min_element() with a comparator that memoizes the ma=
ppings of its last pair of inputs.=C2=A0 This gets it back down to 1N invoc=
ation of the mapping function but now the comparator has to carry around a =
two-element cache and check its inputs against that.=C2=A0 This is clumsy a=
nd verbose enough that one might as well write the usual for-loop instead.<=
/li></ol><p>On the other hand, arg_min() is sufficiently powerful that one =
can express min_element() in terms of it by passing in a simple identity fu=
nction as the operation.<br><br>With that in mind, I did consider suggestin=
g these as new overloads of min_element() and max_element().=C2=A0 However,=
I believe that disambiguating whether the function passed is a comparator =
or a unary op requires either either arbitrarily re-ordering the parameters=
or else using an empty tag struct (similar to piecewise_constructor for tu=
ples).=C2=A0 Neither one strikes me as a particularly great option and arg_=
min() and arg_max() at least have the advantage of implying the mapping.<br=
><br></p>Cheers,<br>- Andrew<br><br>On Wednesday, July 29, 2015 at 11:50:21=
PM UTC-7, David Krauss wrote:<blockquote class=3D"gmail_quote" style=3D"ma=
rgin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">=
<div style=3D"word-wrap:break-word"><br><div><blockquote type=3D"cite"><div=
>On 2015=E2=80=9307=E2=80=9330, at 1:07 AM, Erich Keane <<a href=3D"java=
script:" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'=
;javascript:';return true;" onclick=3D"this.href=3D'javascript:'=
;;return true;">erich...@verizon.net</a>> wrote:</div><br><div><span sty=
le=3D"font-family:Helvetica;font-size:12px;font-style:normal;font-variant:n=
ormal;font-weight:normal;letter-spacing:normal;line-height:normal;text-alig=
n:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing=
:0px;float:none;display:inline!important">Perhaps I'm reading this wron=
g, but it seems that it does the same thing as std::min_element.</span></di=
v></blockquote></div><br><div>Sort-of. Doing it with <font face=3D"Courier"=
>min_element</font> requires performing the transformation inside the compa=
rator, which means running it twice as many times as necessary (or implemen=
ting memoization or caching).</div><div><br></div></div></blockquote></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_7018_621771904.1438240614065--
------=_Part_7017_215032682.1438240614064--
.
Author: "S.B." <i.and.my.little.friends@gmail.com>
Date: Thu, 30 Jul 2015 04:23:23 -0700 (PDT)
Raw View
------=_Part_257_894405634.1438255403918
Content-Type: multipart/alternative;
boundary="----=_Part_258_362509791.1438255403918"
------=_Part_258_362509791.1438255403918
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
=E5=9C=A8 2015=E5=B9=B47=E6=9C=8829=E6=97=A5=E6=98=9F=E6=9C=9F=E4=B8=89 UTC=
+8=E4=B8=8B=E5=8D=883:49:26=EF=BC=8Caken...@gmail.com=E5=86=99=E9=81=93=EF=
=BC=9A
>
> Hello all,
>
> I'd like to suggest a small addition to the standard library in the form=
=20
> of arg min and arg max functions. It's the kind of loop we've probably a=
ll=20
> written hundreds of times: scan through a container, transform each eleme=
nt=20
> through some function, and find the element that produces the highest or=
=20
> lowest result. Among other things, I've written this for finding the=20
> closest point in a set, the closest color in palette, the best individual=
=20
> in a genetic algorithm, and the next edge to add to a minimum spanning tr=
ee.
>
> I'm tired of writing this loop out each time. Regular generic programmin=
g=20
> can capture the basic idiom, and anonymous functions make it easy to=20
> express the transformation step. In short, I'd like to suggest adding a=
=20
> function like this:
>
> template<class ForwardIterator, class UnaryOperation>
> ForwardIterator arg_min(ForwardIterator first, ForwardIterator last,
> UnaryOperation op)
> {
> if (first =3D=3D last)
> return last;
> auto arg =3D first;
> auto minima =3D op(*first++);
> for (; first !=3D last; ++first) {
> auto value =3D op(*first);
> if (value < minima) {
> arg =3D first;
> minima =3D value;
> }
> }
> return arg;
> }
>
>
> to the algorithm section of the library standard, along with the anologou=
s=20
> arg_max() function. As an example of its use, mapping a color to the=20
> nearest palette entry could then be as simple as:
>
> struct rgb { float r, g, b; };
> rgb map_to_palette(rgb const from, vector<rgb> const &palette)
> {
> assert(!palette.empty());
> return *arg_min(begin(palette), end(palette), [&](rgb to) {
> return ((to.r - from.r) * (to.r - from.r) +
> (to.g - from.g) * (to.g - from.g) +
> (to.b - from.b) * (to.b - from.b));
> });
> }
>
>
> I apologize if this has been proposed before; my searches failed to find=
=20
> anything. Thanks for your thoughts and consideration.
>
> Cheers,
> - Andrew Kensler
>
> See discussion on reddit.=20
<http://www.reddit.com/r/cpp/comments/36sqtq/more_efficient_interface_for_a=
lgorithms_taking_a/>
--=20
---=20
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 e=
mail 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-proposa=
ls/.
------=_Part_258_362509791.1438255403918
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br><br>=E5=9C=A8 2015=E5=B9=B47=E6=9C=8829=E6=97=A5=E6=98=9F=E6=9C=9F=E4=
=B8=89 UTC+8=E4=B8=8B=E5=8D=883:49:26=EF=BC=8Caken...@gmail.com=E5=86=99=E9=
=81=93=EF=BC=9A<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-=
left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr=
">Hello all,<br><br>I'd like to suggest a small addition to the standar=
d library in the form of arg min and arg max functions.=C2=A0 It's the =
kind of loop we've probably all written hundreds of times: scan through=
a container, transform each element through some function, and find the el=
ement that produces the highest or lowest result.=C2=A0 Among other things,=
I've written this for finding the closest point in a set, the closest =
color in palette, the best individual in a genetic algorithm, and the next =
edge to add to a minimum spanning tree.<br><br>I'm tired of writing thi=
s loop out each time.=C2=A0 Regular generic programming can capture the bas=
ic idiom, and anonymous functions make it easy to express the transformatio=
n step.=C2=A0 In short, I'd like to suggest adding a function like this=
:<br><br><div style=3D"background-color:rgb(250,250,250);border-color:rgb(1=
87,187,187);border-style:solid;border-width:1px;word-wrap:break-word"><code=
><div><span style=3D"color:#008">template</span><span style=3D"color:#660">=
<</span><span style=3D"color:#008">class</span><span style=3D"color:#000=
"> </span><span style=3D"color:#606">ForwardIterator</span><span style=3D"c=
olor:#660">,</span><span style=3D"color:#000"> </span><span style=3D"color:=
#008">class</span><span style=3D"color:#000"> </span><span style=3D"color:#=
606">UnaryOperation</span><span style=3D"color:#660">></span><span style=
=3D"color:#000"><br></span><span style=3D"color:#606">ForwardIterator</span=
><span style=3D"color:#000"> arg_min</span><span style=3D"color:#660">(</sp=
an><span style=3D"color:#606">ForwardIterator</span><span style=3D"color:#0=
00"> first</span><span style=3D"color:#660">,</span><span style=3D"color:#0=
00"> </span><span style=3D"color:#606">ForwardIterator</span><span style=3D=
"color:#000"> </span><span style=3D"color:#008">last</span><span style=3D"c=
olor:#660">,</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span st=
yle=3D"color:#606">UnaryOperation</span><span style=3D"color:#000"> op</spa=
n><span style=3D"color:#660">)</span><span style=3D"color:#000"><br></span>=
<span style=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =
=C2=A0 </span><span style=3D"color:#008">if</span><span style=3D"color:#000=
"> </span><span style=3D"color:#660">(</span><span style=3D"color:#000">fir=
st </span><span style=3D"color:#660">=3D=3D</span><span style=3D"color:#000=
"> </span><span style=3D"color:#008">last</span><span style=3D"color:#660">=
)</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><=
span style=3D"color:#008">return</span><span style=3D"color:#000"> </span><=
span style=3D"color:#008">last</span><span style=3D"color:#660">;</span><sp=
an style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"color:#008"=
>auto</span><span style=3D"color:#000"> arg </span><span style=3D"color:#66=
0">=3D</span><span style=3D"color:#000"> first</span><span style=3D"color:#=
660">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span styl=
e=3D"color:#008">auto</span><span style=3D"color:#000"> minima </span><span=
style=3D"color:#660">=3D</span><span style=3D"color:#000"> op</span><span =
style=3D"color:#660">(*</span><span style=3D"color:#000">first</span><span =
style=3D"color:#660">++);</span><span style=3D"color:#000"><br>=C2=A0 =C2=
=A0 </span><span style=3D"color:#008">for</span><span style=3D"color:#000">=
</span><span style=3D"color:#660">(;</span><span style=3D"color:#000"> fir=
st </span><span style=3D"color:#660">!=3D</span><span style=3D"color:#000">=
</span><span style=3D"color:#008">last</span><span style=3D"color:#660">;<=
/span><span style=3D"color:#000"> </span><span style=3D"color:#660">++</spa=
n><span style=3D"color:#000">first</span><span style=3D"color:#660">)</span=
><span style=3D"color:#000"> </span><span style=3D"color:#660">{</span><spa=
n style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=
=3D"color:#008">auto</span><span style=3D"color:#000"> value </span><span s=
tyle=3D"color:#660">=3D</span><span style=3D"color:#000"> op</span><span st=
yle=3D"color:#660">(*</span><span style=3D"color:#000">first</span><span st=
yle=3D"color:#660">);</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 </span><span style=3D"color:#008">if</span><span style=3D"col=
or:#000"> </span><span style=3D"color:#660">(</span><span style=3D"color:#0=
00">value </span><span style=3D"color:#660"><</span><span style=3D"color=
:#000"> minima</span><span style=3D"color:#660">)</span><span style=3D"colo=
r:#000"> </span><span style=3D"color:#660">{</span><span style=3D"color:#00=
0"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 arg </span><span style=3D"=
color:#660">=3D</span><span style=3D"color:#000"> first</span><span style=
=3D"color:#660">;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0=
=C2=A0 =C2=A0 =C2=A0 minima </span><span style=3D"color:#660">=3D</span><s=
pan style=3D"color:#000"> value</span><span style=3D"color:#660">;</span><s=
pan style=3D"color:#000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=
=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span=
><span style=3D"color:#660">}</span><span style=3D"color:#000"><br>=C2=A0 =
=C2=A0 </span><span style=3D"color:#008">return</span><span style=3D"color:=
#000"> arg</span><span style=3D"color:#660">;</span><span style=3D"color:#0=
00"><br></span><span style=3D"color:#660">}</span><span style=3D"color:#000=
"><br><br></span></div></code></div><br>to the algorithm section of the lib=
rary standard, along with the anologous arg_max() function.=C2=A0 As an exa=
mple of its use, mapping a color to the nearest palette entry could then be=
as simple as:<br><br><div style=3D"background-color:rgb(250,250,250);borde=
r-color:rgb(187,187,187);border-style:solid;border-width:1px;word-wrap:brea=
k-word"><code><div><span style=3D"color:#008">struct</span><span style=3D"c=
olor:#000"> rgb </span><span style=3D"color:#660">{</span><span style=3D"co=
lor:#000"> </span><span style=3D"color:#008">float</span><span style=3D"col=
or:#000"> r</span><span style=3D"color:#660">,</span><span style=3D"color:#=
000"> g</span><span style=3D"color:#660">,</span><span style=3D"color:#000"=
> b</span><span style=3D"color:#660">;</span><span style=3D"color:#000"> </=
span><span style=3D"color:#660">};</span><span style=3D"color:#000"><br>rgb=
map_to_palette</span><span style=3D"color:#660">(</span><span style=3D"col=
or:#000">rgb </span><span style=3D"color:#008">const</span><span style=3D"c=
olor:#000"> </span><span style=3D"color:#008">from</span><span style=3D"col=
or:#660">,</span><span style=3D"color:#000"> vector</span><span style=3D"co=
lor:#080"><rgb></span><span style=3D"color:#000"> </span><span style=
=3D"color:#008">const</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">&</span><span style=3D"color:#000">palette</span><span =
style=3D"color:#660">)</span><span style=3D"color:#000"><br></span><span st=
yle=3D"color:#660">{</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </s=
pan><span style=3D"color:#008">assert</span><span style=3D"color:#660">(!</=
span><span style=3D"color:#000">palette</span><span style=3D"color:#660">.<=
/span><span style=3D"color:#000">empty</span><span style=3D"color:#660">())=
;</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 </span><span style=3D"=
color:#008">return</span><span style=3D"color:#000"> </span><span style=3D"=
color:#660">*</span><span style=3D"color:#000">arg_min</span><span style=3D=
"color:#660">(</span><span style=3D"color:#008">begin</span><span style=3D"=
color:#660">(</span><span style=3D"color:#000">palette</span><span style=3D=
"color:#660">),</span><span style=3D"color:#000"> </span><span style=3D"col=
or:#008">end</span><span style=3D"color:#660">(</span><span style=3D"color:=
#000">palette</span><span style=3D"color:#660">),</span><span style=3D"colo=
r:#000"> </span><span style=3D"color:#660">[&](</span><span style=3D"co=
lor:#000">rgb to</span><span style=3D"color:#660">)</span><span style=3D"co=
lor:#000"> </span><span style=3D"color:#660">{</span><span style=3D"color:#=
000"><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#008">retu=
rn</span><span style=3D"color:#000"> </span><span style=3D"color:#660">((</=
span><span style=3D"color:#000">to</span><span style=3D"color:#660">.</span=
><span style=3D"color:#000">r </span><span style=3D"color:#660">-</span><sp=
an style=3D"color:#000"> </span><span style=3D"color:#008">from</span><span=
style=3D"color:#660">.</span><span style=3D"color:#000">r</span><span styl=
e=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=3D"=
color:#660">*</span><span style=3D"color:#000"> </span><span style=3D"color=
:#660">(</span><span style=3D"color:#000">to</span><span style=3D"color:#66=
0">.</span><span style=3D"color:#000">r </span><span style=3D"color:#660">-=
</span><span style=3D"color:#000"> </span><span style=3D"color:#008">from</=
span><span style=3D"color:#660">.</span><span style=3D"color:#000">r</span>=
<span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span=
style=3D"color:#660">+</span><span style=3D"color:#000"><br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#660"=
>(</span><span style=3D"color:#000">to</span><span style=3D"color:#660">.</=
span><span style=3D"color:#000">g </span><span style=3D"color:#660">-</span=
><span style=3D"color:#000"> </span><span style=3D"color:#008">from</span><=
span style=3D"color:#660">.</span><span style=3D"color:#000">g</span><span =
style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">*</span><span style=3D"color:#000"> </span><span style=3D"c=
olor:#660">(</span><span style=3D"color:#000">to</span><span style=3D"color=
:#660">.</span><span style=3D"color:#000">g </span><span style=3D"color:#66=
0">-</span><span style=3D"color:#000"> </span><span style=3D"color:#008">fr=
om</span><span style=3D"color:#660">.</span><span style=3D"color:#000">g</s=
pan><span style=3D"color:#660">)</span><span style=3D"color:#000"> </span><=
span style=3D"color:#660">+</span><span style=3D"color:#000"><br>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 </span><span style=3D"color:#=
660">(</span><span style=3D"color:#000">to</span><span style=3D"color:#660"=
>.</span><span style=3D"color:#000">b </span><span style=3D"color:#660">-</=
span><span style=3D"color:#000"> </span><span style=3D"color:#008">from</sp=
an><span style=3D"color:#660">.</span><span style=3D"color:#000">b</span><s=
pan style=3D"color:#660">)</span><span style=3D"color:#000"> </span><span s=
tyle=3D"color:#660">*</span><span style=3D"color:#000"> </span><span style=
=3D"color:#660">(</span><span style=3D"color:#000">to</span><span style=3D"=
color:#660">.</span><span style=3D"color:#000">b </span><span style=3D"colo=
r:#660">-</span><span style=3D"color:#000"> </span><span style=3D"color:#00=
8">from</span><span style=3D"color:#660">.</span><span style=3D"color:#000"=
>b</span><span style=3D"color:#660">));</span><span style=3D"color:#000"><b=
r>=C2=A0 =C2=A0 </span><span style=3D"color:#660">});</span><span style=3D"=
color:#000"><br></span><span style=3D"color:#660">}</span><span style=3D"co=
lor:#000"><br><br></span></div></code></div><br>I apologize if this has bee=
n proposed before; my searches failed to find anything.=C2=A0 Thanks for yo=
ur thoughts and consideration.<br><br>Cheers,<br>- Andrew Kensler<br><br></=
div></blockquote><div>See discussion on <a href=3D"http://www.reddit.com/r/=
cpp/comments/36sqtq/more_efficient_interface_for_algorithms_taking_a/">redd=
it. </a><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_258_362509791.1438255403918--
------=_Part_257_894405634.1438255403918--
.
Author: "Mark A. Gibbs" <indi.in.the.wired@gmail.com>
Date: Thu, 30 Jul 2015 15:03:21 -0700 (PDT)
Raw View
------=_Part_47_663769011.1438293801900
Content-Type: multipart/alternative;
boundary="----=_Part_48_1055957340.1438293801900"
------=_Part_48_1055957340.1438293801900
Content-Type: text/plain; charset=UTF-8
I saw this discussion on Reddit a while back, and at the time it struck me
that - that rather than another algorithm, or mucking around with
max_element's interface - the smart way to solve this problem would be a
"transforming iterator". Like boost::transform_iterator
<http://www.boost.org/doc/libs/1_58_0/libs/iterator/doc/transform_iterator.html>
:
auto p = std::max_element(
boost::make_transform_iterator(first, func),
boost::make_transform_iterator(last, func)).base();
For ranges you'd use the boost::adaptors::transformed adaptor
<http://www.boost.org/doc/libs/1_58_0/libs/range/doc/html/range/reference/adaptors/reference/transformed.html>
(which will surely have an analogue in C++17 ranges):
auto p = boost::max_element(data | boost::adaptors::transformed(func));
Would this solve the problem?
--
---
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_48_1055957340.1438293801900
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I saw this discussion on Reddit a while back, and at the t=
ime it struck me that - that rather than another algorithm, or mucking arou=
nd with <span style=3D"font-family: courier new,monospace;">max_element</sp=
an>'s interface - the smart way to solve this problem would be a "=
transforming iterator". Like <span style=3D"font-family: courier new,m=
onospace;"><a href=3D"http://www.boost.org/doc/libs/1_58_0/libs/iterator/do=
c/transform_iterator.html">boost::transform_iterator</a></span>:<br><br><di=
v class=3D"prettyprint" style=3D"background-color: rgb(250, 250, 250); bord=
er-color: rgb(187, 187, 187); border-style: solid; border-width: 1px; word-=
wrap: break-word;"><code class=3D"prettyprint"><div class=3D"subprettyprint=
"><span style=3D"color: #008;" class=3D"styled-by-prettify">auto</span><spa=
n style=3D"color: #000;" class=3D"styled-by-prettify"> p </span><span style=
=3D"color: #660;" class=3D"styled-by-prettify">=3D</span><span style=3D"col=
or: #000;" class=3D"styled-by-prettify"> std</span><span style=3D"color: #6=
60;" class=3D"styled-by-prettify">::</span><span style=3D"color: #000;" cla=
ss=3D"styled-by-prettify">max_element</span><span style=3D"color: #660;" cl=
ass=3D"styled-by-prettify">(</span><code class=3D"prettyprint"><span style=
=3D"color: #000;" class=3D"styled-by-prettify"><br>=C2=A0 boost</span><span=
style=3D"color: #660;" class=3D"styled-by-prettify">::</span><span style=
=3D"color: #000;" class=3D"styled-by-prettify">make_transform_iterator</spa=
n><span style=3D"color: #660;" class=3D"styled-by-prettify">(</span><span s=
tyle=3D"color: #000;" class=3D"styled-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"> func</span><span style=3D"color: #66=
0;" class=3D"styled-by-prettify">),<br>=C2=A0 </span></code><code class=3D"=
prettyprint"><span style=3D"color: #000;" class=3D"styled-by-prettify">boos=
t</span><span style=3D"color: #660;" class=3D"styled-by-prettify">::</span>=
<span style=3D"color: #000;" class=3D"styled-by-prettify">make_transform_it=
erator</span><span style=3D"color: #660;" class=3D"styled-by-prettify">(</s=
pan><span style=3D"color: #000;" class=3D"styled-by-prettify">last</span><s=
pan 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"c=
olor: #660;" class=3D"styled-by-prettify">)).base();</span><span style=3D"c=
olor: #000;" class=3D"styled-by-prettify"><br></span></code><span style=3D"=
color: #000;" class=3D"styled-by-prettify"></span></div></code></div><br>Fo=
r ranges you'd use the <a href=3D"http://www.boost.org/doc/libs/1_58_0/=
libs/range/doc/html/range/reference/adaptors/reference/transformed.html"><s=
pan style=3D"font-family: courier new,monospace;">boost::adaptors::transfor=
med</span> adaptor</a> (which will surely have an analogue in C++17 ranges)=
:<br><br><div class=3D"prettyprint" style=3D"background-color: rgb(250, 250=
, 250); border-color: rgb(187, 187, 187); border-style: solid; border-width=
: 1px; word-wrap: break-word;"><code class=3D"prettyprint"><div class=3D"su=
bprettyprint"><div class=3D"prettyprint" style=3D"background-color: rgb(250=
, 250, 250); border-color: rgb(187, 187, 187); border-style: solid; border-=
width: 1px; word-wrap: break-word;"><code class=3D"prettyprint"><div class=
=3D"subprettyprint"><span style=3D"color: #606;" class=3D"styled-by-prettif=
y">auto p =3D boost::max_element(data | </span><span style=3D"color: #606;"=
class=3D"styled-by-prettify"><code class=3D"prettyprint"><span style=3D"co=
lor: #606;" class=3D"styled-by-prettify">boost::adaptors::</span></code>tra=
nsformed(func));</span><span style=3D"color: #660;" class=3D"styled-by-pret=
tify"></span></div></code></div><span style=3D"color: #660;" class=3D"style=
d-by-prettify"></span></div></code></div><div dir=3D"ltr"><br>Would this so=
lve the problem?<br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_48_1055957340.1438293801900--
------=_Part_47_663769011.1438293801900--
.
Author: Magnus Fromreide <magfr@lysator.liu.se>
Date: Fri, 31 Jul 2015 07:30:11 +0200
Raw View
On Thu, Jul 30, 2015 at 03:03:21PM -0700, Mark A. Gibbs wrote:
> I saw this discussion on Reddit a while back, and at the time it struck me
> that - that rather than another algorithm, or mucking around with
> max_element's interface - the smart way to solve this problem would be a
> "transforming iterator".
While I agree in principle the transform_iterator version isn't enough.
A typical implementation of max_element is
template <class ForwardIterator>
ForwardIterator max_element ( ForwardIterator first, ForwardIterator last )
{
if (first==last) return last;
ForwardIterator largest = first;
while (++first!=last)
if (*largest<*first)
largest=first;
return largest;
}
and using a transforming iterator wouldn't reduce the number of times
func gets called. What is needed is two wrappers, first the transforming
iterator and secondly a caching iterator that stores the value from the
dereference of the wrapped iterator and returns the cached value on
subsequent dereferences.
So, a caching_iterator<transform_iterator<first, func>> should be
enough to call func no more than N times.
/MF
--
---
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/.
.
Author: "Mark A. Gibbs" <indi.in.the.wired@gmail.com>
Date: Sat, 1 Aug 2015 18:45:27 -0700 (PDT)
Raw View
------=_Part_386_1206141385.1438479927555
Content-Type: multipart/alternative;
boundary="----=_Part_387_1214406793.1438479927556"
------=_Part_387_1214406793.1438479927556
Content-Type: text/plain; charset=UTF-8
On Friday, 31 July 2015 01:30:19 UTC-4, Magnus Fromreide wrote:
>
> So, a caching_iterator<transform_iterator<first, func>> should be
> enough to call func no more than N times.
>
Ah, I assumed that transform iterators already cached, like
istream_iterator does, but in hindsight that wouldn't make sense in this
context.
At any rate, it seems to me that it would probably be more useful to add
transform iterators and caching iterators - along with other iterator or
range adaptors - rather than trying to add a bunch more functions. Adaptors
compose, unlike functions. Arguably we already have a bunch of algorithm
functions that are probably unnecessary - like std::transform is just
std::copy with transform iterators. And if you use transform iterators with
std::copy_if, you get the missing "transform_if" algorithm.
--
---
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_387_1214406793.1438479927556
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Friday, 31 July 2015 01:30:19 UTC-4, Magnus Fromreide =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">So, a caching_iterator&l=
t;transform_<wbr>iterator<first, func>> should be
<br>enough to call func no more than N times.
<br></blockquote><div><br>Ah, I assumed that transform iterators already ca=
ched, like istream_iterator does, but in hindsight that wouldn't make s=
ense in this context.<br><br>At any rate, it seems to me that it would prob=
ably be more useful to add transform iterators and caching iterators - alon=
g with other iterator or range adaptors - rather than trying to add a bunch=
more functions. Adaptors compose, unlike functions. Arguably we already ha=
ve a bunch of algorithm functions that are probably unnecessary - like std:=
:transform is just std::copy with transform iterators. And if you use trans=
form iterators with std::copy_if, you get the missing "transform_if&qu=
ot; algorithm.<br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<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_387_1214406793.1438479927556--
------=_Part_386_1206141385.1438479927555--
.