------=_Part_218_5966730.1380814153699
Content-Type: text/plain; charset=ISO-8859-1

Hello,

I'm trying to design and implement some computational geometry algorithm in
C++, for an X algorithm i need the AVL Tree data structure, which provide a
logarithmic search time.
Is this data structure provided in C++ ISO Standard?

Can i propose to implement such data structure?

Thank you very much.

--

---
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_218_5966730.1380814153699
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hello,<br><br>I'm trying to design and implement some comp=
utational geometry algorithm in C++, for an X algorithm i need the AVL Tree=
 data structure, which provide a logarithmic search time.<br>Is this data s=
tructure provided in C++ ISO Standard?<br><br>Can i propose to implement su=
ch data structure?<br><br>Thank you very much.<br></div>

<p></p>

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

------=_Part_218_5966730.1380814153699--

.

--bcaec501633f1088bd04e7dac990
Content-Type: text/plain; charset=ISO-8859-1

In the last meeting I made a presentation of paper N3700 which covers
hierarchical data structures. In particular it include an AVL adaptor <
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html#tree.tree.adaptors.balance.avltree
>.

At the meeting the consensus was that they needed to see compelling use
cases that prove what decisions need to be made for the interface and
subsequent wording for the standard. I would love it if you could discuss
what your use case is.

Rene.


On Thu, Oct 3, 2013 at 10:29 AM, <luca.gagliano.1988@gmail.com> wrote:

> Hello,
>
> I'm trying to design and implement some computational geometry algorithm
> in C++, for an X algorithm i need the AVL Tree data structure, which
> provide a logarithmic search time.
> Is this data structure provided in C++ ISO Standard?
>
> Can i propose to implement such data structure?
>
> Thank you very much.
>
> --
>
> ---
> 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/.
>



--
--
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

--

---
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/.

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

<div dir=3D"ltr">In the last meeting I made a presentation of paper N3700 w=
hich covers hierarchical data structures. In particular it include an AVL a=
daptor &lt;<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/20=
13/n3700.html#tree.tree.adaptors.balance.avltree">http://www.open-std.org/j=
tc1/sc22/wg21/docs/papers/2013/n3700.html#tree.tree.adaptors.balance.avltre=
e</a>&gt;.<div>
<br></div><div>At the meeting the consensus was that they needed to see com=
pelling use cases that prove what decisions need to be made for the interfa=
ce and subsequent wording for the standard. I would love it if you could di=
scuss what your use case is.</div>
<div><br></div><div>Rene.</div></div><div class=3D"gmail_extra"><br><br><di=
v class=3D"gmail_quote">On Thu, Oct 3, 2013 at 10:29 AM,  <span dir=3D"ltr"=
>&lt;<a href=3D"mailto:luca.gagliano.1988@gmail.com" target=3D"_blank">luca=
..gagliano.1988@gmail.com</a>&gt;</span> wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr">Hello,<br><br>I&#39;m tryin=
g to design and implement some computational geometry algorithm in C++, for=
 an X algorithm i need the AVL Tree data structure, which provide a logarit=
hmic search time.<br>
Is this data structure provided in C++ ISO Standard?<br><br>Can i propose t=
o implement such data structure?<br><br>Thank you very much.<span class=3D"=
HOEnZb"><font color=3D"#888888"><br></font></span></div><span class=3D"HOEn=
Zb"><font color=3D"#888888">

<p></p>

-- <br>
=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</font></span></blockquote></div><br><br clear=3D"all"><div><br></div>-- <b=
r>-- <br>-- Grafik - Don&#39;t Assume Anything<br>-- Redshift Software, Inc=
.. - <a href=3D"http://redshift-software.com">http://redshift-software.com</=
a><br>
-- rrivera/<a href=3D"http://acm.org">acm.org</a> - grafik/<a href=3D"http:=
//redshift-software.com">redshift-software.com</a><br>-- 102708583/icq - gr=
afikrobot/aim - grafikrobot/yahoo
</div>

<p></p>

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

--bcaec501633f1088bd04e7dac990--

.

--047d7bd756e21ec5e604e7db26ed
Content-Type: text/plain; charset=ISO-8859-1

Do the std::map or std::set containers meet your needs? They are not
mandated to be AVL trees -- red-black tress are okay too -- but they do
provide lg n search time.

