------=_Part_38_1029628361.1551837640650
Content-Type: multipart/alternative;
 boundary="----=_Part_39_1570309013.1551837640650"

------=_Part_39_1570309013.1551837640650
Content-Type: text/plain; charset="UTF-8"

The new std::midpoint function (defined in P0811R2
<http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0811r2.html>)
defines a new function std::midpoint.  It is defined for all integral types
and pointers, but not for other iterator types.  I think it should be
defined for all random-access iterator types.  A major use-case for this
function is in implementing algorithms that have to split a range in two,
such as mergesort or median-of-three partitioning for quicksort.  Also, as
this function is specified now, it is implementation-defined whether it
will work for std::vector<X>::iterators.  If vector's iterators are
specified as pointers it will, and if not it won't.  That can easily change
when switching between compilers, or even between optimization levels of
the same compiler.

Joe Gottman

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org.

------=_Part_39_1570309013.1551837640650
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">The new std::midpoint function (defined in=C2=A0<a href=3D=
"http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0811r2.html">P081=
1R2</a>) defines a new function std::midpoint.=C2=A0 It is defined for all =
integral types and pointers, but not for other iterator types.=C2=A0 I thin=
k it should be defined for all random-access iterator types.=C2=A0 A major =
use-case for this function is in implementing algorithms that have to split=
 a range in two, such as mergesort or median-of-three partitioning for quic=
ksort.=C2=A0 Also, as this function is specified now, it is implementation-=
defined whether it will work for std::vector&lt;X&gt;::iterators.=C2=A0 If =
vector&#39;s iterators are specified as pointers it will, and if not it won=
&#39;t.=C2=A0 That can easily change when switching between compilers, or e=
ven between optimization levels of the same compiler.<div><br></div><div>Jo=
e Gottman</div></div>

<p></p>

-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce=
%40isocpp.org</a>.<br />

------=_Part_39_1570309013.1551837640650--

------=_Part_38_1029628361.1551837640650--

.

--0000000000003243bc058371550a
Content-Type: text/plain; charset="UTF-8"

It sounds useful to extend midpoint() to work on at least random-access
iterators, and possibly all forward iterators. Want to write a paper?

On Tue, Mar 5, 2019 at 6:00 PM <jgottman6@gmail.com> wrote:

> The new std::midpoint function (defined in P0811R2
> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0811r2.html>)
> defines a new function std::midpoint.  It is defined for all integral types
> and pointers, but not for other iterator types.  I think it should be
> defined for all random-access iterator types.  A major use-case for this
> function is in implementing algorithms that have to split a range in two,
> such as mergesort or median-of-three partitioning for quicksort.  Also, as
> this function is specified now, it is implementation-defined whether it
> will work for std::vector<X>::iterators.  If vector's iterators are
> specified as pointers it will, and if not it won't.  That can easily change
> when switching between compilers, or even between optimization levels of
> the same compiler.
>
> Joe Gottman
>
> --
> You received this message because you are subscribed to the Google Groups
> "ISO C++ Standard - Future Proposals" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to std-proposals+unsubscribe@isocpp.org.
> To post to this group, send email to std-proposals@isocpp.org.
> To view this discussion on the web visit
> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org
> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org?utm_medium=email&utm_source=footer>
> .
>

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CANh-dXkmMveUnf-TKH8nXB98OsskW5o1GZFsk%3D%3DZfF6N39ub%2Bw%40mail.gmail.com.

--0000000000003243bc058371550a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">It sounds useful to extend midpoint() to work on at least =
random-access iterators, and possibly all forward iterators. Want to write =
a paper?</div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmai=
l_attr">On Tue, Mar 5, 2019 at 6:00 PM &lt;<a href=3D"mailto:jgottman6@gmai=
l.com">jgottman6@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gma=
il_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,2=
04,204);padding-left:1ex"><div dir=3D"ltr">The new std::midpoint function (=
defined in=C2=A0<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/pape=
rs/2018/p0811r2.html" target=3D"_blank">P0811R2</a>) defines a new function=
 std::midpoint.=C2=A0 It is defined for all integral types and pointers, bu=
