Topic: std::map augmentation
Author: gogu <valeriu.smerica@my.fmi.unibuc.ro>
Date: Wed, 6 Feb 2019 18:44:00 -0800 (PST)
Raw View
------=_Part_125_1716863266.1549507440797
Content-Type: multipart/alternative;
boundary="----=_Part_126_477192966.1549507440797"
------=_Part_126_477192966.1549507440797
Content-Type: text/plain; charset="UTF-8"
Make std::map an order statistic tree. Add another template parameter to
std::map before the allocator type that will decide wether or not std::map
will be an order statistic tree. Memory will not be wasted. A second node
type will be defined in the implementation that also contains the size of
the subtree rooted at the node.
https://en.wikipedia.org/wiki/Order_statistic_tree
The std::map should have two other functions, called select and rank that
behave as the wikipedia article says. These should be disabled using
std::enable_if_t/concepts on the parameter that decides if the map is an
order statistic tree or not. Updating the size of the subtree of a node
could be done inside of the already defined functions using if constexpr
inside the function. The body of the compile-time if would update that size
for each node on the path down to the insertion point.
What do you guys think?
--
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/ce18cc74-9116-4da6-b320-fe2b4715b1d6%40isocpp.org.
------=_Part_126_477192966.1549507440797
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Make std::map an order statistic tree. Add another te=
mplate parameter to std::map before the allocator type that will decide wet=
her or not std::map will be an order statistic tree. Memory will not be was=
ted. A second node type will be defined in the implementation that also con=
tains the size of the subtree rooted at the node.<br></div><div><br> https:=
//en.wikipedia.org/wiki/Order_statistic_tree</div><div><br></div><div>The s=
td::map should have two other functions, called select and rank that behave=
as the wikipedia article says. These should be disabled using std::enable_=
if_t/concepts on the parameter that decides if the map is an order statisti=
c tree or not. Updating the size of the subtree of a node could be done ins=
ide of the already defined functions using if constexpr inside the function=
.. The body of the compile-time if would update that size for each node on t=
he path down to the insertion point.<br></div><div><br></div><div>What do y=
ou guys think?<br></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/ce18cc74-9116-4da6-b320-fe2b4715b1d6%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/ce18cc74-9116-4da6-b320-fe2b4715b1d6=
%40isocpp.org</a>.<br />
------=_Part_126_477192966.1549507440797--
------=_Part_125_1716863266.1549507440797--
.
Author: Tony V E <tvaneerd@gmail.com>
Date: Wed, 06 Feb 2019 22:37:35 -0500
Raw View
<html><head></head><body lang=3D"en-US" style=3D"background-color: rgb(255,=
255, 255); line-height: initial;"> =
<div style=3D"width: 100%; fo=
nt-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif=
; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, =
255, 255);">Have we run out of the supply of class names?</div><div style=
=3D"width: 100%; font-size: initial; font-family: Calibri, 'Slate Pro', san=
s-serif, sans-serif; color: rgb(31, 73, 125); text-align: initial; backgrou=
nd-color: rgb(255, 255, 255);"><br></div><div style=3D"width: 100%; font-si=
ze: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; col=
or: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255, =
255);">Make a new class, don't call it map.</div><div style=3D"width: 100%;=
font-size: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-se=
rif; color: rgb(31, 73, 125); text-align: initial; background-color: rgb(25=
5, 255, 255);"><br></div> =
=
<div style=3D"width: 100%; font-size: initial; font-family: Calibri=
, 'Slate Pro', sans-serif, sans-serif; color: rgb(31, 73, 125); text-align:=
initial; background-color: rgb(255, 255, 255);"><br style=3D"display:initi=
al"></div> =
=
<div style=3D"font-s=
ize: initial; font-family: Calibri, 'Slate Pro', sans-serif, sans-serif; co=
lor: rgb(31, 73, 125); text-align: initial; background-color: rgb(255, 255,=
255);">Sent from my BlackBerry portable Babbage&n=
bsp;Device</div> =
=
<table width=3D"100%" style=3D"=
background-color:white;border-spacing:0px;"> <tbody><tr><td colspan=3D"2" s=
tyle=3D"font-size: initial; text-align: initial; background-color: rgb(255,=
255, 255);"> <div style=3D"border-style: solid n=
one none; border-top-color: rgb(181, 196, 223); border-top-width: 1pt; padd=
ing: 3pt 0in 0in; font-family: Tahoma, 'BB Alpha Sans', 'Slate Pro'; font-s=
ize: 10pt;"> <div><b>From: </b>gogu</div><div><b>Sent: </b>Wednesday, Febr=
uary 6, 2019 9:44 PM</div><div><b>To: </b>ISO C++ Standard - Future Proposa=
ls</div><div><b>Reply To: </b>std-proposals@isocpp.org</div><div><b>Subject=
: </b>[std-proposals] std::map augmentation</div></div></td></tr></tbody></=
table><div style=3D"border-style: solid none none; border-top-color: rgb(18=
6, 188, 209); border-top-width: 1pt; font-size: initial; text-align: initia=
l; background-color: rgb(255, 255, 255);"></div><br><div id=3D"_originalCon=
tent" style=3D""><div dir=3D"ltr"><div>Make std::map an order statistic tre=
e. Add another template parameter to std::map before the allocator type tha=
t will decide wether or not std::map will be an order statistic tree. Memor=
y will not be wasted. A second node type will be defined in the implementat=
ion that also contains the size of the subtree rooted at the node.<br></div=
><div><br> https://en.wikipedia.org/wiki/Order_statistic_tree</div><div><br=
></div><div>The std::map should have two other functions, called select and=
rank that behave as the wikipedia article says. These should be disabled u=
sing std::enable_if_t/concepts on the parameter that decides if the map is =
an order statistic tree or not. Updating the size of the subtree of a node =
could be done inside of the already defined functions using if constexpr in=
side the function. The body of the compile-time if would update that size f=
or each node on the path down to the insertion point.<br></div><div><br></d=
iv><div>What do you guys think?<br></div></div>
<p></p>
-- <br>
You received this message because you are subscribed to the Google Groups "=
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/ce18cc74-9116-4da6-b320-fe2b4715b1d6%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.goo=
gle.com/a/isocpp.org/d/msgid/std-proposals/ce18cc74-9116-4da6-b320-fe2b4715=
b1d6%40isocpp.org</a>.<br>
<br><!--end of _originalContent --></div></body></html>
<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/20190207033735.5222481.23704.70753%40=
gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com=
/a/isocpp.org/d/msgid/std-proposals/20190207033735.5222481.23704.70753%40gm=
ail.com</a>.<br />
.
Author: Bengt Gustafsson <bengt.gustafsson@beamways.com>
Date: Thu, 7 Feb 2019 23:06:54 -0800 (PST)
Raw View
------=_Part_184_428170984.1549609615024
Content-Type: text/plain; charset="UTF-8"
Yes, this is the situation concepts were designed for. Make it a separate class fulfilling the concepts of a map.
What is the use case of the new functionality?
Also note that flat_map trivially implements this by iterator arithmetics.
--
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/e54a7dec-c1f2-4c2d-a807-f9f63ddf9596%40isocpp.org.
------=_Part_184_428170984.1549609615024--
.
Author: gogu <valeriu.smerica@my.fmi.unibuc.ro>
Date: Sat, 9 Feb 2019 06:19:22 -0800 (PST)
Raw View
------=_Part_718_1178703817.1549721962344
Content-Type: multipart/alternative;
boundary="----=_Part_719_688725448.1549721962344"
------=_Part_719_688725448.1549721962344
Content-Type: text/plain; charset="UTF-8"
The use case would be the same as the one of
std::nth_element. Between insertions and deletes, some guy wants to obtain
the rank of some element in O(log n). Flat_map indeed has it, but
insertions are slow.
On Friday, 8 February 2019 09:06:55 UTC+2, Bengt Gustafsson wrote:
>
> Yes, this is the situation concepts were designed for. Make it a separate
> class fulfilling the concepts of a map.
>
> What is the use case of the new functionality?
>
> Also note that flat_map trivially implements this by iterator arithmetics.
>
>
--
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/14ed3e66-5ac6-4de1-b965-01d4294574bf%40isocpp.org.
------=_Part_719_688725448.1549721962344
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">The use case would be the same as the one of <br><h1 id=3D=
"firstHeading" class=3D"firstHeading"><span style=3D"font-size:0.7em; line-=
height:130%">std::</span>nth_element. Between insertions and deletes, some =
guy wants to obtain the rank of some element in O(log n). Flat_map indeed h=
as it, but insertions are slow.<br></h1><br>On Friday, 8 February 2019 09:0=
6:55 UTC+2, Bengt Gustafsson wrote:<blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;">Yes, this is the situation concepts were designed for. Make it a sepa=
rate class fulfilling the concepts of a map.<p>What is the use case of the =
new functionality?</p><p>Also note that flat_map trivially implements this =
by iterator arithmetics.</p><p></p></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/14ed3e66-5ac6-4de1-b965-01d4294574bf%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/14ed3e66-5ac6-4de1-b965-01d4294574bf=
%40isocpp.org</a>.<br />
------=_Part_719_688725448.1549721962344--
------=_Part_718_1178703817.1549721962344--
.