Billy O'Neal
https://github.com/BillyONeal/ <https://bitbucket.org/BillyONeal/>
http://stackoverflow.com/users/82320/billy-oneal
Malware Response Instructor - BleepingComputer.com


On Thu, Oct 3, 2013 at 11:59 AM, Rene Rivera <grafikrobot@gmail.com> wrote:

> In the last meeting I made a presentation of paper N3700 which covers
> hierarchical data structures. In particular it include an AVL adaptor <
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html#tree.tree.adaptors.balance.avltree
> >.
>
> At the meeting the consensus was that they needed to see compelling use
> cases that prove what decisions need to be made for the interface and
> subsequent wording for the standard. I would love it if you could discuss
> what your use case is.
>
> Rene.
>
>
> On Thu, Oct 3, 2013 at 10:29 AM, <luca.gagliano.1988@gmail.com> wrote:
>
>> Hello,
>>
>> I'm trying to design and implement some computational geometry algorithm
>> in C++, for an X algorithm i need the AVL Tree data structure, which
>> provide a logarithmic search time.
>> Is this data structure provided in C++ ISO Standard?
>>
>> Can i propose to implement such data structure?
>>
>> Thank you very much.
>>
>> --
>>
>> ---
>> 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/.
>>
>
>
>
> --
> --
> -- Grafik - Don't Assume Anything
> -- Redshift Software, Inc. - http://redshift-software.com
> -- rrivera/acm.org - grafik/redshift-software.com
> -- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
>
> --
>
> ---
> 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/.
>

--

---
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/.

--047d7bd756e21ec5e604e7db26ed
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Do the std::map or std::set containers meet your needs? Th=
ey are not mandated to be AVL trees -- red-black tress are okay too -- but =
they do provide lg n search time.</div><div class=3D"gmail_extra"><br clear=
=3D"all">

<div><div dir=3D"ltr"><div>Billy O&#39;Neal</div><div><a href=3D"https://bi=
tbucket.org/BillyONeal/" target=3D"_blank">https://github.com/BillyONeal/</=
a></div><div><a href=3D"http://stackoverflow.com/users/82320/billy-oneal" t=
arget=3D"_blank">http://stackoverflow.com/users/82320/billy-oneal</a></div>

<div>Malware Response Instructor - BleepingComputer.com</div></div></div>
<br><br><div class=3D"gmail_quote">On Thu, Oct 3, 2013 at 11:59 AM, Rene Ri=
vera <span dir=3D"ltr">&lt;<a href=3D"mailto:grafikrobot@gmail.com" target=
=3D"_blank">grafikrobot@gmail.com</a>&gt;</span> wrote:<br><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pad=
ding-left:1ex">

<div dir=3D"ltr">In the last meeting I made a presentation of paper N3700 w=
hich covers hierarchical data structures. In particular it include an AVL a=
daptor &lt;<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/20=
13/n3700.html#tree.tree.adaptors.balance.avltree" target=3D"_blank">http://=
www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html#tree.tree.adapt=
ors.balance.avltree</a>&gt;.<div>


<br></div><div>At the meeting the consensus was that they needed to see com=
pelling use cases that prove what decisions need to be made for the interfa=
ce and subsequent wording for the standard. I would love it if you could di=
scuss what your use case is.</div>


<div><br></div><div>Rene.</div></div><div class=3D"gmail_extra"><div><div c=
lass=3D"h5"><br><br><div class=3D"gmail_quote">On Thu, Oct 3, 2013 at 10:29=
 AM,  <span dir=3D"ltr">&lt;<a href=3D"mailto:luca.gagliano.1988@gmail.com"=
 target=3D"_blank">luca.gagliano.1988@gmail.com</a>&gt;</span> wrote:<br>


<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;padding=
-left:1ex;border-left-color:rgb(204,204,204);border-left-width:1px;border-l=
eft-style:solid"><div dir=3D"ltr">Hello,<br><br>I&#39;m trying to design an=
d implement some computational geometry algorithm in C++, for an X algorith=
m i need the AVL Tree data structure, which provide a logarithmic search ti=
me.<br>


Is this data structure provided in C++ ISO Standard?<br><br>Can i propose t=
o implement such data structure?<br><br>Thank you very much.<span><font col=
or=3D"#888888"><br></font></span></div><span><font color=3D"#888888">

