------=_Part_670_313577925.1443114020541
Content-Type: multipart/alternative;
 boundary="----=_Part_671_1528361849.1443114020541"

------=_Part_671_1528361849.1443114020541
Content-Type: text/plain; charset=UTF-8

I am currently writing a proposal to make std::sort and std::stable_sort work
with forward and bidirectional iterators. Here is the first incomplete
draft of the proposal:

https://github.com/Morwenn/Sorting-algorithms-proposal/blob/master/sorting-algorithms.pdf

As you can see, some ideas are already there, but some questions remain
unsolved:

   - Why were these functions restricted to random-access iterators?
   - What should be the complexity guarantees for forward iterators?
   - Did I make mistakes? Can I do better?
   - Should I also propose that std::inplace_merge work with forward
   iterators to complete the proposal?
   - What would be its complexity when no extra memory is available?

I intend to complete the proposal with some benchmark results. I already
have implementations of sorting algorithms that work with forward and
bidirectional iterators, but they
are not the most efficient in the World, and I don't always know how to
compute their complexity.

If any of you has clues about parts of the problems, I would be glad to
listen to them and complete the proposal accordingly :)

--

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

<div dir=3D"ltr">I am currently writing a proposal to make <span style=3D"f=
ont-family: courier new,monospace;">std::sort </span>and <span style=3D"fon=
t-family: courier new,monospace;">std::stable_sort </span>work with forward=
 and bidirectional iterators. Here is the first incomplete draft of the pro=
posal:<br><br><a href=3D"https://github.com/Morwenn/Sorting-algorithms-prop=
osal/blob/master/sorting-algorithms.pdf">https://github.com/Morwenn/Sorting=
-algorithms-proposal/blob/master/sorting-algorithms.pdf<br></a><br>As you c=
an see, some ideas are already there, but some questions remain unsolved:<b=
r><ul><li>Why were these functions restricted to random-access iterators?</=
li><li>What should be the complexity guarantees for forward iterators?</li>=
<li>Did I make mistakes? Can I do better?</li><li>Should I also propose tha=
t <span style=3D"font-family: courier new,monospace;">std::inplace_merge </=
span>work with forward iterators to complete the proposal?</li><li>What wou=
ld be its complexity when no extra memory is available?</li></ul>I intend t=
o complete the proposal with some benchmark results. I already have impleme=
ntations of sorting algorithms that work with forward and bidirectional ite=
rators, but they<br>are not the most efficient in the World, and I don&#39;=
t always know how to compute their complexity.<br><br>If any of you has clu=
es about parts of the problems, I would be glad to listen to them and compl=
ete the proposal accordingly :)<br><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&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+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"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_671_1528361849.1443114020541--
------=_Part_670_313577925.1443114020541--

.

--001a113560825d191a0520823a9b
Content-Type: text/plain; charset=UTF-8

On Thu, Sep 24, 2015 at 8:00 PM, Morwenn <morwenn29@gmail.com> wrote:

> I am currently writing a proposal to make std::sort and std::stable_sort work
> with forward and bidirectional iterators. Here is the first incomplete
> draft of the proposal:
>
> As you can see, some ideas are already there, but some questions remain
> unsolved:
>
>    - Why were these functions restricted to random-access iterators?
>
>
  Perhaps it's possible that this is the only generic setting where you
could have generic free functions that efficiently sort without additional
allocation (which implies weaker exception guarantees and reduced
performance). Also std::list's sort has efficient sorting (asymptotically)
with good exception guarantees, but it relies on internal properties of the
iterators, and so has to be a method.
  Incidentally, there seems to be such a question on StackOverflow
<http://stackoverflow.com/questions/4342957/why-does-vector-not-have-sort-method-as-a-member-function-of-vector-while-lis>,
with some answers being similar.

--

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

--001a113560825d191a0520823a9b
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Thu, Sep 24, 2015 at 8:00 PM, Morwenn <span dir=3D"ltr">&lt;<a href=
=3D"mailto:morwenn29@gmail.com" target=3D"_blank">morwenn29@gmail.com</a>&g=
t;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0=
px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);borde=
r-left-style:solid;padding-left:1ex"><div dir=3D"ltr">I am currently writin=
g a proposal to make <span style=3D"font-family:&#39;courier new&#39;,monos=
pace">std::sort </span>and <span style=3D"font-family:&#39;courier new&#39;=
,monospace">std::stable_sort </span>work with forward and bidirectional ite=
rators. Here is the first incomplete draft of the proposal:<br><br>As you c=
an see, some ideas are already there, but some questions remain unsolved:<b=
r><ul><li><font><font>Why were these functions restricted to random-access =
iterators?</font></font></li></ul></div></blockquote><div><br></div><div>=
=C2=A0 Perhaps it&#39;s possible that this is the only generic setting wher=
e you could have generic free functions that efficiently sort without addit=
ional allocation (which implies weaker exception guarantees and reduced per=
formance). Also std::list&#39;s sort has efficient sorting (asymptotically)=
 with good exception guarantees, but it relies on internal properties of th=