t not for other iterator types.=C2=A0 I think it should be defined for all =
random-access iterator types.=C2=A0 A major use-case for this function is i=
n implementing algorithms that have to split a range in two, such as merges=
ort or median-of-three partitioning for quicksort.=C2=A0 Also, as this func=
tion is specified now, it is implementation-defined whether it will work fo=
r std::vector&lt;X&gt;::iterators.=C2=A0 If vector&#39;s iterators are spec=
ified as pointers it will, and if not it won&#39;t.=C2=A0 That can easily c=
hange when switching between compilers, or even between optimization levels=
 of the same compiler.<div><br></div><div>Joe Gottman</div></div>

<p></p>

-- <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" 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>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank">=
https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-=
4467-b775-dee91f8b3bce%40isocpp.org</a>.<br>
</blockquote></div>

<p></p>

-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CANh-dXkmMveUnf-TKH8nXB98OsskW5o1GZFs=
k%3D%3DZfF6N39ub%2Bw%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoote=
r">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CANh-dXkmMv=
eUnf-TKH8nXB98OsskW5o1GZFsk%3D%3DZfF6N39ub%2Bw%40mail.gmail.com</a>.<br />

--0000000000003243bc058371550a--

.

------=_Part_537_2104282936.1551926458513
Content-Type: multipart/alternative;
 boundary="----=_Part_538_1393349891.1551926458514"

------=_Part_538_1393349891.1551926458514
Content-Type: text/plain; charset="UTF-8"

I'm of two minds about extending the midpoint() function to all iterator
types.  It would definitely be useful, but there are a couple of potential
problems.  Currently the midpoint() function is always of constant
complexity; if we extend it to forward iterators it will be O(n) for
forward or bidirectional iterator types. Also, for a pair of pointers  p
and q into the same container,, both midpoint(p, q) and midpoint(q, p) are
currently well-defined.  It is possible to maintain this property if p and
q are random-access iterators into the same container, but not if they are
only bidirectional or forward iterators.

Joe Gottman

On Wednesday, March 6, 2019 at 1:41:10 PM UTC-5, Jeffrey Yasskin wrote:
>
> It sounds useful to extend midpoint() to work on at least random-access
> iterators, and possibly all forward iterators. Want to write a paper?
>
> On Tue, Mar 5, 2019 at 6:00 PM <jgot...@gmail.com <javascript:>> wrote:
>
>> The new std::midpoint function (defined in P0811R2
>> <http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0811r2.html>)
>> defines a new function std::midpoint.  It is defined for all integral types
>> and pointers, but not for other iterator types.  I think it should be
>> defined for all random-access iterator types.  A major use-case for this
>> function is in implementing algorithms that have to split a range in two,
>> such as mergesort or median-of-three partitioning for quicksort.  Also, as
>> this function is specified now, it is implementation-defined whether it
>> will work for std::vector<X>::iterators.  If vector's iterators are
>> specified as pointers it will, and if not it won't.  That can easily change
>> when switching between compilers, or even between optimization levels of
>> the same compiler.
>>
>> Joe Gottman
>>
>> --
>> 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-proposal...@isocpp.org <javascript:>.
>> To post to this group, send email to std-pr...@isocpp.org <javascript:>.
>> To view this discussion on the web visit
>> https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org
>> <https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org?utm_medium=email&utm_source=footer>
>> .
>>
>

--
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/20baa69d-2cff-4a94-9455-8325e9865059%40isocpp.org.

------=_Part_538_1393349891.1551926458514
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I&#39;m of two minds about extending the midpoint() functi=
on to all iterator types.=C2=A0 It would definitely be useful, but there ar=
e a couple of potential problems.=C2=A0 Currently the midpoint() function i=
s always of constant complexity; if we extend it to forward iterators it wi=
ll be O(n) for forward or bidirectional iterator types. Also, for a pair of=
 pointers=C2=A0 p and q into the same container,, both midpoint(p, q) and m=
idpoint(q, p) are currently well-defined.=C2=A0 It is possible to maintain =
this property if p and q are random-access iterators into the same containe=
r, but not if they are only bidirectional or forward iterators.<div><br></d=
iv><div>Joe Gottman<br><br>On Wednesday, March 6, 2019 at 1:41:10 PM UTC-5,=
 Jeffrey Yasskin wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0=