<p></p>

-- <br>
=A0<br>
--- <br>
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals%2Bunsubscribe@isocpp.org" target=3D=
"_blank">std-proposals+unsubscribe@isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org" target=3D"_blank">std-proposals@isocpp.org</a>.<br>
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/" target=3D"_blank">http://groups.google.com/a/isocpp.org/gro=
up/std-proposals/</a>.<br>
</font></span></blockquote></div><br><br clear=3D"all"><div><br></div></div=
></div><span class=3D"HOEnZb"><font color=3D"#888888">-- <br>-- <br>-- Graf=
ik - Don&#39;t Assume Anything<br>-- Redshift Software, Inc. - <a href=3D"h=
ttp://redshift-software.com" target=3D"_blank">http://redshift-software.com=
</a><br>


-- rrivera/<a href=3D"http://acm.org" target=3D"_blank">acm.org</a> - grafi=
k/<a href=3D"http://redshift-software.com" target=3D"_blank">redshift-softw=
are.com</a><br>-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo
</font></span></div><div class=3D"HOEnZb"><div class=3D"h5">

<p></p>

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

<p></p>

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

--047d7bd756e21ec5e604e7db26ed--

.

------=_Part_2376_6366581.1381077012481
Content-Type: text/plain; charset=ISO-8859-1

On Thursday, October 3, 2013 2:59:28 PM UTC-4, Rene Rivera wrote:

> In the last meeting I made a presentation of paper N3700 which covers
> hierarchical data structures. In particular it include an AVL adaptor <
> http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3700.html#tree.tree.adaptors.balance.avltree
> >.
>
> At the meeting the consensus was that they needed to see compelling use
> cases that prove what decisions need to be made for the interface and
> subsequent wording for the standard. I would love it if you could discuss
> what your use case is.
>

We use an object library that uses AVL trees for smart pointer sets, smart
pointer hash tables, and smart pointer maps.  The maps contain dual AVL
trees, one by first pointer order, once by second pointer order.  It is
mostly conformant with the STL interfaces now.  It does use a different
iterator model. In particular, the iterators know the container they come
from, and you can ask them if they're valid() rather than comparing them
against end().

Though this isn't the version we use, it has been released as an open
source library at SourceForge, and you may find it useful.
http://sourceforge.net/projects/gems-pp/
The files you are looking for are Containers/AVLTree*.*.

--

---
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_2376_6366581.1381077012481
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><span style=3D"font-size: 13px;">On Thursday, October 3, 2=
013 2:59:28 PM UTC-4, Rene Rivera wrote:</span><br><blockquote class=3D"gma=
il_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid=
;padding-left: 1ex;"><div dir=3D"ltr">In the last meeting I made a presenta=
tion of paper N3700 which covers hierarchical data structures. In particula=
r it include an AVL adaptor &lt;<a href=3D"http://www.open-std.org/jtc1/sc2=
2/wg21/docs/papers/2013/n3700.html#tree.tree.adaptors.balance.avltree" targ=
et=3D"_blank">http://www.open-std.org/jtc1/<wbr>sc22/wg21/docs/papers/2013/=
<wbr>n3700.html#tree.tree.adaptors.<wbr>balance.avltree</a>&gt;.<div>
<br></div><div>At the meeting the consensus was that they needed to see com=
pelling use cases that prove what decisions need to be made for the interfa=
ce and subsequent wording for the standard. I would love it if you could di=
scuss what your use case is.</div></div></blockquote><div><br></div><div>We=
 use an object&nbsp;<span style=3D"font-size: 13px;">library</span><span st=
yle=3D"font-size: 13px;">&nbsp;</span><span style=3D"font-size: 13px;">that=
 uses AVL trees for smart pointer sets, smart pointer hash tables, and smar=
t pointer maps. &nbsp;The maps contain dual AVL trees, one by first pointer=
 order, once by second pointer order. &nbsp;It is mostly conformant with th=