e iterators, and so has to be a method. =C2=A0</div><div>=C2=A0 Incidentall=
y, there seems to be <a href=3D"http://stackoverflow.com/questions/4342957/=
why-does-vector-not-have-sort-method-as-a-member-function-of-vector-while-l=
is">such a question on StackOverflow</a>, with some answers being similar.<=
/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&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+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"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

--001a113560825d191a0520823a9b--

.

------=_Part_510_1044555239.1443120234112
Content-Type: multipart/alternative;
 boundary="----=_Part_511_974056567.1443120234112"

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

Le jeudi 24 septembre 2015 20:16:22 UTC+2, Ami Tavory a =C3=A9crit :
>
>   Perhaps it's possible that this is the only generic setting where you=
=20
> could have generic free functions that efficiently sort without additiona=
l=20
> allocation (which implies weaker exception guarantees and reduced=20
> performance). Also std::list's sort has efficient sorting (asymptotically=
)=20
> with good exception guarantees, but it relies on internal properties of t=
he=20
> iterators, and so has to be a method. =20
>   Incidentally, there seems to be such a question on StackOverflow=20
> <http://stackoverflow.com/questions/4342957/why-does-vector-not-have-sort=
-method-as-a-member-function-of-vector-while-lis>,=20
> with some answers being similar.
>

The question on SO doesn't really answer why generic algorithms don't exist=
=20
for forward and bidirectional iterators but why lists have sorting methods.=
=20
As I highlight in the proposal, it's still possible to write generic=20
sorting algorithms for forward and bidirectional iterators while having=20
them recognize std::list and std::forward_list to have both genericity and=
=20
efficiency. I have benchmarks in the making and while the generic=20
algorithms can't beat the specialized list algorithms, even naive=20
impementations can still have decent performances even though I did not=20
optimize them. For example, quicksort is easy to implement and works with=
=20
forward iterators (and can trivially be enhanced to perform an insertion=20
sort on small inputs for bidirectional iterators) and mergesort is still=20
good enough for stable sorting when it can allocate extra memory. These=20
algorithms don't beat the list ones but may still be valuable for other=20
data structures.

My goal with this proposal is to have algorithms to sort any containers=20
with an iterator interface, even user-defined ones, while keeping the=20
efficiency of list algorithms under the hood. We can have more genericity=
=20
with zero overhead with a good impementation :p

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

Le jeudi 24 septembre 2015 20:16:22 UTC+2, Ami Tavory a =C3=A9crit=C2=A0:<b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><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-l=
eft-style:solid;padding-left:1ex"><div dir=3D"ltr"></div></blockquote><div>=
</div><div>=C2=A0 Perhaps it&#39;s possible that this is the only generic s=
etting where you could have generic free functions that efficiently sort wi=
thout additional allocation (which implies weaker exception guarantees and =
reduced performance). Also std::list&#39;s sort has efficient sorting (asym=
ptotically) with good exception guarantees, but it relies on internal prope=
rties of the iterators, and so has to be a method. =C2=A0</div><div>=C2=A0 =
Incidentally, there seems to be <a href=3D"http://stackoverflow.com/questio=
ns/4342957/why-does-vector-not-have-sort-method-as-a-member-function-of-vec=
tor-while-lis" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=
=3D&#39;http://www.google.com/url?q\75http%3A%2F%2Fstackoverflow.com%2Fques=
tions%2F4342957%2Fwhy-does-vector-not-have-sort-method-as-a-member-function=
-of-vector-while-lis\46sa\75D\46sntz\0751\46usg\75AFQjCNHLNUWExVsSFGBdFLb9E=
w2t3CEVWw&#39;;return true;" onclick=3D"this.href=3D&#39;http://www.google.=
com/url?q\75http%3A%2F%2Fstackoverflow.com%2Fquestions%2F4342957%2Fwhy-does=
-vector-not-have-sort-method-as-a-member-function-of-vector-while-lis\46sa\=
75D\46sntz\0751\46usg\75AFQjCNHLNUWExVsSFGBdFLb9Ew2t3CEVWw&#39;;return true=
;">such a question on StackOverflow</a>, with some answers being similar.</=
div></div></div></div></blockquote><div><br>The question on SO doesn&#39;t =
really answer why generic algorithms don&#39;t exist for forward and bidire=
ctional iterators but why lists have sorting methods. As I highlight in the=
 proposal, it&#39;s still possible to write generic sorting algorithms for =