;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div di=
r=3D"ltr">It sounds useful to extend midpoint() to work on at least random-=
access iterators, and possibly all forward iterators. Want to write a paper=
?</div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Tue, Mar 5, 2019 =
at 6:00 PM &lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mai=
lto=3D"dndEgdycAgAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javas=
cript:&#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&#39;;retu=
rn true;">jgot...@gmail.com</a>&gt; wrote:<br></div><blockquote class=3D"gm=
ail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,=
204,204);padding-left:1ex"><div dir=3D"ltr">The new std::midpoint function =
(defined in=C2=A0<a href=3D"http://www.open-std.org/jtc1/sc22/wg21/docs/pap=
ers/2018/p0811r2.html" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"th=
is.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.open-std.org=
%2Fjtc1%2Fsc22%2Fwg21%2Fdocs%2Fpapers%2F2018%2Fp0811r2.html\x26sa\x3dD\x26s=
ntz\x3d1\x26usg\x3dAFQjCNHI_V5QgUs9CQzrIEgsfKFfnf6_hg&#39;;return true;" on=
click=3D"this.href=3D&#39;http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.o=
pen-std.org%2Fjtc1%2Fsc22%2Fwg21%2Fdocs%2Fpapers%2F2018%2Fp0811r2.html\x26s=
a\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHI_V5QgUs9CQzrIEgsfKFfnf6_hg&#39;;retur=
n true;">P0811R2</a>) defines a new function std::midpoint.=C2=A0 It is def=
ined for all integral types and pointers, but not for other iterator types.=
=C2=A0 I think it should be defined for all random-access iterator types.=
=C2=A0 A major use-case for this function is in implementing algorithms tha=
t have to split a range in two, such as mergesort or median-of-three partit=
ioning for quicksort.=C2=A0 Also, as this function is specified now, it is =
implementation-defined whether it will work for std::vector&lt;X&gt;::itera=
tors.=C2=A0 If vector&#39;s iterators are specified as pointers it will, an=
d if not it won&#39;t.=C2=A0 That can easily change when switching between =
compilers, or even between optimization levels of the same compiler.<div><b=
r></div><div>Joe Gottman</div></div>

<p></p>

-- <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"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"=
dndEgdycAgAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:&=
#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&#39;;return true=
;">std-proposal...@<wbr>isocpp.org</a>.<br>
To post to this group, send email to <a href=3D"javascript:" target=3D"_bla=
nk" gdf-obfuscated-mailto=3D"dndEgdycAgAJ" rel=3D"nofollow" onmousedown=3D"=
this.href=3D&#39;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39=
;javascript:&#39;;return true;">std-pr...@isocpp.org</a>.<br>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%=
40isocpp.org?utm_medium=3Demail&amp;utm_source=3Dfooter" target=3D"_blank" =
rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;https://groups.google.com/=
a/isocpp.org/d/msgid/std-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40i=
socpp.org?utm_medium\x3demail\x26utm_source\x3dfooter&#39;;return true;" on=
click=3D"this.href=3D&#39;https://groups.google.com/a/isocpp.org/d/msgid/st=
d-proposals/17327c95-88a5-4467-b775-dee91f8b3bce%40isocpp.org?utm_medium\x3=
demail\x26utm_source\x3dfooter&#39;;return true;">https://groups.google.com=
/a/<wbr>isocpp.org/d/msgid/std-<wbr>proposals/17327c95-88a5-4467-<wbr>b775-=
dee91f8b3bce%40isocpp.org</a><wbr>.<br>
</blockquote></div>
</blockquote></div></div>

<p></p>

-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/20baa69d-2cff-4a94-9455-8325e9865059%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/20baa69d-2cff-4a94-9455-8325e9865059=
%40isocpp.org</a>.<br />

------=_Part_538_1393349891.1551926458514--

------=_Part_537_2104282936.1551926458513--

.

Am Do., 7. M=C3=A4rz 2019 um 03:41 Uhr schrieb <jgottman6@gmail.com>:
>
> I'm of two minds about extending the midpoint() function to all iterator =
types.  It would definitely be useful, but there are a couple of potential =
problems.  Currently the midpoint() function is always of constant complexi=
ty; if we extend it to forward iterators it will be O(n) for forward or bid=
irectional iterator types. Also, for a pair of pointers  p and q into the s=
ame container,, both midpoint(p, q) and midpoint(q, p) are currently well-d=
efined.  It is possible to maintain this property if p and q are random-acc=
ess iterators into the same container, but not if they are only bidirection=
al or forward iterators.
>
> Joe Gottman

I don't consider this as an argument, *not* to provide this
functionality. We have a long-established practice of functions in the
standard library (especially in [algorithms]) that specify complexity
limits depending on iterator categories, e.g. for is_permutation:

Complexity: No applications of the corresponding predicate if
ForwardIterator1 and ForwardIterator2
meet the requirements of random access iterators and last1 - first1 !=3D
last2 - first2.
Otherwise, exactly last1 - first1 applications of the corresponding
predicate if equal(first1,
last1, first2, last2) would return true if pred was not given in the
argument list or equal(first1,
last1, first2, last2, pred) would return true if pred was given in the
argument list; otherwise,
at worst O(N2), where N has the value last1 - first1.

Several other examples exist.

- Daniel

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAGNvRgCGf7nq4bJiZxyG41b_Gcyy86oQDL1mrj%2BvbNJx0=
onLkQ%40mail.gmail.com.

.

------=_Part_851_1366663645.1551976186729
Content-Type: multipart/alternative;
 boundary="----=_Part_852_1959429044.1551976186729"

------=_Part_852_1959429044.1551976186729
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable



On Thursday, March 7, 2019 at 2:03:32 AM UTC-5, Daniel Kr=C3=BCgler wrote:
>
> Am Do., 7. M=C3=A4rz 2019 um 03:41 Uhr schrieb <jgot...@gmail.com <javasc=
ript:>>:=20
>
> >=20
> > I'm of two minds about extending the midpoint() function to all iterato=
r=20
> types.  It would definitely be useful, but there are a couple of potentia=
l=20
> problems.  Currently the midpoint() function is always of constant=20
> complexity; if we extend it to forward iterators it will be O(n) for=20
> forward or bidirectional iterator types. Also, for a pair of pointers  p=
=20
> and q into the same container,, both midpoint(p, q) and midpoint(q, p) ar=
e=20
> currently well-defined.  It is possible to maintain this property if p an=
d=20
> q are random-access iterators into the same container, but not if they ar=
e=20
> only bidirectional or forward iterators.=20
> >=20
> > Joe Gottman=20
>
> I don't consider this as an argument, *not* to provide this=20
> functionality.


And yet, we do this all the time. `std::sort`, `std::lower_bound`, and such=
=20
all require RandomAccessRanges. They don't need that requirement; you can=
=20
do sorting and binary searches on any ForwardRange. But that's not=20
something anyone actually *wants* to do; it's excruciatingly slow.

Furthermore, let's say that I have a `std::forward_list`. This is a=20
ForwardRange, but it is also a SizedRange. If I want to do some=20
`midpoint`-based algorithm, the most efficient way to do this is *not* by=
=20
iterators, but by *indices.* That is, you start with an index range of [0,=
=20
size), and you `midpoint` that to get your middle index. You then use=20
`range::advance` to increment the begin iterator to the midpoint. And then=
=20
you decide which side you're interested in.

But you keep the index around to do you next `midpoint` call. This minimize=
=20
the number of increments to iterators: you will only ever perform n=20
increments at the most.

If we let people use `midpoint` directly on ForwardRanges, you're=20
performing lots more iterator increments. Each part of a binary search=20
increments the iterator N times, followed by N/2 to get the midpoint. Even=
=20
if we restrict it to a SizedRange, that still doesn't work, because we only=
=20
know the size of a `std::forward_list`, not the size of an iterator pair=20
from a `forward_list`.

This is precisely why we *don't* require `sort` and `lower_bound` to work=
=20
on non-RandomAccessRanges: to prevent people from writing bad, inefficient=
=20
algorithms. I submit that `midpoint` is just a part of `lower_bound`, so it=
=20
should have a similar restriction.

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/012a18b0-3ca0-49f2-bd1f-304c148fdb67%40isocpp.or=
g.

------=_Part_852_1959429044.1551976186729
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><br><br>On Thursday, March 7, 2019 at 2:03:32 AM UTC-5, Da=
niel Kr=C3=BCgler wrote:<blockquote class=3D"gmail_quote" style=3D"margin: =
0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">Am Do.=
, 7. M=C3=A4rz 2019 um 03:41 Uhr schrieb &lt;<a href=3D"javascript:" target=
=3D"_blank" gdf-obfuscated-mailto=3D"qvSzRl_FAgAJ" rel=3D"nofollow" onmouse=
down=3D"this.href=3D&#39;javascript:&#39;;return true;" onclick=3D"this.hre=
f=3D&#39;javascript:&#39;;return true;">jgot...@gmail.com</a>&gt;:
<br>&gt;
<br>&gt; I&#39;m of two minds about extending the midpoint() function to al=
l iterator types. =C2=A0It would definitely be useful, but there are a coup=
le of potential problems. =C2=A0Currently the midpoint() function is always=
 of constant complexity; if we extend it to forward iterators it will be O(=
n) for forward or bidirectional iterator types. Also, for a pair of pointer=
s =C2=A0p and q into the same container,, both midpoint(p, q) and midpoint(=
q, p) are currently well-defined. =C2=A0It is possible to maintain this pro=
perty if p and q are random-access iterators into the same container, but n=
ot if they are only bidirectional or forward iterators.
<br>&gt;
<br>&gt; Joe Gottman
<br>
<br>I don&#39;t consider this as an argument, *not* to provide this
<br>functionality.</blockquote><div><br></div><div>And yet, we do this all =
the time. `std::sort`, `std::lower_bound`, and such all require RandomAcces=
sRanges. They don&#39;t need that requirement; you can do sorting and binar=
y searches on any ForwardRange. But that&#39;s not something anyone actuall=
y <i>wants</i> to do; it&#39;s excruciatingly slow.</div><div><br></div><di=
v>Furthermore, let&#39;s say that I have a `std::forward_list`. This is a F=
orwardRange, but it is also a SizedRange. If I want to do some `midpoint`-b=
ased algorithm, the most efficient way to do this is <i>not</i> by iterator=
s, but by <i>indices.</i> That is, you start with an index range of [0, siz=
e), and you `midpoint` that to get your middle index. You then use `range::=
advance` to increment the begin iterator to the midpoint. And then you deci=
de which side you&#39;re interested in.</div><div><br></div><div>But you ke=
ep the index around to do you next `midpoint` call. This minimize the numbe=
r of increments to iterators: you will only ever perform n increments at th=
e most.<br></div><div><br></div><div>If we let people use `midpoint` direct=
ly on ForwardRanges, you&#39;re performing lots more iterator increments. E=
ach part of a binary search increments the iterator N times, followed by N/=
2 to get the midpoint. Even if we restrict it to a SizedRange, that still d=
oesn&#39;t work, because we only know the size of a `std::forward_list`, no=
t the size of an iterator pair from a `forward_list`.<br></div><div><br></d=
iv><div>This is precisely why we <i>don&#39;t</i> require `sort` and `lower=
_bound` to work on non-RandomAccessRanges: to prevent people from writing b=
ad, inefficient algorithms. I submit that `midpoint` is just a part of `low=
er_bound`, so it should have a similar restriction.<br></div></div>

<p></p>

-- <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 />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/012a18b0-3ca0-49f2-bd1f-304c148fdb67%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/012a18b0-3ca0-49f2-bd1f-304c148fdb67=
%40isocpp.org</a>.<br />

------=_Part_852_1959429044.1551976186729--

------=_Part_851_1366663645.1551976186729--

.

Am Do., 7. M=C3=A4rz 2019 um 17:29 Uhr schrieb Nicol Bolas <jmckesson@gmail=
..com>:
>
>
>
> On Thursday, March 7, 2019 at 2:03:32 AM UTC-5, Daniel Kr=C3=BCgler wrote=
:
>>
>> Am Do., 7. M=C3=A4rz 2019 um 03:41 Uhr schrieb <jgot...@gmail.com>:
>> >
>> > I'm of two minds about extending the midpoint() function to all iterat=
or types.  It would definitely be useful, but there are a couple of potenti=
al problems.  Currently the midpoint() function is always of constant compl=
exity; if we extend it to forward iterators it will be O(n) for forward or =
bidirectional iterator types. Also, for a pair of pointers  p and q into th=
e same container,, both midpoint(p, q) and midpoint(q, p) are currently wel=
l-defined.  It is possible to maintain this property if p and q are random-=
access iterators into the same container, but not if they are only bidirect=
ional or forward iterators.
>> >
>> > Joe Gottman
>>
>> I don't consider this as an argument, *not* to provide this
>> functionality.
>> And yet, we do this all the time.

In my original reply I was giving an argument, *why* we could add this
functionality. It was not an argument that was intended to suggest
that it needs to be added.

> `std::sort`, `std::lower_bound`, and such all require RandomAccessRanges.=
 They don't need that requirement; you can do sorting and binary searches o=
n any ForwardRange. But that's not something anyone actually wants to do; i=
t's excruciatingly slow.

This alone is not a reason to not provide such a functionality. For
example, std::distance is "slow" for forward iterators, but it is
still a useful functionality.

> Furthermore, let's say that I have a `std::forward_list`. This is a Forwa=
rdRange, but it is also a SizedRange.

I cannot find evidence that supports your claim: According to [range.sized]=
 p2

"[..] T models SizedRange only if ranges::size(t) is O(1) [..]

std::forward_list does not provide a size() member function, because
that would conflict with the design targets of that specific
container. In addition, the requirements imposed by [range.prim.size]
seem to conflict with ranges::size() being well-formed for
std::forward_list. There does not even exist support for a std::size
range access for std::forward_list.

> If I want to do some `midpoint`-based algorithm, the most efficient way t=
o do this is not by iterators, but by indices. That is, you start with an i=
ndex range of [0, size), and you `midpoint` that to get your middle index. =
You then use `range::advance` to increment the begin iterator to the midpoi=
nt. And then you decide which side you're interested in.
>

Our original point of discussion was an algorithm, now you are
switching to container functionality. Our (unwritten) guidelines have
the effect that we have a much more conservative view when deciding to
provide functionality for containers (such as for forward_list for
example), but we have no such strict guidelines for algorithms.

> But you keep the index around to do you next `midpoint` call. This minimi=
ze the number of increments to iterators: you will only ever perform n incr=
ements at the most.
>
> If we let people use `midpoint` directly on ForwardRanges, you're perform=
ing lots more iterator increments. Each part of a binary search increments =
the iterator N times, followed by N/2 to get the midpoint. Even if we restr=
ict it to a SizedRange, that still doesn't work, because we only know the s=
ize of a `std::forward_list`, not the size of an iterator pair from a `forw=
ard_list`.
>

I was not suggesting to provide container support for midpoint. This
would be inappropriate for the reasons that you and me have provided.

> This is precisely why we don't require `sort` and `lower_bound` to work o=
n non-RandomAccessRanges: to prevent people from writing bad, inefficient a=
lgorithms. I submit that `midpoint` is just a part of `lower_bound`, so it =
should have a similar restriction.

I disagree that this is *precisely* the reason why we don't have
standarized std::sort and std::lower_bound to work for non-random
access ranges. We do provide support for the algorithm partition_point
even for forward iterators for example, even though the algorithm
needs to call the equivalent of std::distance which has linear
complexity for non-random access iterators. Stepanov and McJones
provide in Elements of Programming

We need to decide whether we want an middle_point algorithm for
forward iterators. There may be some reasons not to provide it, but
the question is whether they are sufficient. On the other hand we can
always start with stricter requirements and can relax those
requirements in the future if there is evidence that there are
sufficient motivating reasons. So unless someone brings forward some
usecases for plain forward iterator support for middle_point I'm happy
to standardize only a random access iterator based version of
middle_point. However, such a reduced provision does not naturally
fall out of the existing Standard Library contents, it requires an
individual decision.

- Daniel

--=20
You received this message because you are subscribed to the Google Groups "=
ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
To view this discussion on the web visit https://groups.google.com/a/isocpp=
..org/d/msgid/std-proposals/CAGNvRgDFy%3DeXXa1ii9y_WF04SAsvC7JAX6pbAWTO3c9Wi=
kVWoQ%40mail.gmail.com.

.