Topic: Three proposals to improve our containers
Author: euloanty@live.com
Date: Fri, 6 Dec 2013 20:10:01 -0800 (PST)
Raw View
------=_Part_548_23720784.1386389401255
Content-Type: text/plain; charset=ISO-8859-1
1.Give vectors a unsafe_resize, unsafe_push_back, unsafe_emplace_back,
unsafe_insert.
These operations will make less use of "malloc" or new[] and less use of
pointers.
To "unsafe_resize", programmers must make all the elements that they need
construct and deconstruct correctly.
2.In C++11 we have 4 new unordered containers, so ordered containers become
less use.
And std::set,std::map,std::multiset and std::multimap often use RB_TREEs as
their implement.
If we use a order_statistic tree (a kind of RB_TREE that can record size) ,
we could update iterators of ordered associative containers from
bidirectional_iterator to random-access_iterator and its time complexity is
only log n.
Then ordered containers are more useful.
A good example is the famous "Josephus problem".
For more details, please read <<Introduction to Algorithms>>.
3.We can give fast versions of std::list,
std::set,std::map,std::multiset,std::multimap.
We know the size() is not so necessary in these containers.
We can add
std::nosize_list,std::no_size_set,std::nosize_map,std::nosize_multiset,std::nosize_multimap
These fast versions don't record size().
--
---
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_548_23720784.1386389401255
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><p>1.Give vectors a unsafe_resize, unsafe_push_back, unsaf=
e_emplace_back, unsafe_insert.<br>These operations will make less use of "m=
alloc" or new[] and less use of pointers.<br>To "unsafe_resize", programmer=
s must make all the elements that they need construct and deconstruct corre=
ctly.</p><p>2.In C++11 we have 4 new unordered containers, so ord=
ered containers become less use.<br>And std::set,std::map,std::multise=
t and std::multimap often use RB_TREEs as their implement.<br>If we us=
e a order_statistic tree (a kind of RB_TREE that can record size) ,<br=
>we could update iterators of ordered associative containers from bidi=
rectional_iterator to random-access_iterator and its time complexity is onl=
y log n.<br>Then ordered containers are more useful.<br>A good ex=
ample is the famous "Josephus problem".<br>For more details, please read &l=
t;<Introduction to Algorithms>>.</p><p>3.We can give fast versions=
of std::list, std::set,std::map,std::multiset,std::multimap.<br>We know th=
e size() is not so necessary in these containers.</p><p>We can add std::nos=
ize_list,std::no_size_set,std::nosize_map,std::nosize_multiset,std::nosize_=
multimap<br>These fast versions don't record size().<br></p></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 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_548_23720784.1386389401255--
.
Author: "Billy O'Neal" <billy.oneal@gmail.com>
Date: Fri, 6 Dec 2013 21:17:49 -0800
Raw View
--001a11c1db34a6395104eceae4ca
Content-Type: text/plain; charset=ISO-8859-1
These all sound like suggestions for specialized containers, not for
general purpose containers. (Regarding #1, there's a whole thread about
that which has not been met with much support)
Billy O'Neal
https://github.com/BillyONeal/ <https://bitbucket.org/BillyONeal/>
http://stackoverflow.com/users/82320/billy-oneal
Malware Response Instructor - BleepingComputer.com
On Fri, Dec 6, 2013 at 8:10 PM, <euloanty@live.com> wrote:
> 1.Give vectors a unsafe_resize, unsafe_push_back, unsafe_emplace_back,
> unsafe_insert.
> These operations will make less use of "malloc" or new[] and less use of
> pointers.
> To "unsafe_resize", programmers must make all the elements that they need
> construct and deconstruct correctly.
>
> 2.In C++11 we have 4 new unordered containers, so ordered containers
> become less use.
> And std::set,std::map,std::multiset and std::multimap often use RB_TREEs
> as their implement.
> If we use a order_statistic tree (a kind of RB_TREE that can record size) ,
> we could update iterators of ordered associative containers from
> bidirectional_iterator to random-access_iterator and its time complexity is
> only log n.
> Then ordered containers are more useful.
> A good example is the famous "Josephus problem".
> For more details, please read <<Introduction to Algorithms>>.
>
> 3.We can give fast versions of std::list,
> std::set,std::map,std::multiset,std::multimap.
> We know the size() is not so necessary in these containers.
>
> We can add
> std::nosize_list,std::no_size_set,std::nosize_map,std::nosize_multiset,std::nosize_multimap
> These fast versions don't record size().
>
> --
>
> ---
> 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/.
--001a11c1db34a6395104eceae4ca
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">These all sound like suggestions for specialized container=
s, not for general purpose containers. (Regarding #1, there's a whole t=
hread about that which has not been met with much support)</div><div class=
=3D"gmail_extra">
<br clear=3D"all"><div><div dir=3D"ltr"><div>Billy O'Neal</div><div><a =
href=3D"https://bitbucket.org/BillyONeal/" target=3D"_blank">https://github=
..com/BillyONeal/</a></div><div><a href=3D"http://stackoverflow.com/users/82=
320/billy-oneal" target=3D"_blank">http://stackoverflow.com/users/82320/bil=
ly-oneal</a></div>
<div>Malware Response Instructor - BleepingComputer.com</div></div></div>
<br><br><div class=3D"gmail_quote">On Fri, Dec 6, 2013 at 8:10 PM, <span d=
ir=3D"ltr"><<a href=3D"mailto:euloanty@live.com" target=3D"_blank">euloa=
nty@live.com</a>></span> wrote:<br><blockquote class=3D"gmail_quote" sty=
le=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir=3D"ltr"><p>1.Give vectors a unsafe_resize, unsafe_push_back, unsaf=
e_emplace_back, unsafe_insert.<br>These operations will make less use of &q=
uot;malloc" or new[] and less use of pointers.<br>To "unsafe_resi=
ze", programmers must make all the elements that they need construct a=
nd deconstruct correctly.</p>
<p>2.In C++11 we have=A04 new=A0unordered containers, so ordered=A0containe=
rs become less use.<br>And std::set,std::map,std::multiset and std::multima=
p often use=A0RB_TREEs as their implement.<br>If we use a order_statistic t=
ree (a kind of=A0RB_TREE that can record size) ,<br>
we could update iterators of ordered associative=A0containers from bidirect=
ional_iterator to random-access_iterator and its time complexity is only lo=
g n.<br>Then=A0ordered containers=A0are more useful.<br>A good example is t=
he famous "Josephus problem".<br>
For more details, please read <<Introduction to Algorithms>>.</=
p><p>3.We can give fast versions of std::list, std::set,std::map,std::multi=
set,std::multimap.<br>We know the size() is not so necessary in these conta=
iners.</p>
<p>We can add std::nosize_list,std::no_size_set,std::nosize_map,std::nosize=
_multiset,std::nosize_multimap<br>These fast versions don't record size=
().<span class=3D"HOEnZb"><font color=3D"#888888"><br></font></span></p></d=
iv>
<span class=3D"HOEnZb"><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" 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></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 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 />
--001a11c1db34a6395104eceae4ca--
.