forward and bidirectional iterators while having them recognize <span style=
=3D"font-family: courier new,monospace;">std::list </span>and <span style=
=3D"font-family: courier new,monospace;">std::forward_list </span>to have b=
oth genericity and efficiency. I have benchmarks in the making and while th=
e generic algorithms can&#39;t beat the specialized list algorithms, even n=
aive impementations can still have decent performances even though I did no=
t optimize them. For example, quicksort is easy to implement and works with=
 forward iterators (and can trivially be enhanced to perform an insertion s=
ort on small inputs for bidirectional iterators) and mergesort is still goo=
d enough for stable sorting when it can allocate extra memory. These algori=
thms don&#39;t beat the list ones but may still be valuable for other data =
structures.<br><br>My goal with this proposal is to have algorithms to sort=
 any containers with an iterator interface, even user-defined ones, while k=
eeping the efficiency of list algorithms under the hood. We can have more g=
enericity with zero overhead with a good impementation :p<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&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+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"http://groups.google.com/a/isocpp.org/group/=
std-proposals/">http://groups.google.com/a/isocpp.org/group/std-proposals/<=
/a>.<br />

------=_Part_511_974056567.1443120234112--
------=_Part_510_1044555239.1443120234112--

.

------=_Part_255_994354543.1454682377896
Content-Type: multipart/alternative;
 boundary="----=_Part_256_291129622.1454682377896"

------=_Part_256_291129622.1454682377896
Content-Type: text/plain; charset=UTF-8

Hi everyone, I updated the proposal and hope it can make it into next
mailing and can be discussed during the next meeting, even though I'm a bit
late and don't have anyone to champion the proposal.
Anyway, things changed, and here is how:

   - I added std::inplace_merge to the paper since the iterator category of
   std::stable_sort is linked to that of std::inplace_merge.
   - I wrote the algorithms and timed them, and it's possible to implement
   an efficient n log n std::inplace_merge for forward iterators without
   too much efforts; it took the implementation from Stepanov and McJone's *Elements
   of Programming*.
   - I think I found reasonable complexities we can ask for std::sort,
   std::stable_sort and std::inplace_merge for forward and bidirectional
   iterators.
   - More discussions about things (Parallelism TS, Ranges TS, benefits of
   std::list::sort over generic algorithms).
   - Wording for the three algorithms.

The updated proposal can still be found at the same address:
https://github.com/Morwenn/Sorting-algorithms-proposal/blob/master/sorting-algorithms.pdf

Is anyone willing to present and/or champion the proposal during the next
meeting in Jacksonville at the end of the month, or in Oulu (Finland) later
this if the proposal doesn't make it into the next mailing?

--

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

<div dir=3D"ltr">Hi everyone, I updated the proposal and hope it can make i=
t into next mailing and can be discussed during the next meeting, even thou=
gh I&#39;m a bit late and don&#39;t have anyone to champion the proposal.<b=
r>Anyway, things changed, and here is how:<br><ul><li>I added <span style=
=3D"font-family: courier new,monospace;">std::inplace_merge</span> to the p=
aper since the iterator category of <span style=3D"font-family: courier new=
,monospace;">std::stable_sort</span> is linked to that of <span style=3D"fo=
nt-family: courier new,monospace;">std::inplace_merge</span>.</li><li>I wro=
te the algorithms and timed them, and it&#39;s possible to implement an eff=
icient n log n <span style=3D"font-family: courier new,monospace;">std::inp=
lace_merge</span> for forward iterators without too much efforts; it took t=
he implementation from Stepanov and McJone&#39;s <i>Elements of Programming=
</i>.</li><li>I think I found reasonable complexities we can ask for <span =
style=3D"font-family: courier new,monospace;">std::sort</span>, <span style=
=3D"font-family: courier new,monospace;">std::stable_sort</span> and <span =
style=3D"font-family: courier new,monospace;">std::inplace_merge</span> for=
 forward and bidirectional iterators.</li><li>More discussions about things=
 (Parallelism TS, Ranges TS, benefits of=C2=A0<span style=3D"font-family: c=
ourier new,monospace;"></span><span style=3D"font-family: courier new,monos=
pace;">std::list::sort</span> over generic algorithms).</li><li>Wording for=
 the three algorithms.</li></ul>The updated proposal can still be found at =
the same address: <a href=3D"https://github.com/Morwenn/Sorting-algorithms-=
proposal/blob/master/sorting-algorithms.pdf" target=3D"_blank" rel=3D"nofol=
low">https://github.com/Morwenn/<wbr>Sorting-algorithms-proposal/<wbr>blob/=
master/sorting-<wbr>algorithms.pdf</a><br><br>Is anyone willing to present =
and/or champion the proposal during the next meeting in Jacksonville at the=
 end of the month, or in Oulu (Finland) later this if the proposal doesn&#3=
9;t make it into the next mailing?<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&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+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_256_291129622.1454682377896--
------=_Part_255_994354543.1454682377896--

.