e STL interfaces now. &nbsp;It does use a different iterator model. In part=
icular, the iterators know the container they come from, and you can ask th=
em if they're valid() rather than comparing them against end().</span></div=
><div><br></div><div>Though this isn't the version we use, it has been rele=
ased as an open source library at SourceForge, and you may find it useful.<=
/div><div><a href=3D"http://sourceforge.net/projects/gems-pp/">http://sourc=
eforge.net/projects/gems-pp/</a><br></div><div>The files you are looking fo=
r are Containers/AVLTree*.*.</div><div><br></div><blockquote class=3D"gmail=
_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;p=
adding-left: 1ex;">
</blockquote></div>

<p></p>

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

------=_Part_2376_6366581.1381077012481--

.

------=_Part_1705_32127577.1381094443080
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

3 oct 2013 =D0=B3., 19:29:13 UTC+4 luca.gagl...@gmail.com:
>
> I'm trying to design and implement some computational geometry algorithm=
=20
> in C++, for an X algorithm i need the AVL Tree data structure, which=20
> provide a logarithmic search time.
>

If std::map/set does not fit for your needs, then you can look also to=20
avl_set, avl_multiset and avltree in boost -=20
http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive/avl_set_multiset.ht=
ml=20
..

--=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_1705_32127577.1381094443080
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">3 oct 2013&nbsp;=D0=B3., 19:29:13 UTC+4 luca.gagl...@gmail=
..com:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">I'm tryi=
ng to design and implement some computational geometry algorithm in C++, fo=
r an X algorithm i need the AVL Tree data structure, which provide a logari=
thmic search time.<br></div></blockquote><div><br>If std::map/set does not =
fit for your needs, then you can look also to avl_set, avl_multiset and avl=
tree in boost - http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive/avl=
_set_multiset.html .<br></div></div>

<p></p>

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

------=_Part_1705_32127577.1381094443080--

.

------=_Part_2745_15004064.1381134076978
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

I think there are basically two types of uses of hierarchical data=20
structures, and they are quite different.

A is "I need an associative contanier with a logarithmic find time".

B is "I have data with hierarchical relationships that I want to represent"=
..

In the current set of suggestions for the standard we have both of these=20
types, the first represented by N3700 on AVL trees and similar, and the=20
other N3693 on file systems (and thus directory hierarchies).

What's a bit strange to me is that N3700 introduces a notion of cursor,=20
which is a kind of iterator over one level of a tree, while for the purpose=
=20
A above is not needed and seems to make the visible design over-complex.=20
Something like a cursor is of course needed inside but according to N3700=
=20
begin() returns a cursor and not an iterator over the entire tree, so the=
=20
level-iness of the underlying data structure is exposed, which is not what=
=20
the A use case wants. At the same time, at least for B-tree implementation=
=20
and red-black implementation the numbrer of entries on each level is set by=
=20
the data structure and not by the application so the data structure is not=
=20
useful for the B use case.

In N3693 the cursor concept is not used, instead there are=20
directory_iterators and recursive_directory_iterators to fulfil similar=20
purposes.

To me it would seem more logical that the trees of N3700 returned the=20
recursive iterators that are defined in the paper and work with cursors as=
=20
a subordinate tool. Then they could be used as drop in replacements for map=
=20
and set when more control over the exact implementation is needed.

 It would then be logical that the directory objects of N3693 had cursors=
=20
which were compatible with the iterators of N3700 so that these could be=20
used to implement recursive directory traversal when needed.

In addition it seems to exist a need for a more general type B data=20
structure where the user can define how many elements to store in each=20
level. I'm not certain if this can be made general enough to fit into the=
=20
standard, though.


Den s=C3=B6ndagen den 6:e oktober 2013 kl. 23:20:43 UTC+2 skrev Evgeny Pana=
syuk:
>
> 3 oct 2013 =D0=B3., 19:29:13 UTC+4 luca.gagl...@gmail.com:
>>
>> I'm trying to design and implement some computational geometry algorithm=
=20
>> in C++, for an X algorithm i need the AVL Tree data structure, which=20
>> provide a logarithmic search time.
>>
>
> If std::map/set does not fit for your needs, then you can look also to=20
> avl_set, avl_multiset and avltree in boost -=20
> http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive/avl_set_multiset.=
html.
>

--=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_2745_15004064.1381134076978
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I think there are basically two types of uses of hierarchi=
cal data structures, and they are quite different.<div><br></div><div>A is =
"I need an associative contanier with a logarithmic find time".</div><div><=
br></div><div>B is "I have data with hierarchical relationships that I want=
 to represent".</div><div><br></div><div>In the current set of suggestions =
