Topic: Comparators in std::map, std::priority_queue and std::set
Author: aary@umich.edu
Date: Tue, 7 Mar 2017 20:20:41 -0800 (PST)
Raw View
------=_Part_26_1086864836.1488946841633
Content-Type: multipart/alternative;
boundary="----=_Part_27_1905860086.1488946841633"
------=_Part_27_1905860086.1488946841633
Content-Type: text/plain; charset=UTF-8
These libraries all offer constructors that are of the form
Container::Container(..., const Comparator& compare = Comparator{}, ...) :
comparator{compare} { ... }
This means that the comparator the library receives in the constructor
parameters must be copied into the internal storage for the comparator,
this results in at most two copies that have to be made for the comparator.
When the user passes a comparator that is not an elidable prvalue, there
will be one copy made at the call site and then another copy in the
initialization of the underlying comparator.
This does not follow the C++ way of only paying for what you ask for, there
don't need to be two copies. The library can offer an API that allows the
user to customize whether they want a copy or a move, this can be achieved
with perfect forwarding similarly to what is done in the constructor for
std::thread. The constructors can be modified as such
Container::Container(..., ComparatorCompatible&& f, ...) :
comparator{std::forward<ComparatorCompatible>(f)} { ... }
Here the user can supply a value to the comparator (in which case it will
be copied only once) or they can pass an rvalue which will be moved.
Nobody pays for what they didn't ask for!
--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/58f30b6b-de70-439d-8edd-60928dd3f074%40isocpp.org.
------=_Part_27_1905860086.1488946841633
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">These libraries all offer constructors that are of the for=
m<div><br></div><div><font face=3D"courier new, monospace">Container::Conta=
iner(..., const Comparator& compare =3D Comparator{}, ...) : comparator=
{compare} { ... }</font></div><div><font face=3D"courier new, monospace"><b=
r></font></div><div><font face=3D"arial, sans-serif">This means that the co=
mparator the library receives in the constructor parameters must be copied =
into the internal storage for the comparator, this results in at most two c=
opies that have to be made for the comparator. =C2=A0When the user passes a=
comparator that is not an elidable prvalue, there will be one copy made at=
the call site and then another copy in the initialization of the underlyin=
g comparator. =C2=A0</font></div><div><font face=3D"arial, sans-serif"><br>=
</font></div><div><font face=3D"arial, sans-serif">This does not follow the=
C++ way of only paying for what you ask for, there don't need to be tw=
o copies. =C2=A0The library can offer an API that allows the user to custom=
ize whether they want a copy or a move, this can be achieved with perfect f=
orwarding similarly to what is done in the constructor for </font><font fac=
e=3D"courier new, monospace">std::thread</font><font face=3D"arial, sans-se=
rif">. =C2=A0The constructors can be modified as such=C2=A0</font></div><di=
v><font face=3D"arial, sans-serif"><br></font></div><div><font face=3D"cour=
ier new, monospace">Container::Container(..., ComparatorCompatible&&=
; f, ...) : comparator{std::forward<ComparatorCompatible>(f)} { ... }=
</font></div><div><font face=3D"courier new, monospace"><br></font></div><d=
iv><font face=3D"arial, sans-serif">Here the user can supply a value to the=
comparator (in which case it will be copied only once) or they can pass an=
rvalue which will be moved. =C2=A0Nobody pays for what they didn't ask=
for!</font></div><div><font face=3D"arial, sans-serif"><br></font></div></=
div>
<p></p>
-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/58f30b6b-de70-439d-8edd-60928dd3f074%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/58f30b6b-de70-439d-8edd-60928dd3f074=
%40isocpp.org</a>.<br />
------=_Part_27_1905860086.1488946841633--
------=_Part_26_1086864836.1488946841633--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Tue, 7 Mar 2017 20:33:01 -0800 (PST)
Raw View
------=_Part_38_32149436.1488947581269
Content-Type: multipart/alternative;
boundary="----=_Part_39_340507703.1488947581269"
------=_Part_39_340507703.1488947581269
Content-Type: text/plain; charset=UTF-8
On Tuesday, March 7, 2017 at 11:20:41 PM UTC-5, aa...@umich.edu wrote:
>
> These libraries all offer constructors that are of the form
>
> Container::Container(..., const Comparator& compare = Comparator{}, ...) :
> comparator{compare} { ... }
>
> This means that the comparator the library receives in the constructor
> parameters must be copied into the internal storage for the comparator,
> this results in at most two copies that have to be made for the comparator.
> When the user passes a comparator that is not an elidable prvalue, there
> will be one copy made at the call site and then another copy in the
> initialization of the underlying comparator.
>
>
This does not follow the C++ way of only paying for what you ask for, there
> don't need to be two copies.
>
That only matters if the comparators is not empty. And most comparators
are. Empty, trivially copyable types won't do any copying of anything at
all.
So the only people who are paying anything at all are people who have
stateful comparators. More people probably use stateful allocators (which
have the same copying problem) than stateful comparators. The effort needed
to change the standard is simply not worth the benefit, since most users
will gain absolutely nothing from it.
The library can offer an API that allows the user to customize whether they
> want a copy or a move, this can be achieved with perfect forwarding
> similarly to what is done in the constructor for std::thread. The
> constructors can be modified as such
>
> Container::Container(..., ComparatorCompatible&& f, ...) :
> comparator{std::forward<ComparatorCompatible>(f)} { ... }
>
>
And that turns what would have been a concrete function into a template
function. I'm not sure how backwards compatible such a change would be.
Here the user can supply a value to the comparator (in which case it will
> be copied only once) or they can pass an rvalue which will be moved.
> Nobody pays for what they didn't ask for!
>
--
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.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/81d9c479-04e2-4fb0-83ed-054209f46805%40isocpp.org.
------=_Part_39_340507703.1488947581269
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">On Tuesday, March 7, 2017 at 11:20:41 PM UTC-5, aa...@umic=
h.edu wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">T=
hese libraries all offer constructors that are of the form<div><br></div><d=
iv><font face=3D"courier new, monospace">Container::Container(..., const Co=
mparator& compare =3D Comparator{}, ...) : comparator{compare} { ... }<=
/font></div><div><font face=3D"courier new, monospace"><br></font></div><di=
v><font face=3D"arial, sans-serif">This means that the comparator the libra=
ry receives in the constructor parameters must be copied into the internal =
storage for the comparator, this results in at most two copies that have to=
be made for the comparator. =C2=A0When the user passes a comparator that i=
s not an elidable prvalue, there will be one copy made at the call site and=
then another copy in the initialization of the underlying comparator.</fon=
t></div></div></blockquote><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-le=
ft: 1ex;"><div>=C2=A0</div></blockquote><blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-le=
ft: 1ex;"><div dir=3D"ltr"><div><font face=3D"arial, sans-serif"></font></d=
iv><div><font face=3D"arial, sans-serif"></font></div><div><font face=3D"ar=
ial, sans-serif">This does not follow the C++ way of only paying for what y=
ou ask for, there don't need to be two copies.</font></div></div></bloc=
kquote><div><br>That only matters if the comparators is not empty. And most=
comparators are. Empty, trivially copyable types won't do any copying =
of anything at all.<br><br>So the only people who are paying anything at al=
l are people who have stateful comparators. More people probably use statef=
ul allocators (which have the same copying problem) than stateful comparato=
rs. The effort needed to change the standard is simply not worth the benefi=
t, since most users will gain absolutely nothing from it.<br><br></div><blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><font face=
=3D"arial, sans-serif">The library can offer an API that allows the user to=
customize whether they want a copy or a move, this can be achieved with pe=
rfect forwarding similarly to what is done in the constructor for </font><f=
ont face=3D"courier new, monospace">std::thread</font><font face=3D"arial, =
sans-serif">. =C2=A0The constructors can be modified as such=C2=A0</font></=
div><div><font face=3D"arial, sans-serif"><br></font></div><div><font face=
=3D"courier new, monospace">Container::Container(..., ComparatorCompatible&=
amp;& f, ...) : comparator{std::forward<<wbr>ComparatorCompatible>=
;(f)} { ... }</font></div><div><font face=3D"courier new, monospace"><br></=
font></div></div></blockquote><div><br>And that turns what would have been =
a concrete function into a template function. I'm not sure how backward=
s compatible such a change would be.<br><br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;=
padding-left: 1ex;"><div dir=3D"ltr"><div><font face=3D"courier new, monosp=
ace"></font></div><div><font face=3D"arial, sans-serif">Here the user can s=
upply a value to the comparator (in which case it will be copied only once)=
or they can pass an rvalue which will be moved. =C2=A0Nobody pays for what=
they didn't ask for!</font></div></div></blockquote></div>
<p></p>
-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/81d9c479-04e2-4fb0-83ed-054209f46805%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/81d9c479-04e2-4fb0-83ed-054209f46805=
%40isocpp.org</a>.<br />
------=_Part_39_340507703.1488947581269--
------=_Part_38_32149436.1488947581269--
.