Topic: Policy Based Data Structures
Author: adamant.pwn@gmail.com
Date: Wed, 9 Aug 2017 06:00:28 -0700 (PDT)
Raw View
------=_Part_2684_2070091697.1502283628372
Content-Type: multipart/alternative;
boundary="----=_Part_2685_1983465745.1502283628372"
------=_Part_2685_1983465745.1502283628372
Content-Type: text/plain; charset="UTF-8"
Hello, everyone! There is special kind of structures in SGI STL, namely
policy based data structures. You can see the manual here
<https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html>.
It is a library of policy-based elementary data structures designed for
high-performance, flexibility, semantic safety, and conformance to the
corresponding containers in std. It provides very flexible and generic
concept of data structures like hash tables, balanced binary trees, heaps,
tries, etc. Also it has some implementations of those featuring maps based
on patricia tries, set containers with order_of_key and find_by_order
functions (essentials missed in std set and map) based on red-black or
splay trees and some more. Using this library programmer can take balanced
binary tree out of the box, write update policy for metadata (i.e. function
which calculates metadata in some vertex given metadata in it and its
children), balancing will be maintained automatically. Using this library
it would be easy to make generic balanced tree handling split/merge
operations or range queries or anything else which could be efficiently
handled by balanced trees with less efforts.
So what do you think of adding it to the C++ standard?
--
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/a487866a-58f7-4f0a-a005-54ddd014ba2c%40isocpp.org.
------=_Part_2685_1983465745.1502283628372
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hello, everyone! There is special kind of structures in SG=
I STL, namely policy based data structures. You can see the manual=C2=A0<a =
href=3D"https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structu=
res.html">here</a>. It is a library=C2=A0<span style=3D"color: rgb(0, 0, 0)=
; font-family: "Times New Roman"; font-size: medium;">of policy-b=
ased elementary data structures=C2=A0</span><span style=3D"color: rgb(0, 0,=
0); font-family: "Times New Roman"; font-size: medium;">designed=
for high-performance, flexibility, semantic safety, and conformance to the=
corresponding containers in=C2=A0</span><code class=3D"literal" style=3D"c=
olor: rgb(0, 0, 0);">std. It provides very flexible and generic concept of =
data structures like hash tables, balanced binary trees, heaps, tries, etc.=
Also it has some implementations of those featuring maps based on patricia=
tries, set containers with order_of_key and find_by_order functions (essen=
tials missed in std set and map) based on red-black or splay trees and some=
more. Using this library programmer can take balanced binary tree out of t=
he box, write update policy for metadata (i.e. function which calculates me=
tadata in some vertex given metadata in it and its children), balancing wil=
l be maintained automatically. Using this library it would be easy to make =
generic balanced tree handling split/merge operations or range queries or a=
nything else which could be efficiently handled by balanced trees with less=
efforts.</code><div><code class=3D"literal" style=3D"color: rgb(0, 0, 0);"=
><br></code></div><div><code class=3D"literal" style=3D"color: rgb(0, 0, 0)=
;">So what do you think of adding it to the C++ standard?</code></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/a487866a-58f7-4f0a-a005-54ddd014ba2c%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/a487866a-58f7-4f0a-a005-54ddd014ba2c=
%40isocpp.org</a>.<br />
------=_Part_2685_1983465745.1502283628372--
------=_Part_2684_2070091697.1502283628372--
.
Author: Alexander Zaitsev <zamazan4ik@gmail.com>
Date: Wed, 9 Aug 2017 06:03:41 -0700 (PDT)
Raw View
------=_Part_4050_1586729448.1502283821144
Content-Type: multipart/alternative;
boundary="----=_Part_4051_1376062328.1502283821144"
------=_Part_4051_1376062328.1502283821144
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Can you provide us example where these containers will be better and more=
=20
flexible than current std::set/std::map/etc ?
=D1=81=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=D0=B2=D0=B3=D1=83=D1=81=D1=82=D0=
=B0 2017 =D0=B3., 16:00:28 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=
=D0=B0=D1=82=D0=B5=D0=BB=D1=8C adama...@gmail.com=20
=D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
>
> Hello, everyone! There is special kind of structures in SGI STL, namely=
=20
> policy based data structures. You can see the manual here=20
> <https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.h=
tml>.=20
> It is a library of policy-based elementary data structures designed for=
=20
> high-performance, flexibility, semantic safety, and conformance to the=20
> corresponding containers in std. It provides very flexible and generic=20
> concept of data structures like hash tables, balanced binary trees, heaps=
,=20
> tries, etc. Also it has some implementations of those featuring maps base=
d=20
> on patricia tries, set containers with order_of_key and find_by_order=20
> functions (essentials missed in std set and map) based on red-black or=20
> splay trees and some more. Using this library programmer can take balance=
d=20
> binary tree out of the box, write update policy for metadata (i.e. functi=
on=20
> which calculates metadata in some vertex given metadata in it and its=20
> children), balancing will be maintained automatically. Using this library=
=20
> it would be easy to make generic balanced tree handling split/merge=20
> operations or range queries or anything else which could be efficiently=
=20
> handled by balanced trees with less efforts.
>
> So what do you think of adding it to the C++ standard?
>
--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/9986a7fa-e4f5-4852-a524-400f8b07763a%40isocpp.or=
g.
------=_Part_4051_1376062328.1502283821144
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Can you provide us example where these containers will be =
better and more flexible than current std::set/std::map/etc ?<br><br>=D1=81=
=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=D0=B2=D0=B3=D1=83=D1=81=D1=82=D0=B0 2017=
=D0=B3., 16:00:28 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=
=D1=82=D0=B5=D0=BB=D1=8C adama...@gmail.com =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=
=D0=B0=D0=BB:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-le=
ft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">=
Hello, everyone! There is special kind of structures in SGI STL, namely pol=
icy based data structures. You can see the manual=C2=A0<a href=3D"https://g=
cc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.html" target=
=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D'https://www.go=
ogle.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2Flibstdc%2B%2B%2F=
manual%2Fpolicy_data_structures.html\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQj=
CNEDwwVU_pe3jIDVDJoQRUf18kQp8A';return true;" onclick=3D"this.href=3D&#=
39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2=
Flibstdc%2B%2B%2Fmanual%2Fpolicy_data_structures.html\x26sa\x3dD\x26sntz\x3=
d1\x26usg\x3dAFQjCNEDwwVU_pe3jIDVDJoQRUf18kQp8A';return true;">here</a>=
.. It is a library=C2=A0<span style=3D"color:rgb(0,0,0);font-family:"Ti=
mes New Roman";font-size:medium">of policy-based elementary data struc=
tures=C2=A0</span><span style=3D"color:rgb(0,0,0);font-family:"Times N=
ew Roman";font-size:medium">designed for high-performance, flexibility=
, semantic safety, and conformance to the corresponding containers in=C2=A0=
</span><code style=3D"color:rgb(0,0,0)">std. It provides very flexible and =
generic concept of data structures like hash tables, balanced binary trees,=
heaps, tries, etc. Also it has some implementations of those featuring map=
s based on patricia tries, set containers with order_of_key and find_by_ord=
er functions (essentials missed in std set and map) based on red-black or s=
play trees and some more. Using this library programmer can take balanced b=
inary tree out of the box, write update policy for metadata (i.e. function =
which calculates metadata in some vertex given metadata in it and its child=
ren), balancing will be maintained automatically. Using this library it wou=
ld be easy to make generic balanced tree handling split/merge operations or=
range queries or anything else which could be efficiently handled by balan=
ced trees with less efforts.</code><div><code style=3D"color:rgb(0,0,0)"><b=
r></code></div><div><code style=3D"color:rgb(0,0,0)">So what do you think o=
f adding it to the C++ standard?</code></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/9986a7fa-e4f5-4852-a524-400f8b07763a%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/9986a7fa-e4f5-4852-a524-400f8b07763a=
%40isocpp.org</a>.<br />
------=_Part_4051_1376062328.1502283821144--
------=_Part_4050_1586729448.1502283821144--
.
Author: adamant.pwn@gmail.com
Date: Wed, 9 Aug 2017 06:15:39 -0700 (PDT)
Raw View
------=_Part_5266_721855248.1502284539893
Content-Type: multipart/alternative;
boundary="----=_Part_5267_782122276.1502284539893"
------=_Part_5267_782122276.1502284539893
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
One very obvious example is with order_of_key and find_by_order functions.=
=20
As you know, iterators in std::set are bidirectional, so you can't easily=
=20
find k-th element in set or calculate the distance between two elements in=
=20
O(log n). But with pbds you can! Here <http://ideone.com/u7AoJ1> is the=20
example. Also you can read some overview of library here=20
<http://codeforces.com/blog/entry/11080> and here=20
<http://codeforces.com/blog/entry/13279> with some more examples provided,=
=20
including using of owns update policies with metadata.=20
=D1=81=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=D0=B2=D0=B3=D1=83=D1=81=D1=82=D0=
=B0 2017 =D0=B3., 16:03:41 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=
=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Alexander Zaitsev=20
=D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
>
> Can you provide us example where these containers will be better and more=
=20
> flexible than current std::set/std::map/etc ?
>
> =D1=81=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=D0=B2=D0=B3=D1=83=D1=81=D1=82=D0=
=B0 2017 =D0=B3., 16:00:28 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=
=D0=B0=D1=82=D0=B5=D0=BB=D1=8C adama...@gmail.com=20
> =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:
>>
>> Hello, everyone! There is special kind of structures in SGI STL, namely=
=20
>> policy based data structures. You can see the manual here=20
>> <https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures.=
html>.=20
>> It is a library of policy-based elementary data structures designed for=
=20
>> high-performance, flexibility, semantic safety, and conformance to the=
=20
>> corresponding containers in std. It provides very flexible and generic=
=20
>> concept of data structures like hash tables, balanced binary trees, heap=
s,=20
>> tries, etc. Also it has some implementations of those featuring maps bas=
ed=20
>> on patricia tries, set containers with order_of_key and find_by_order=20
>> functions (essentials missed in std set and map) based on red-black or=
=20
>> splay trees and some more. Using this library programmer can take balanc=
ed=20
>> binary tree out of the box, write update policy for metadata (i.e. funct=
ion=20
>> which calculates metadata in some vertex given metadata in it and its=20
>> children), balancing will be maintained automatically. Using this librar=
y=20
>> it would be easy to make generic balanced tree handling split/merge=20
>> operations or range queries or anything else which could be efficiently=
=20
>> handled by balanced trees with less efforts.
>>
>> So what do you think of adding it to the C++ standard?
>>
>
--=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.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/be54355b-3c6d-4000-b223-31a7911063cb%40isocpp.or=
g.
------=_Part_5267_782122276.1502284539893
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">One very obvious example is with order_of_key and find_by_=
order functions. As you know, iterators in std::set are bidirectional, so y=
ou can't easily find k-th element in set or calculate the distance betw=
een two elements in O(log n). But with pbds you can! <a href=3D"http://ideo=
ne.com/u7AoJ1">Here</a>=C2=A0is the example. Also you can read some overvie=
w of library=C2=A0<a href=3D"http://codeforces.com/blog/entry/11080">here</=
a>=C2=A0and=C2=A0<a href=3D"http://codeforces.com/blog/entry/13279">here</a=
>=C2=A0with some more examples provided, including using of owns update pol=
icies with metadata.=C2=A0<br><br>=D1=81=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=
=D0=B2=D0=B3=D1=83=D1=81=D1=82=D0=B0 2017 =D0=B3., 16:03:41 UTC+3 =D0=BF=D0=
=BE=D0=BB=D1=8C=D0=B7=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C Alexander Z=
aitsev =D0=BD=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:<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">Can you provide us example where these=
containers will be better and more flexible than current std::set/std::map=
/etc ?<br><br>=D1=81=D1=80=D0=B5=D0=B4=D0=B0, 9 =D0=B0=D0=B2=D0=B3=D1=83=D1=
=81=D1=82=D0=B0 2017 =D0=B3., 16:00:28 UTC+3 =D0=BF=D0=BE=D0=BB=D1=8C=D0=B7=
=D0=BE=D0=B2=D0=B0=D1=82=D0=B5=D0=BB=D1=8C <a>adama...@gmail.com</a> =D0=BD=
=D0=B0=D0=BF=D0=B8=D1=81=D0=B0=D0=BB:<blockquote class=3D"gmail_quote" styl=
e=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex=
"><div dir=3D"ltr">Hello, everyone! There is special kind of structures in =
SGI STL, namely policy based data structures. You can see the manual=C2=A0<=
a href=3D"https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_struc=
tures.html" rel=3D"nofollow" target=3D"_blank" onmousedown=3D"this.href=3D&=
#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%=
2Flibstdc%2B%2B%2Fmanual%2Fpolicy_data_structures.html\x26sa\x3dD\x26sntz\x=
3d1\x26usg\x3dAFQjCNEDwwVU_pe3jIDVDJoQRUf18kQp8A';return true;" onclick=
=3D"this.href=3D'https://www.google.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.=
org%2Fonlinedocs%2Flibstdc%2B%2B%2Fmanual%2Fpolicy_data_structures.html\x26=
sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEDwwVU_pe3jIDVDJoQRUf18kQp8A';retu=
rn true;">here</a>. It is a library=C2=A0<span style=3D"color:rgb(0,0,0);fo=
nt-family:"Times New Roman";font-size:medium">of policy-based ele=
mentary data structures=C2=A0</span><span style=3D"color:rgb(0,0,0);font-fa=
mily:"Times New Roman";font-size:medium">designed for high-perfor=
mance, flexibility, semantic safety, and conformance to the corresponding c=
ontainers in=C2=A0</span><code style=3D"color:rgb(0,0,0)">std. It provides =
very flexible and generic concept of data structures like hash tables, bala=
nced binary trees, heaps, tries, etc. Also it has some implementations of t=
hose featuring maps based on patricia tries, set containers with order_of_k=
ey and find_by_order functions (essentials missed in std set and map) based=
on red-black or splay trees and some more. Using this library programmer c=
an take balanced binary tree out of the box, write update policy for metada=
ta (i.e. function which calculates metadata in some vertex given metadata i=
n it and its children), balancing will be maintained automatically. Using t=
his library it would be easy to make generic balanced tree handling split/m=
erge operations or range queries or anything else which could be efficientl=
y handled by balanced trees with less efforts.</code><div><code style=3D"co=
lor:rgb(0,0,0)"><br></code></div><div><code style=3D"color:rgb(0,0,0)">So w=
hat do you think of adding it to the C++ standard?</code></div></div></bloc=
kquote></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/be54355b-3c6d-4000-b223-31a7911063cb%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/be54355b-3c6d-4000-b223-31a7911063cb=
%40isocpp.org</a>.<br />
------=_Part_5267_782122276.1502284539893--
------=_Part_5266_721855248.1502284539893--
.