for the standard we have both of these types, the first represented by N370=
0 on AVL trees and similar, and the other N3693 on file systems (and thus d=
irectory hierarchies).</div><div><br></div><div>What's a bit strange to me =
is that N3700 introduces a notion of cursor, which is a kind of iterator ov=
er one level of a tree, while for the purpose A above is not needed and see=
ms to make the visible design over-complex. Something like a cursor is of c=
ourse needed inside but according to N3700 begin() returns a cursor and not=
 an iterator over the entire tree, so the level-iness of the underlying dat=
a structure is exposed, which is not what the A use case wants. At the same=
 time, at least for B-tree implementation and red-black implementation the =
numbrer of entries on each level is set by the data structure and not by th=
e application so the data structure is not useful for the B use case.</div>=
<div><br></div><div>In N3693 the cursor concept is not used, instead there =
are directory_iterators and recursive_directory_iterators to fulfil similar=
 purposes.</div><div><br></div><div>To me it would seem more logical that t=
he trees of N3700 returned the recursive iterators that are defined in the =
paper and work with cursors as a subordinate tool. Then they could be used =
as drop in replacements for map and set when more control over the exact im=
plementation is needed.</div><div><br></div><div>&nbsp;It would then be log=
ical that the directory objects of N3693 had cursors which were compatible =
with the iterators of N3700 so that these could be used to implement recurs=
ive directory traversal when needed.</div><div><br></div><div>In addition i=
t seems to exist a need for a more general type B data structure where the =
user can define how many elements to store in each level. I'm not certain i=
f this can be made general enough to fit into the standard, though.</div><d=
iv><br><br>Den s=C3=B6ndagen den 6:e oktober 2013 kl. 23:20:43 UTC+2 skrev =
Evgeny Panasyuk:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"lt=
r">3 oct 2013&nbsp;=D0=B3., 19:29:13 UTC+4 <a>luca.gagl...@gmail.com</a>:<b=
lockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-=
left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">I'm trying to design=
 and implement some computational geometry algorithm in C++, for an X algor=
ithm i need the AVL Tree data structure, which provide a logarithmic search=
 time.<br></div></blockquote><div><br>If std::map/set does not fit for your=
 needs, then you can look also to avl_set, avl_multiset and avltree in boos=
t - <a href=3D"http://www.boost.org/doc/libs/1_54_0/doc/html/intrusive/avl_=
set_multiset.html" target=3D"_blank">http://www.boost.org/doc/libs/<wbr>1_5=
4_0/doc/html/intrusive/avl_<wbr>set_multiset.html</a> .<br></div></div></bl=
ockquote></div></div>

<p></p>

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

------=_Part_2745_15004064.1381134076978--

.

On Mon, Oct 7, 2013 at 1:21 AM, Bengt Gustafsson
<bengt.gustafsson@beamways.com> wrote:
> I think there are basically two types of uses of hierarchical data
> structures, and they are quite different.
>
> A is "I need an associative contanier with a logarithmic find time".
>
> B is "I have data with hierarchical relationships that I want to represent".
>
> In the current set of suggestions for the standard we have both of these
> types, the first represented by N3700 on AVL trees and similar,

This claim confuses me. If you just need an associative container with
logarithmic find time, you can use std::map, as Billy O'Neal said, or
a related data structure like btree_map:
https://code.google.com/p/cpp-btree/. What's the use case that needs
direct access to the tree itself?

I interpret N3700 as filling the 'B' use case, although the balancing
methods in it (why aren't these algorithms? where's even the
definition for multiway_tree::rotate?) indicate that Rene also wants
to use it to implement solutions for case 'A'.

--

---
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_188_1823565.1381173171212
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Well, I reread N3700 and it is now quite clear that they want to cater for=
=20
both needs. The B use case is catered for mainly by the nary_tree template=
=20
while the A use case is catered for by the different adaptors towards the=
=20
end of the document, such as avl_tree and b_star_tree. It is complicated=20
but I think it is very promising. I would like to see some indication of=20
how the intend each level of the nary_tree to be implemented. Does it have=
=20
similar properties as a vector, or is it a binary tree in itself?

