Topic: Parallel operations for associative containers?
Author: NDos Dannyu <ndospark320@naver.com>
Date: Sat, 16 Jan 2016 23:52:02 -0800 (PST)
Raw View
------=_Part_4090_310595851.1453017122841
Content-Type: multipart/alternative;
boundary="----=_Part_4091_29506804.1453017122841"
------=_Part_4091_29506804.1453017122841
Content-Type: text/plain; charset=UTF-8
Because their iterators use O(log n) time to travel a step, they may be
inappropriate to be used with standard algorithms.
So I suggest to add parallel operations for associative containers.
For example, a function that applies function to all of its nodes:
*namespace* std {
*template* <*class* Key, *class* Compare = less<Key>, *class* Allocator
= allocator<Key>>
*class* set {
*private*:
*...*
*class* node; // Let this represent nodes
node *base_node; // Let this be the base node
*template* <*class Func*> *void* *for_all_recursive*(Func &&func,
node *rec) {
*if *(rec == nullptr) *return*;
func(node->data); // apply func to data
auto fut(async(for_all_recursive, forward<Func>(func),
rec->right);
for_all_recursive(forward<Func>(func), node->left);
fut.wait();
}
*...*
*public*:
*...*
*template* <*class Func*> *void **for_all*(Func &&func) {
for_all_recurive(forward<Func>(func), base_node);
}
*...*
};
}
This example is quite impratical, though.
--
---
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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_4091_29506804.1453017122841
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Because=C2=A0their iterators use O(log n) time to tra=
vel a step, they may be inappropriate to be used with standard algorithms.<=
/div><div>So I suggest to add parallel operations for associative container=
s.</div><div>For example, a function that applies function to all of its no=
des:</div><div><b>namespace</b> std {</div><div>=C2=A0=C2=A0=C2=A0 <b>templ=
ate</b> <<b>class</b> Key, <b>class</b> Compare =3D less<Key>, <b>=
class</b> Allocator =3D allocator<Key>></div><div>=C2=A0=C2=A0=C2=
=A0 <b>class</b> set {</div><div>=C2=A0=C2=A0=C2=A0 <b>private</b>:</div><d=
iv>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0<b>class</b> node; // Let this re=
present nodes</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 node *ba=
se_node; // Let this be the base node</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 <b>template</b> <<b>class Func</b>> <b>void</b> <u>fo=
r_all_recursive</u>(Func &&func, node *rec) {</div><div>=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0<b>if </b>(r=
ec =3D=3D nullptr) <b>return</b>;</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 func(node->data); // apply func to =
data</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 auto fut(async(for_all_recursive, forward<Func>(func), rec->=
;right);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 for_all_recursive(forward<Func>(func), node->left);</=
div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
fut.wait();</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }</div><d=
iv>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div><i>=C2=
=A0=C2=A0=C2=A0 </i><b>public</b>:</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0 <i>...</i></div><div><i>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0</i> <b>template</b> <<b>class Func</b>> <b></b><b>void </b><u>=
for_all</u>(Func &&func) {</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 for_all_recurive(forward<Func>(f=
unc), base_node);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }</d=
iv><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div>=C2=
=A0=C2=A0=C2=A0=C2=A0};</div><div>}</div><div><br></div><div>This example i=
s quite impratical, though.</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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_4091_29506804.1453017122841--
------=_Part_4090_310595851.1453017122841--
.
Author: Farid Mehrabi <farid.mehrabi@gmail.com>
Date: Sun, 17 Jan 2016 20:06:34 +0330
Raw View
--001a113a71caa5c7b905298a3fa8
Content-Type: text/plain; charset=UTF-8
I think we need a some fast range or something:
std::set<int> intset;
for(auto i: fast_range(intset))//proposed library feature 'fast_range'
async(func,i);
2016-01-17 11:22 GMT+03:30 NDos Dannyu <ndospark320@naver.com>:
> Because their iterators use O(log n) time to travel a step, they may be
> inappropriate to be used with standard algorithms.
> So I suggest to add parallel operations for associative containers.
> For example, a function that applies function to all of its nodes:
> *namespace* std {
> *template* <*class* Key, *class* Compare = less<Key>, *class*
> Allocator = allocator<Key>>
> *class* set {
> *private*:
> *...*
> *class* node; // Let this represent nodes
> node *base_node; // Let this be the base node
> *template* <*class Func*> *void* *for_all_recursive*(Func &&func,
> node *rec) {
> *if *(rec == nullptr) *return*;
> func(node->data); // apply func to data
> auto fut(async(for_all_recursive, forward<Func>(func),
> rec->right);
> for_all_recursive(forward<Func>(func), node->left);
> fut.wait();
> }
> *...*
> *public*:
> *...*
> *template* <*class Func*> *void **for_all*(Func &&func) {
> for_all_recurive(forward<Func>(func), base_node);
> }
> *...*
> };
> }
>
> This example is quite impratical, though.
>
> --
>
> ---
> 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
> https://groups.google.com/a/isocpp.org/group/std-proposals/.
>
--
how am I supposed to end the twisted road of your hair in such a dark
night??
unless the candle of your face does shed some light upon my way!!!
--
---
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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
--001a113a71caa5c7b905298a3fa8
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"rtl"><div class=3D"gmail_default" style=3D"font-family:'ari=
al narrow',sans-serif;font-size:large" dir=3D"ltr">I think we need a so=
me fast range or something:</div><div class=3D"gmail_default" style=3D"font=
-family:'arial narrow',sans-serif;font-size:large" dir=3D"ltr"><br>=
</div><div class=3D"gmail_default" style=3D"font-family:'arial narrow&#=
39;,sans-serif;font-size:large" dir=3D"ltr">std::set<int> intset;</di=
v><div class=3D"gmail_default" style=3D"font-family:'arial narrow',=
sans-serif;font-size:large" dir=3D"ltr">for(auto i: fast_range(intset))//pr=
oposed library feature 'fast_range'</div><div class=3D"gmail_defaul=
t" style=3D"font-family:'arial narrow',sans-serif;font-size:large" =
dir=3D"ltr">=C2=A0 =C2=A0 =C2=A0 async(func,i);</div></div><div class=3D"gm=
ail_extra"><br><div class=3D"gmail_quote"><div dir=3D"ltr">2016-01-17 11:22=
GMT+03:30 NDos Dannyu <span dir=3D"ltr"><<a href=3D"mailto:ndospark320@=
naver.com" target=3D"_blank">ndospark320@naver.com</a>></span>:</div><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #=
ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>Because=C2=A0their iterat=
ors use O(log n) time to travel a step, they may be inappropriate to be use=
d with standard algorithms.</div><div>So I suggest to add parallel operatio=
ns for associative containers.</div><div>For example, a function that appli=
es function to all of its nodes:</div><div><b>namespace</b> std {</div><div=
>=C2=A0=C2=A0=C2=A0 <b>template</b> <<b>class</b> Key, <b>class</b> Comp=
are =3D less<Key>, <b>class</b> Allocator =3D allocator<Key>>=
;</div><div>=C2=A0=C2=A0=C2=A0 <b>class</b> set {</div><div>=C2=A0=C2=A0=C2=
=A0 <b>private</b>:</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i=
>...</i></div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0<b>class=
</b> node; // Let this represent nodes</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0 node *base_node; // Let this be the base node</div><div>=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <b>template</b> <<b>class Fun=
c</b>> <b>void</b> <u>for_all_recursive</u>(Func &&func, node *r=
ec) {</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0<b>if </b>(rec =3D=3D nullptr) <b>return</b>;</div><div>=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 func(node-&=
gt;data); // apply func to data</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 auto fut(async(for_all_recursive, forward=
<Func>(func), rec->right);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 for_all_recursive(forward<Func&g=
t;(func), node->left);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0 fut.wait();</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0 }</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <=
i>...</i></div><div><i>=C2=A0=C2=A0=C2=A0 </i><b>public</b>:</div><div>=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div><i>=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0</i> <b>template</b> <<b>class Func</b>=
> <b></b><b>void </b><u>for_all</u>(Func &&func) {</div><div>=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 for_all_rec=
urive(forward<Func>(func), base_node);</div><div>=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0 }</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0 <i>...</i></div><div>=C2=A0=C2=A0=C2=A0=C2=A0};</div><div>}</div><di=
v><br></div><div>This example is quite impratical, though.</div></div><span=
class=3D"HOEnZb"><font color=3D"#888888">
<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" 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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/" target=3D"_blank">https://groups.google.com/a/isocpp.org/g=
roup/std-proposals/</a>.<br>
</font></span></blockquote></div><br><br clear=3D"all"><div><br></div>-- <b=
r><div class=3D"gmail_signature"><div dir=3D"rtl"><div><div dir=3D"ltr">how=
am I supposed to end the twisted road of=C2=A0 your hair in such a dark ni=
ght??<br>unless the candle of your face does shed some light upon my way!!!=
<br></div></div></div></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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--001a113a71caa5c7b905298a3fa8--
.
Author: Magnus Fromreide <magfr@lysator.liu.se>
Date: Sun, 17 Jan 2016 21:52:10 +0100
Raw View
On Sun, Jan 17, 2016 at 08:06:34PM +0330, Farid Mehrabi wrote:
> I think we need a some fast range or something:
>
> std::set<int> intset;
> for(auto i: fast_range(intset))//proposed library feature 'fast_range'
> async(func,i);
And what should this fast_range do? Why is it needed?
/MF
> 2016-01-17 11:22 GMT+03:30 NDos Dannyu <ndospark320@naver.com>:
>
> > Because their iterators use O(log n) time to travel a step, they may be
> > inappropriate to be used with standard algorithms.
> > So I suggest to add parallel operations for associative containers.
> > For example, a function that applies function to all of its nodes:
> > *namespace* std {
> > *template* <*class* Key, *class* Compare = less<Key>, *class*
> > Allocator = allocator<Key>>
> > *class* set {
> > *private*:
> > *...*
> > *class* node; // Let this represent nodes
> > node *base_node; // Let this be the base node
> > *template* <*class Func*> *void* *for_all_recursive*(Func &&func,
> > node *rec) {
> > *if *(rec == nullptr) *return*;
> > func(node->data); // apply func to data
> > auto fut(async(for_all_recursive, forward<Func>(func),
> > rec->right);
> > for_all_recursive(forward<Func>(func), node->left);
> > fut.wait();
> > }
> > *...*
> > *public*:
> > *...*
> > *template* <*class Func*> *void **for_all*(Func &&func) {
> > for_all_recurive(forward<Func>(func), base_node);
> > }
> > *...*
> > };
> > }
> >
> > This example is quite impratical, though.
> >
> > --
> >
> > ---
> > 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
> > https://groups.google.com/a/isocpp.org/group/std-proposals/.
> >
>
>
>
> --
> how am I supposed to end the twisted road of your hair in such a dark
> night??
> unless the candle of your face does shed some light upon my way!!!
>
> --
>
> ---
> 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 https://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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: Farid Mehrabi <farid.mehrabi@gmail.com>
Date: Mon, 18 Jan 2016 19:27:47 +0330
Raw View
--001a11c1550cca775d05299dd208
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
2016-01-18 0:22 GMT+03:30 Magnus Fromreide <magfr@lysator.liu.se>:
> On Sun, Jan 17, 2016 at 08:06:34PM +0330, Farid Mehrabi wrote:
> =E2=80=8B=E2=80=8B
> > I think we need a some fast range or something:
> >
> > std::set<int> intset;
> > for(auto i: fast_range(intset))//proposed library feature 'fast_range'
> > async(func,i);
>
> And what should this fast_range do? Why is it needed?
>
in complex containers( the ones involving sorting , normally tree based
ones), normal iteration has the overhead of seeing every node by its
logical order. the proposed feature is supposed to iteratively generate a
set of references - based on the container's structure - that circumvent
the sorting overheads and process nodes out of order to achieve speed
advantage. when sorting is not a demand and some operation is to be
performed on all elements of a container regardless of their logical
order, why should the price of such overhead be paid?
regards,
FM.
--=20
how am I supposed to end the twisted road of your hair in such a dark
night??
unless the candle of your face does shed some light upon my way!!!
--=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 https://groups.google.com/a/isocpp.org/group/std-propos=
als/.
--001a11c1550cca775d05299dd208
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"rtl"><div class=3D"gmail_default" style=3D"direction:ltr;font-f=
amily:'arial narrow',sans-serif;font-size:large"><br></div><div cla=
ss=3D"gmail_extra"><div style=3D"direction:ltr"><br></div><div class=3D"gma=
il_quote"><div dir=3D"ltr">2016-01-18 0:22 GMT+03:30 Magnus Fromreide <span=
dir=3D"ltr"><<a href=3D"mailto:magfr@lysator.liu.se" target=3D"_blank">=
magfr@lysator.liu.se</a>></span>:</div><blockquote class=3D"gmail_quote"=
style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:=
rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div style=3D"di=
rection:ltr">On Sun, Jan 17, 2016 at 08:06:34PM +0330, Farid Mehrabi wrote:=
<div class=3D"gmail_default" style=3D"font-family:'arial narrow',sa=
ns-serif;font-size:large;display:inline">=E2=80=8B=E2=80=8B</div></div><spa=
n class=3D""><div style=3D"direction:ltr">> I think we need a some fast =
range or something:</div><div style=3D"direction:ltr">></div><div style=
=3D"direction:ltr">> std::set<int> intset;</div><div style=3D"dire=
ction:ltr">> for(auto i: fast_range(intset))//proposed library feature &=
#39;fast_range'</div><div style=3D"direction:ltr">>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0async(func,i);</div>
<div style=3D"direction:ltr"><br></div>
</span><div style=3D"direction:ltr">And what should this fast_range do? Why=
is it needed?</div></blockquote><div style=3D"direction:ltr">=C2=A0</div><=
div style=3D"direction:ltr"><div class=3D"gmail_default" style=3D"font-fami=
ly:'arial narrow',sans-serif;font-size:large">in complex containers=
( the ones involving sorting , normally tree based =C2=A0ones), normal iter=
ation has the overhead of seeing every node by its logical order. the propo=
sed feature is supposed to iteratively generate a set of references - based=
on the container's structure - that circumvent the sorting overheads a=
nd process nodes out of order to achieve speed advantage. when sorting is n=
ot a demand and some operation is to be performed on all elements of a cont=
ainer regardless of =C2=A0their logical order, why should the price of such=
overhead be paid?</div><div class=3D"gmail_default" style=3D"font-family:&=
#39;arial narrow',sans-serif;font-size:large"><br></div><div class=3D"g=
mail_default" style=3D"font-family:'arial narrow',sans-serif;font-s=
ize:large">regards,</div><div class=3D"gmail_default" style=3D"font-family:=
'arial narrow',sans-serif;font-size:large">FM.</div></div><div styl=
e=3D"direction:ltr">=C2=A0</div></div><div style=3D"direction:ltr">--=C2=A0=
</div><div class=3D"gmail_signature"><div dir=3D"rtl"><div><div dir=3D"ltr"=
>how am I supposed to end the twisted road of=C2=A0 your hair in such a dar=
k night??<br>unless the candle of your face does shed some light upon my wa=
y!!!<br></div></div></div></div>
</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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--001a11c1550cca775d05299dd208--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Mon, 18 Jan 2016 15:27:24 -0800 (PST)
Raw View
------=_Part_1943_385849748.1453159644675
Content-Type: multipart/alternative;
boundary="----=_Part_1944_1807937837.1453159644675"
------=_Part_1944_1807937837.1453159644675
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Monday, January 18, 2016 at 10:58:28 AM UTC-5, Farid Mehrabi wrote:
>
> 2016-01-18 0:22 GMT+03:30 Magnus Fromreide <ma...@lysator.liu.se=20
> <javascript:>>:
>
>> On Sun, Jan 17, 2016 at 08:06:34PM +0330, Farid Mehrabi wrote:
>> =E2=80=8B=E2=80=8B
>> > I think we need a some fast range or something:
>> >
>> > std::set<int> intset;
>> > for(auto i: fast_range(intset))//proposed library feature 'fast_range'
>> > async(func,i);
>>
>> And what should this fast_range do? Why is it needed?
>>
> =20
> in complex containers( the ones involving sorting , normally tree based=
=20
> ones), normal iteration has the overhead of seeing every node by its=20
> logical order. the proposed feature is supposed to iteratively generate a=
=20
> set of references - based on the container's structure - that circumvent=
=20
> the sorting overheads and process nodes out of order to achieve speed=20
> advantage. when sorting is not a demand and some operation is to be=20
> performed on all elements of a container regardless of their logical=20
> order, why should the price of such overhead be paid?
>
>
Because you can't *not* pay it.
The reason why indexing a tree-based associative iterator has `log(n)`=20
performance is because it is a *tree*. That's the data-structure. It has=20
*nothing* to do with the tree being sorted (that's about how the tree gets=
=20
built and maintained). Well, not directly; they are trees because they're=
=20
required to be sorted, but that's kinda the point.
There's nothing you can do about that performance. There is no order for=20
iterating through a tree without having `log(n)` performance. That's the=20
nature of the beast. Something similar goes for unordered containers. Their=
=20
iterator performance comes from the nature of being a hash table.
If you don't want to pay that cost, use a `flat_set/map`. But we can't make=
=20
other containers have their performance.
--=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 https://groups.google.com/a/isocpp.org/group/std-propos=
als/.
------=_Part_1944_1807937837.1453159644675
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Monday, January 18, 2016 at 10:58:28 AM UTC-5, Farid Mehrabi wrote:<bloc=
kquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-l=
eft: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"rtl"><div><div style=3D=
"direction:ltr"></div><div class=3D"gmail_quote"><div dir=3D"ltr">2016-01-1=
8 0:22 GMT+03:30 Magnus Fromreide <span dir=3D"ltr"><<a href=3D"javascri=
pt:" target=3D"_blank" gdf-obfuscated-mailto=3D"DkYyEIdiFwAJ" rel=3D"nofoll=
ow" onmousedown=3D"this.href=3D'javascript:';return true;" onclick=
=3D"this.href=3D'javascript:';return true;">ma...@lysator.liu.se</a=
>></span>:</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0p=
x 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border=
-left-style:solid;padding-left:1ex"><div style=3D"direction:ltr">On Sun, Ja=
n 17, 2016 at 08:06:34PM +0330, Farid Mehrabi wrote:<div style=3D"font-fami=
ly:'arial narrow',sans-serif;font-size:large;display:inline">=E2=80=
=8B=E2=80=8B</div></div><span><div style=3D"direction:ltr">> I think we =
need a some fast range or something:</div><div style=3D"direction:ltr">>=
</div><div style=3D"direction:ltr">> std::set<int> intset;</div><d=
iv style=3D"direction:ltr">> for(auto i: fast_range(intset))//proposed l=
ibrary feature 'fast_range'</div><div style=3D"direction:ltr">>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0async(func,i);</div>
<div style=3D"direction:ltr"><br></div>
</span><div style=3D"direction:ltr">And what should this fast_range do? Why=
is it needed?</div></blockquote><div style=3D"direction:ltr">=C2=A0</div><=
div style=3D"direction:ltr"><div style=3D"font-family:'arial narrow'=
;,sans-serif;font-size:large">in complex containers( the ones involving sor=
ting , normally tree based =C2=A0ones), normal iteration has the overhead o=
f seeing every node by its logical order. the proposed feature is supposed =
to iteratively generate a set of references - based on the container's =
structure - that circumvent the sorting overheads and process nodes out of =
order to achieve speed advantage. when sorting is not a demand and some ope=
ration is to be performed on all elements of a container regardless of =C2=
=A0their logical order, why should the price of such overhead be paid?</div=
></div></div><br></div></div></blockquote><div><br>Because you can't <i=
>not</i> pay it.<br><br>The reason why indexing a tree-based associative it=
erator has `log(n)` performance is because it is a <i>tree</i>. That's =
the data-structure. It has <i>nothing</i> to do with the tree being sorted =
(that's about how the tree gets built and maintained). Well, not direct=
ly; they are trees because they're required to be sorted, but that'=
s kinda the point.<br><br>There's nothing you can do about that perform=
ance. There is no order for iterating through a tree without having `log(n)=
` performance. That's the nature of the beast. Something similar goes f=
or unordered containers. Their iterator performance comes from the nature o=
f being a hash table.<br><br>If you don't want to pay that cost, use a =
`flat_set/map`. But we can't make other containers have their performan=
ce.<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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_1944_1807937837.1453159644675--
------=_Part_1943_385849748.1453159644675--
.
Author: "T. C." <rs2740@gmail.com>
Date: Mon, 18 Jan 2016 15:39:14 -0800 (PST)
Raw View
------=_Part_932_788294449.1453160355043
Content-Type: multipart/alternative;
boundary="----=_Part_933_1888183689.1453160355043"
------=_Part_933_1888183689.1453160355043
Content-Type: text/plain; charset=UTF-8
On Sunday, January 17, 2016 at 2:52:02 AM UTC-5, NDos Dannyu wrote:
>
> Because their iterators use O(log n) time to travel a step, they may be
> inappropriate to be used with standard algorithms.
>
They don't. Increment a set or map iterator is amortized constant (i.e., a
full traversal takes linear time).
--
---
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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_933_1888183689.1453160355043
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br>On Sunday, January 17, 2016 at 2:52:02 AM UTC-5, NDos =
Dannyu wrote:<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">=
<div>Because=C2=A0their iterators use O(log n) time to travel a step, they =
may be inappropriate to be used with standard algorithms.</div></div></bloc=
kquote><div><br></div><div><br></div><div>They don't. Increment a set o=
r map iterator is amortized constant (i.e., a full traversal takes linear t=
ime).</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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_933_1888183689.1453160355043--
------=_Part_932_788294449.1453160355043--
.
Author: Viacheslav Usov <via.usov@gmail.com>
Date: Tue, 19 Jan 2016 18:19:44 +0100
Raw View
--e89a8fb2020465973a0529b31374
Content-Type: text/plain; charset=UTF-8
On Sun, Jan 17, 2016 at 8:52 AM, NDos Dannyu <ndospark320@naver.com> wrote:
> Because their iterators use O(log n) time to travel a step
This is false. [iterator.requirements.general], #9 states very plainly:
"All the categories of iterators require only those functions that are
realizable for a given category in constant time (amortized)."
Regardless of what you wrote afterwards, this is simply not a valid premise
to build your proposal upon.
Cheers,
V.
--
---
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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
--e89a8fb2020465973a0529b31374
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On S=
un, Jan 17, 2016 at 8:52 AM, NDos Dannyu <span dir=3D"ltr"><<a href=3D"m=
ailto:ndospark320@naver.com" target=3D"_blank">ndospark320@naver.com</a>>=
;</span> wrote:</div><div class=3D"gmail_quote"><br></div><div class=3D"gma=
il_quote">> Because=C2=A0their iterators use O(log n) time to travel a s=
tep<div><br></div><div>This is false.=C2=A0[iterator.requirements.general],=
#9 states very plainly: "All the categories of iterators require only=
those functions that are realizable for a given category in constant
time (amortized)."</div><div><br></div><div>Regardless of what you wro=
te afterwards, this is simply not a valid premise to build your proposal up=
on.</div><div><br></div><div>Cheers,</div><div>V.</div></div></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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--e89a8fb2020465973a0529b31374--
.
Author: Viacheslav Usov <via.usov@gmail.com>
Date: Tue, 19 Jan 2016 18:24:16 +0100
Raw View
--089e0149c94e925a910529b323aa
Content-Type: text/plain; charset=UTF-8
On Tue, Jan 19, 2016 at 12:27 AM, Nicol Bolas <jmckesson@gmail.com> wrote:
> There's nothing you can do about that performance. There is no order for
iterating through a tree without having `log(n)` performance. That's the
nature of the beast.
Following a pointer from one node to another is O (log N)? Because that's
the nature of the beast? You need a better justification I am afraid.
Cheers,
V.
--
---
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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
--089e0149c94e925a910529b323aa
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On T=
ue, Jan 19, 2016 at 12:27 AM, Nicol Bolas <span dir=3D"ltr"><<a href=3D"=
mailto:jmckesson@gmail.com" target=3D"_blank">jmckesson@gmail.com</a>></=
span> wrote:</div><div class=3D"gmail_quote"><br></div><div class=3D"gmail_=
quote">> There's nothing you can do about that performance. There is=
no order for iterating through a tree without having `log(n)` performance.=
That's the nature of the beast.</div><div class=3D"gmail_quote"><br></=
div><div class=3D"gmail_quote">Following a pointer from one node to another=
is O (log N)? Because that's the nature of the beast? You need a bette=
r justification I am afraid.</div><div class=3D"gmail_quote"><br></div><div=
class=3D"gmail_quote">Cheers,</div><div class=3D"gmail_quote">V.</div></di=
v></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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--089e0149c94e925a910529b323aa--
.
Author: Viacheslav Usov <via.usov@gmail.com>
Date: Tue, 19 Jan 2016 18:37:47 +0100
Raw View
--001a11369330f512ed0529b35324
Content-Type: text/plain; charset=UTF-8
More to the point here, some standard library mechanism to get a set of N
disjoint iterator ranges uniformly covering an entire container,
associative or not, would be nice to have. Or perhaps one exists already?
Such ranges can be used by multiple threads independently.
Cheers,
V.
On Sun, Jan 17, 2016 at 8:52 AM, NDos Dannyu <ndospark320@naver.com> wrote:
> Because their iterators use O(log n) time to travel a step, they may be
> inappropriate to be used with standard algorithms.
> So I suggest to add parallel operations for associative containers.
> For example, a function that applies function to all of its nodes:
> *namespace* std {
> *template* <*class* Key, *class* Compare = less<Key>, *class*
> Allocator = allocator<Key>>
> *class* set {
> *private*:
> *...*
> *class* node; // Let this represent nodes
> node *base_node; // Let this be the base node
> *template* <*class Func*> *void* *for_all_recursive*(Func &&func,
> node *rec) {
> *if *(rec == nullptr) *return*;
> func(node->data); // apply func to data
> auto fut(async(for_all_recursive, forward<Func>(func),
> rec->right);
> for_all_recursive(forward<Func>(func), node->left);
> fut.wait();
> }
> *...*
> *public*:
> *...*
> *template* <*class Func*> *void **for_all*(Func &&func) {
> for_all_recurive(forward<Func>(func), base_node);
> }
> *...*
> };
> }
>
> This example is quite impratical, though.
>
> --
>
> ---
> 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
> https://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 https://groups.google.com/a/isocpp.org/group/std-proposals/.
--001a11369330f512ed0529b35324
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">More to the point here, some standard library mechanism to=
get a set of N disjoint iterator ranges uniformly covering an entire conta=
iner, associative or not, would be nice to have. Or perhaps one exists alre=
ady? Such ranges can be used by multiple threads independently.<div><br></d=
iv><div>Cheers,</div><div>V.</div></div><div class=3D"gmail_extra"><br><div=
class=3D"gmail_quote">On Sun, Jan 17, 2016 at 8:52 AM, NDos Dannyu <span d=
ir=3D"ltr"><<a href=3D"mailto:ndospark320@naver.com" target=3D"_blank">n=
dospark320@naver.com</a>></span> wrote:<br><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex=
"><div dir=3D"ltr"><div>Because=C2=A0their iterators use O(log n) time to t=
ravel a step, they may be inappropriate to be used with standard algorithms=
..</div><div>So I suggest to add parallel operations for associative contain=
ers.</div><div>For example, a function that applies function to all of its =
nodes:</div><div><b>namespace</b> std {</div><div>=C2=A0=C2=A0=C2=A0 <b>tem=
plate</b> <<b>class</b> Key, <b>class</b> Compare =3D less<Key>, <=
b>class</b> Allocator =3D allocator<Key>></div><div>=C2=A0=C2=A0=
=C2=A0 <b>class</b> set {</div><div>=C2=A0=C2=A0=C2=A0 <b>private</b>:</div=
><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div>=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0<b>class</b> node; // Let this=
represent nodes</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 node =
*base_node; // Let this be the base node</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0 <b>template</b> <<b>class Func</b>> <b>void</b> <u=
>for_all_recursive</u>(Func &&func, node *rec) {</div><div>=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0<b>if </b=
>(rec =3D=3D nullptr) <b>return</b>;</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 func(node->data); // apply func =
to data</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 auto fut(async(for_all_recursive, forward<Func>(func), rec-=
>right);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 for_all_recursive(forward<Func>(func), node->left)=
;</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0 fut.wait();</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }</div=
><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div><i>=
=C2=A0=C2=A0=C2=A0 </i><b>public</b>:</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0 <i>...</i></div><div><i>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0</i> <b>template</b> <<b>class Func</b>> <b></b><b>void </b>=
<u>for_all</u>(Func &&func) {</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 for_all_recurive(forward<Func>=
;(func), base_node);</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }=
</div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <i>...</i></div><div>=
=C2=A0=C2=A0=C2=A0=C2=A0};</div><div>}</div><div><br></div><div>This exampl=
e is quite impratical, though.</div></div><span class=3D"HOEnZb"><font colo=
r=3D"#888888">
<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" 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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/" target=3D"_blank">https://groups.google.com/a/isocpp.org/g=
roup/std-proposals/</a>.<br>
</font></span></blockquote></div><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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--001a11369330f512ed0529b35324--
.
Author: Farid Mehrabi <farid.mehrabi@gmail.com>
Date: Tue, 19 Jan 2016 21:47:47 +0330
Raw View
--001a113a71ca573fa80529b3e5b6
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
2016-01-19 2:57 GMT+03:30 Nicol Bolas <jmckesson@gmail.com>:
> Because you can't *not* pay it.
>
=E2=80=8BNo, We can.=E2=80=8B
>
> The reason why indexing a tree-based associative iterator has `log(n)`
> performance is because it is a *tree*. That's the data-structure. It has
> *nothing* to do with the tree being sorted (that's about how the tree
> gets built and maintained). Well, not directly; they are trees because
> they're required to be sorted, but that's kinda the point.
>
=E2=80=8BAgain no.
total traversal of a tree =E2=80=8Bwithout iterators is O(N). iterators are
required to keep the order of elements and that might or might not
increase the overhead ( depends on the implementation ). But search and
search-based access in a balanced tree or in the average is O(log(N)).
>
> There's nothing you can do about that performance. There is no order for
> iterating through a tree without having `log(n)` performance.
>
=E2=80=8B
Don't terms 'pre/post/in-order traversal=E2=80=8B'
=E2=80=8Bring any bells?=E2=80=8B
=E2=80=8B
> That's the nature of the beast. Something similar goes for unordered
> containers. Their iterator performance comes from the nature of being a
> hash table.
>
=E2=80=8BOnce more, no=E2=80=8B.
Iterator performance comes from the requirement to keep the order. Node
pointers can be traversed faster.
>
> If you don't want to pay that cost, use a `flat_set/map`. But we can't
> make other containers have their performance.
>
=E2=80=8BTree-based containers are designed to allow fast search and insert=
ion.
That may cause slow performance of iterators.
But when all nodes are to be traversed in an order-insensitive fashion, the
extra overhead of ordered iteration can be avoided.
You are obviously talking about the limitations of current std container
interface, but that is the problem we are discussing an approach towards.
Implementation of many std classes allow other interfacing features too,
but benefits and downsides of these features are point of further
thoughts.=E2=80=8B=E2=80=8B
--=20
how am I supposed to end the twisted road of your hair in such a dark
night??
unless the candle of your face does shed some light upon my way!!!
--=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 https://groups.google.com/a/isocpp.org/group/std-propos=
als/.
--001a113a71ca573fa80529b3e5b6
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"rtl"><div class=3D"gmail_default" style=3D"text-align:left;font=
-family:'arial narrow',sans-serif;font-size:large"><br></div><div c=
lass=3D"gmail_extra"><div style=3D"text-align:left"><br></div><div class=3D=
"gmail_quote"><div dir=3D"ltr">2016-01-19 2:57 GMT+03:30 Nicol Bolas <span =
dir=3D"ltr"><<a href=3D"mailto:jmckesson@gmail.com" target=3D"_blank">jm=
ckesson@gmail.com</a>></span>:</div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204=
,204);border-left-style:solid;border-right-width:1px;border-right-color:rgb=
(204,204,204);border-right-style:solid;padding-left:1ex;padding-right:1ex">=
<div style=3D"text-align:left">Because you can't <i>not</i> pay it.<br>=
</div></blockquote><div style=3D"text-align:left"><br></div><div style=3D"t=
ext-align:left"><div class=3D"gmail_default" style=3D"font-family:'aria=
l narrow',sans-serif;font-size:large" dir=3D"ltr">=E2=80=8BNo, We can.=
=E2=80=8B</div><br></div><div style=3D"text-align:left">=C2=A0<br></div><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0px 0.8ex;border-left-width:=
1px;border-left-color:rgb(204,204,204);border-left-style:solid;border-right=
-width:1px;border-right-color:rgb(204,204,204);border-right-style:solid;pad=
ding-left:1ex;padding-right:1ex"><div><div style=3D"text-align:left"><br></=
div><div style=3D"text-align:left">The reason why indexing a tree-based ass=
ociative iterator has `log(n)` performance is because it is a <i>tree</i>. =
That's the data-structure. It has <i>nothing</i> to do with the tree be=
ing sorted (that's about how the tree gets built and maintained). Well,=
not directly; they are trees because they're required to be sorted, bu=
t that's kinda the point.</div></div></blockquote><div style=3D"text-al=
ign:left"><br></div><div style=3D"text-align:left"><div class=3D"gmail_defa=
ult" style=3D"font-family:'arial narrow',sans-serif;font-size:large=
" dir=3D"ltr">=E2=80=8BAgain no.</div><div class=3D"gmail_default" style=3D=
"font-family:'arial narrow',sans-serif;font-size:large" dir=3D"ltr"=
>total traversal of a tree =E2=80=8Bwithout iterators is O(N). iterators ar=
e required to keep the order of elements and that might or =C2=A0might not =
increase the overhead ( depends on the implementation ). But search and sea=
rch-based access in a balanced tree or in the average is O(log(N)).</div></=
div><div style=3D"text-align:left">=C2=A0</div><blockquote class=3D"gmail_q=
uote" style=3D"margin:0px 0.8ex;border-left-width:1px;border-left-color:rgb=
(204,204,204);border-left-style:solid;border-right-width:1px;border-right-c=
olor:rgb(204,204,204);border-right-style:solid;padding-left:1ex;padding-rig=
ht:1ex"><div style=3D"text-align:left"><br></div><div style=3D"text-align:l=
eft">There's nothing you can do about that performance. There is no ord=
er for iterating through a tree without having `log(n)` performance.=C2=A0<=
/div></blockquote><div style=3D"text-align:left"><br></div><div style=3D"te=
xt-align:left"><div class=3D"gmail_default" style=3D"font-family:'arial=
narrow',sans-serif;font-size:large">=E2=80=8B<div class=3D"gmail_defau=
lt" dir=3D"ltr" style=3D"display:inline">Don't terms 'pre/post/in-o=
rder traversal=E2=80=8B'</div><span style=3D"font-family:arial,sans-ser=
if;font-size:small">=C2=A0</span><div class=3D"gmail_default" dir=3D"ltr" s=
tyle=3D"display:inline">=E2=80=8Bring any bells?=E2=80=8B</div>=E2=80=8B</d=
iv></div><div style=3D"text-align:left">=C2=A0</div><blockquote class=3D"gm=
ail_quote" style=3D"margin:0px 0.8ex;border-left-width:1px;border-left-colo=
r:rgb(204,204,204);border-left-style:solid;border-right-width:1px;border-ri=
ght-color:rgb(204,204,204);border-right-style:solid;padding-left:1ex;paddin=
g-right:1ex"><div style=3D"text-align:left">That's the nature of the be=
ast. Something similar goes for unordered containers. Their iterator perfor=
mance comes from the nature of being a hash table.<br></div></blockquote><d=
iv style=3D"text-align:left"><br></div><div style=3D"text-align:left"><div =
class=3D"gmail_default" style=3D"font-family:'arial narrow',sans-se=
rif;font-size:large" dir=3D"ltr">=E2=80=8BOnce more, no=E2=80=8B.</div><div=
class=3D"gmail_default" style=3D"font-family:'arial narrow',sans-s=
erif;font-size:large" dir=3D"ltr">Iterator performance comes from the requi=
rement to keep the order. Node pointers can be traversed faster.</div></div=
><div style=3D"text-align:left">=C2=A0</div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0px 0.8ex;border-left-width:1px;border-left-color:rgb(20=
4,204,204);border-left-style:solid;border-right-width:1px;border-right-colo=
r:rgb(204,204,204);border-right-style:solid;padding-left:1ex;padding-right:=
1ex"><div><div style=3D"text-align:left"><br></div><div style=3D"text-align=
:left">If you don't want to pay that cost, use a `flat_set/map`. But we=
can't make other containers have their performance.</div></div></block=
quote><div style=3D"text-align:left"><br></div><div style=3D"text-align:lef=
t"><div class=3D"gmail_default" style=3D"font-family:'arial narrow'=
,sans-serif;font-size:large" dir=3D"ltr">=E2=80=8BTree-based containers are=
designed to allow fast search and insertion. That may cause slow performan=
ce of iterators.</div><div class=3D"gmail_default" style=3D"font-family:=
9;arial narrow',sans-serif;font-size:large" dir=3D"ltr">But when all no=
des are to be traversed in an order-insensitive fashion, the extra overhead=
of ordered iteration can be avoided.</div><div class=3D"gmail_default" sty=
le=3D"font-family:'arial narrow',sans-serif;font-size:large" dir=3D=
"ltr"><br></div><div class=3D"gmail_default" style=3D"font-family:'aria=
l narrow',sans-serif;font-size:large" dir=3D"ltr">You are obviously tal=
king about the limitations of current std container interface, but that is =
the problem we are discussing an approach towards. Implementation of many s=
td classes allow other interfacing features too, but benefits and downsides=
of these features are point of further thoughts.=E2=80=8B=E2=80=8B</div></=
div></div><div><div style=3D"text-align:left"><br></div></div><div style=3D=
"text-align:left">--=C2=A0</div><div class=3D"gmail_signature"><div dir=3D"=
rtl"><div><div dir=3D"ltr">how am I supposed to end the twisted road of=C2=
=A0 your hair in such a dark night??<br>unless the candle of your face does=
shed some light upon my way!!!<br></div></div></div></div>
</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"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
--001a113a71ca573fa80529b3e5b6--
.