So one would hope that the file system suggestion's directory tree would=20
have a compatible API with cursors which can be adapted by the same=20
iterator templates to get the different types of traversals. A problem here=
=20
would be that N3693 defines their iterators as InputIterators only, which=
=20
may not be useful for the adaptors. Hopefully this could motivate a=20
"better" type of accessibility to directories, maybe even random access.


Den m=E5ndagen den 7:e oktober 2013 kl. 10:46:32 UTC+2 skrev Jeffrey Yasski=
n:
>
> On Mon, Oct 7, 2013 at 1:21 AM, Bengt Gustafsson=20
> <bengt.gu...@beamways.com <javascript:>> wrote:=20
> > I think there are basically two types of uses of hierarchical data=20
> > structures, and they are quite different.=20
> >=20
> > A is "I need an associative contanier with a logarithmic find time".=20
> >=20
> > B is "I have data with hierarchical relationships that I want to=20
> represent".=20
> >=20
> > In the current set of suggestions for the standard we have both of thes=
e=20
> > types, the first represented by N3700 on AVL trees and similar,=20
>
> This claim confuses me. If you just need an associative container with=20
> logarithmic find time, you can use std::map, as Billy O'Neal said, or=20
> a related data structure like btree_map:=20
> https://code.google.com/p/cpp-btree/. What's the use case that needs=20
> direct access to the tree itself?=20
>
> I interpret N3700 as filling the 'B' use case, although the balancing=20
> methods in it (why aren't these algorithms? where's even the=20
> definition for multiway_tree::rotate?) indicate that Rene also wants=20
> to use it to implement solutions for case 'A'.=20
>

--=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_188_1823565.1381173171212
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div>Well, I reread N3700 and it is now quite clear that t=
hey want to cater for both needs. The B use case is catered for mainly by t=
he nary_tree template while the A use case is catered for by the different =
adaptors towards the end of the document, such as avl_tree and b_star_tree.=
 It is complicated but I think it is very promising. I would like to see so=
me indication of how the intend each level of the nary_tree to be implement=
ed. Does it have similar properties as a vector, or is it a binary tree in =
itself?</div><div><br></div><div>So one would hope that the file system sug=
gestion's directory tree would have a compatible API with cursors which can=
 be adapted by the same iterator templates to get the different types of tr=
aversals. A problem here would be that N3693 defines their iterators as Inp=
utIterators only, which may not be useful for the adaptors. Hopefully this =
could motivate a "better" type of accessibility to directories, maybe even =
random access.</div><div><br></div><br>Den m=E5ndagen den 7:e oktober 2013 =
kl. 10:46:32 UTC+2 skrev Jeffrey Yasskin:<blockquote class=3D"gmail_quote" =
style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-l=
eft: 1ex;">On Mon, Oct 7, 2013 at 1:21 AM, Bengt Gustafsson
<br>&lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"=
t791gnQPYZUJ">bengt.gu...@beamways.com</a><wbr>&gt; wrote:
<br>&gt; I think there are basically two types of uses of hierarchical data
<br>&gt; structures, and they are quite different.
<br>&gt;
<br>&gt; A is "I need an associative contanier with a logarithmic find time=
".
<br>&gt;
<br>&gt; B is "I have data with hierarchical relationships that I want to r=
epresent".
<br>&gt;
<br>&gt; In the current set of suggestions for the standard we have both of=
 these
<br>&gt; types, the first represented by N3700 on AVL trees and similar,
<br>
<br>This claim confuses me. If you just need an associative container with
<br>logarithmic find time, you can use std::map, as Billy O'Neal said, or
<br>a related data structure like btree_map:
<br><a href=3D"https://code.google.com/p/cpp-btree/" target=3D"_blank">http=
s://code.google.com/p/cpp-<wbr>btree/</a>. What's the use case that needs
<br>direct access to the tree itself?
<br>
<br>I interpret N3700 as filling the 'B' use case, although the balancing
<br>methods in it (why aren't these algorithms? where's even the
<br>definition for multiway_tree::rotate?) indicate that Rene also wants
<br>to use it to implement solutions for case 'A'.
<br></blockquote></div>

<p></p>

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

------=_Part_188_1823565.1381173171212--

.