------=_Part_2778_1305444123.1496071682859
Content-Type: multipart/alternative;
 boundary="----=_Part_2779_795014001.1496071682859"

------=_Part_2779_795014001.1496071682859
Content-Type: text/plain; charset="UTF-8"

Hey,
         The present implementations of the std::binary_search has
arbitrary forward iterators as arguments. But it has been found that when
the underlying data structure is a list, linear search beats binary search.
( Find the link of the paper attached )

The difference in performance of binary search and linear search in the
case of lists is huge ,hence , it is necessary to make changes.

I therefore, propose to make std::binary_search incompatible with lists.

To make this change , we need to make std::lower_bound incompatible with
lists, which is justified due to performance issues.

Paper <http://umich.edu/~eecs381/handouts/binary_search_std_list.pdf>

Regards,
Jay Pokarna


--
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/fe9d756b-7d1e-4be6-9a04-9f4e19774a13%40isocpp.org.

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

<div dir=3D"ltr">Hey,<div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0The present imp=
lementations of the std::binary_search has arbitrary forward iterators as a=
rguments. But it has been found that when the underlying data structure is =
a list, linear search beats binary search. ( Find the link of the paper att=
ached )=C2=A0</div><div><br></div><div>The difference in performance of bin=
ary search and linear search in the case of lists is huge ,hence , it is ne=
cessary to make changes.</div><div>=C2=A0</div><div>I therefore, propose to=
 make std::binary_search incompatible with lists.=C2=A0</div><div><br></div=
><div>To make this change , we need to make std::lower_bound incompatible w=
ith lists, which is justified due to performance issues.</div><div><br></di=
v><div><a href=3D"http://umich.edu/~eecs381/handouts/binary_search_std_list=
..pdf">Paper</a><br></div><div><br></div><div>Regards,</div><div>Jay Pokarna=
</div><div><br></div><div><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/fe9d756b-7d1e-4be6-9a04-9f4e19774a13%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/fe9d756b-7d1e-4be6-9a04-9f4e19774a13=
%40isocpp.org</a>.<br />

------=_Part_2779_795014001.1496071682859--

------=_Part_2778_1305444123.1496071682859--

.

------=_Part_2858_261879607.1496074561076
Content-Type: multipart/alternative;
 boundary="----=_Part_2859_1982696208.1496074561076"

------=_Part_2859_1982696208.1496074561076
Content-Type: text/plain; charset="UTF-8"



On Monday, May 29, 2017 at 11:28:03 AM UTC-4, jay pokarna wrote:
>
> Hey,
>          The present implementations of the std::binary_search has
> arbitrary forward iterators as arguments. But it has been found that when
> the underlying data structure is a list, linear search beats binary search.
> ( Find the link of the paper attached )
>
> The difference in performance of binary search and linear search in the
> case of lists is huge ,hence , it is necessary to make changes.
>
> I therefore, propose to make std::binary_search incompatible with lists.
>
> To make this change , we need to make std::lower_bound incompatible with
> lists, which is justified due to performance issues.
>
> Paper <http://umich.edu/~eecs381/handouts/binary_search_std_list.pdf>
>
>
This would be a backwards-incompatible change. So some investigation would
need to be done on the impact of such a change.

A better thing to do would be to prevent the Range TS's version of these
functions from working on non-random access ranges/iterators. At least then
we could prevent people from doing this going forward.

--
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/19ae6944-c260-43af-af17-e43db2939bca%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Monday, May 29, 2017 at 11:28:03 AM UTC-4, jay =
pokarna wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
>Hey,<div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0The present implementations of =
the std::binary_search has arbitrary forward iterators as arguments. But it=
 has been found that when the underlying data structure is a list, linear s=
earch beats binary search. ( Find the link of the paper attached )=C2=A0</d=
iv><div><br></div><div>The difference in performance of binary search and l=
inear search in the case of lists is huge ,hence , it is necessary to make =
changes.</div><div>=C2=A0</div><div>I therefore, propose to make std::binar=
y_search incompatible with lists.=C2=A0</div><div><br></div><div>To make th=
is change , we need to make std::lower_bound incompatible with lists, which=
 is justified due to performance issues.</div><div><br></div><div><a href=
=3D"http://umich.edu/~eecs381/handouts/binary_search_std_list.pdf" target=
=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;http://www.goo=
gle.com/url?q\x3dhttp%3A%2F%2Fumich.edu%2F~eecs381%2Fhandouts%2Fbinary_sear=
ch_std_list.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEY_DOT9ZiYW29d35YTG=
NwLA_pLhA&#39;;return true;" onclick=3D"this.href=3D&#39;http://www.google.=
com/url?q\x3dhttp%3A%2F%2Fumich.edu%2F~eecs381%2Fhandouts%2Fbinary_search_s=
td_list.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEY_DOT9ZiYW29d35YTGNwLA=
_pLhA&#39;;return true;">Paper</a></div><br></div></blockquote><div><br>Thi=
s would be a backwards-incompatible change. So some investigation would nee=
d to be done on the impact of such a change.<br><br>A better thing to do wo=
uld be to prevent the Range TS&#39;s version of these functions from workin=
g on non-random access ranges/iterators. At least then we could prevent peo=
ple from doing this going forward.<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/19ae6944-c260-43af-af17-e43db2939bca%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/19ae6944-c260-43af-af17-e43db2939bca=
%40isocpp.org</a>.<br />

------=_Part_2859_1982696208.1496074561076--

------=_Part_2858_261879607.1496074561076--

.

--94eb2c06cde8c31dcd0550ac9e59
Content-Type: text/plain; charset="UTF-8"

On Mon, May 29, 2017 at 10:28 AM, jay pokarna <jay.pokarna10@gmail.com>
wrote:

> Hey,
>          The present implementations of the std::binary_search has
> arbitrary forward iterators as arguments. But it has been found that when
> the underlying data structure is a list, linear search beats binary search.
> ( Find the link of the paper attached )
>
> The difference in performance of binary search and linear search in the
> case of lists is huge ,hence , it is necessary to make changes.
>
> I therefore, propose to make std::binary_search incompatible with lists.
>
> To make this change , we need to make std::lower_bound incompatible with
> lists, which is justified due to performance issues.
>
Paper <http://umich.edu/~eecs381/handouts/binary_search_std_list.pdf>
>
> Regards,
> Jay Pokarna
>
>
The given paper provides a lot of interesting data but I see some flaws:
1) It fails to consider the impact of custom allocators which could
dramatically reduce the cost of iteration
2) Its consideration of comparison costs is overly simplistic. If my
comparison operator internally requires dereferencing many pointers then
the cost of iteration could still be less than cost of comparison. Building
linked lists of objects with complex comparison operators would in fact be
a very reasonable use case, as linked lists are often best suited for use
with large and complex objects that can afford to be individually heap
allocated. A lower_bound on a list<int> certainly seems preposterous, but a
lower_bound on a list<list<int>> could be very reasonable.
3) The paper does not appear to make any case for why the feature is
incorrect and should be removed. It only suggests, from an engineering
perspective, that the author did not find a use case for lower_bound on a
list. No argument is made for why there could *never* be a valid use. "It's
slower in my one use case on my particular hardware" is not an argument for
taking it away from everyone else.
4) We also know that std::list itself is in almost all cases slower than
std::vector. So if "it's almost always slower" is an argument for removing
something, then it seems like std::list is the problem -- not lower_bound.
If efficiency is our measuring stick for keeping or removing something, why
shouldn't we just remove std::list?
5) The efficiency of an operation is not always the only or the most
important engineering trade-off. Some use-cases may be slower when using
lower_bound but also have made that choice intelligently as a broader
engineering decision.

--
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/CADbh%2BeS8fX1DjoemGgbhJ_L7J%2BoVjDck5S7myYfEyujSK9j9vg%40mail.gmail.com.

--94eb2c06cde8c31dcd0550ac9e59
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 M=
on, May 29, 2017 at 10:28 AM, jay pokarna <span dir=3D"ltr">&lt;<a href=3D"=
mailto:jay.pokarna10@gmail.com" target=3D"_blank">jay.pokarna10@gmail.com</=
a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><=
div dir=3D"ltr">Hey,<div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0The present impl=
ementations of the std::binary_search has arbitrary forward iterators as ar=
guments. But it has been found that when the underlying data structure is a=
 list, linear search beats binary search. ( Find the link of the paper atta=
ched )=C2=A0</div><div><br></div><div>The difference in performance of bina=
ry search and linear search in the case of lists is huge ,hence , it is nec=
essary to make changes.</div><div>=C2=A0</div><div>I therefore, propose to =
make std::binary_search incompatible with lists.=C2=A0</div><div><br></div>=
<div>To make this change , we need to make std::lower_bound incompatible wi=
th lists, which is justified due to performance issues. =C2=A0</div></div><=
/blockquote><div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr"><div><a href=3D"http://umich.edu/~eecs381/handouts/binary_search_s=
td_list.pdf" target=3D"_blank">Paper</a><br></div><div><br></div><div>Regar=
ds,</div><div>Jay Pokarna</div><div><br></div><span class=3D"gmail-HOEnZb">=
<font color=3D"#888888"></font></span></div></blockquote></div><div><br></d=
iv><div>The given paper provides a lot of interesting data but I see some f=
laws:</div><div>1) It fails to consider the impact of custom allocators whi=
ch could dramatically reduce the cost of iteration</div><div>2) Its conside=
ration of comparison costs is overly simplistic. If my comparison operator =
internally requires dereferencing many pointers then the cost of iteration =
could still be less than cost of comparison. Building linked lists of objec=
ts with complex comparison operators would in fact be a very reasonable use=
 case, as linked lists are often best suited for use with large and complex=
 objects that can afford to be individually heap allocated. A lower_bound o=
n a list&lt;int&gt; certainly seems preposterous, but a lower_bound on a li=
st&lt;list&lt;int&gt;&gt; could be very reasonable.</div><div>3) The paper =
does not appear to make any case for why the feature is incorrect and shoul=
d be removed. It only suggests, from an engineering perspective, that the a=
uthor did not find a use case for lower_bound on a list. No argument is mad=
e for why there could *never* be a valid use. &quot;It&#39;s slower in my o=
ne use case on my particular hardware&quot; is not an argument for taking i=
t away from everyone else.</div><div>4) We also know that std::list itself =
is in almost all cases slower than std::vector. So if &quot;it&#39;s almost=
 always slower&quot; is an argument for removing something, then it seems l=
ike std::list is the problem -- not lower_bound. If efficiency is our measu=
ring stick for keeping or removing something, why shouldn&#39;t we just rem=
ove std::list?</div><div>5) The efficiency of an operation is not always th=
e only or the most important engineering trade-off. Some use-cases may be s=
lower when using lower_bound but also have made that choice intelligently a=
s a broader engineering decision.</div><div>=C2=A0</div></div></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/CADbh%2BeS8fX1DjoemGgbhJ_L7J%2BoVjDck=
5S7myYfEyujSK9j9vg%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter"=
>https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CADbh%2BeS8fX=
1DjoemGgbhJ_L7J%2BoVjDck5S7myYfEyujSK9j9vg%40mail.gmail.com</a>.<br />

--94eb2c06cde8c31dcd0550ac9e59--

.

On segunda-feira, 29 de maio de 2017 08:28:02 PDT jay pokarna wrote:
> To make this change , we need to make std::lower_bound incompatible with
> lists, which is justified due to performance issues.

How do you propose that be done, concretely? Please include QLinkedList in
your answer.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel Open Source Technology Center

--
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/7254988.VdTJMTucRh%40tjmaciei-mobl1.

.

------=_Part_2955_920079973.1496080950287
Content-Type: multipart/alternative;
 boundary="----=_Part_2956_1646208519.1496080950287"

------=_Part_2956_1646208519.1496080950287
Content-Type: text/plain; charset="UTF-8"

>3) The paper does not appear to make any case for why the feature is
incorrect and should be removed. It only suggests, from an engineering
perspective, that the author did not >find a use case for lower_bound on a
list. No argument is made for why there could *never* be a valid use.

I never said that I want to rule out the algorithm because it was giving
wrong answers. It's answers are always correct, but we need to take into
consideration time required to do the process.

>"It's slower in my one use case on my particular hardware" is not an
>argument for taking it away from everyone else.
The way the author has chosen the test cases , show us that he has
considered a variety of test cases.

>4) We also know that std::list itself is in almost all cases slower than
std::vector. So if "it's almost always slower" is an argument for removing
something, then it seems like std::list is >the problem -- not lower_bound.
If efficiency is our measuring stick for keeping or removing something, why
shouldn't we just remove std::list?

LinkedLists have their own use. When you cannot allocate contiguous memory
locations , due to issues like memory to be allocated , or size of memory,
then we don't have any other option than to use a list. Hence, it cannot be
ruled out. Moreover , the problem is not std::list or std::binary_search.
The problem is using binary search to search a list.

>5) The efficiency of an operation is not always the only or the most
important engineering trade-off. Some use-cases may be slower when using
lower_bound but also have made >that choice intelligently as a broader
engineering decision.

Users of the standard Template Library blindly use the algorithm for
searching on any data structure. The point is that if a naive approach
works better than the algorithm , then there is no point of implementing it
on lists.

>1) It fails to consider the impact of custom allocators which could
dramatically reduce the cost of iteration

I don't understand how the use of custom allocators will reduce the cost of
iteration

--
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/96d775f1-0b99-41e2-9130-2ff2e94b89bc%40isocpp.org.

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

<div dir=3D"ltr"><font color=3D"#999999">&gt;3) The paper does not appear t=
o make any case for why the feature is incorrect and should be removed. It =
only suggests, from an engineering perspective, that the author did not &gt=
;find a use case for lower_bound on a list. No argument is made for why the=
re could *never* be a valid use.=C2=A0</font><div><font color=3D"#999999"><=
br></font></div><div><div>I never said that I want to rule out the algorith=
m because it was giving wrong answers. It&#39;s answers are always correct,=
 but we need to take into consideration time required to do the process.=C2=
=A0</div></div><div><br></div><div><font color=3D"#999999">&gt;&quot;It&#39=
;s slower in my one use case on my particular hardware&quot; is not an &gt;=
argument for taking it away from everyone else.</font><div>The way the auth=
or has chosen the test cases , show us that he has considered a variety of =
test cases.</div><div><br></div><div><font color=3D"#999999">&gt;4) We also=
 know that std::list itself is in almost all cases slower than std::vector.=
 So if &quot;it&#39;s almost always slower&quot; is an argument for removin=
g something, then it seems like std::list is &gt;the problem -- not lower_b=
ound. If efficiency is our measuring stick for keeping or removing somethin=
g, why shouldn&#39;t we just remove std::list?</font><br></div><div><br></d=
iv><div><font color=3D"#000000">LinkedLists have their own use. When you ca=
nnot allocate contiguous memory locations , due to issues like memory to be=
 allocated , or size of memory, then we don&#39;t have any other option tha=
n to use a list. Hence, it cannot be ruled out. Moreover , the problem is n=
ot std::list or std::binary_search. The problem is using binary search to s=
earch a list.</font></div><div><font color=3D"#999999"><br></font></div><di=
v><font color=3D"#999999">&gt;5) The efficiency of an operation is not alwa=
ys the only or the most important engineering trade-off. Some use-cases may=
 be slower when using lower_bound but also have made &gt;that choice intell=
igently as a broader engineering decision.</font><font color=3D"#000000"><b=
r></font></div><div><font color=3D"#999999"><br></font></div><div><div>User=
s of the standard Template Library blindly use the algorithm for searching =
on any data structure. The point is that if a naive approach works better t=
han the algorithm , then there is no point of implementing it on lists.<br>=
</div></div><div><br></div><div><span style=3D"background-color: rgb(255, 2=
55, 255);"><font color=3D"#999999">&gt;1) It fails to consider the impact o=
f custom allocators which could dramatically reduce the cost of iteration</=
font></span><br></div><div><span style=3D"background-color: rgb(255, 255, 2=
55);"><font color=3D"#999999"><br></font></span></div><div><span style=3D"b=
ackground-color: rgb(255, 255, 255);"><font color=3D"#000000">I don&#39;t u=
nderstand how the use of custom allocators will reduce the cost of iteratio=
n</font></span></div><div><br></div></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/96d775f1-0b99-41e2-9130-2ff2e94b89bc%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/96d775f1-0b99-41e2-9130-2ff2e94b89bc=
%40isocpp.org</a>.<br />

------=_Part_2956_1646208519.1496080950287--

------=_Part_2955_920079973.1496080950287--

.

--94eb2c190326e4600b0550ae6345
Content-Type: text/plain; charset="UTF-8"

On Mon, May 29, 2017 at 1:02 PM, jay pokarna <jay.pokarna10@gmail.com>
wrote:

> >3) The paper does not appear to make any case for why the feature is
> incorrect and should be removed. It only suggests, from an engineering
> perspective, that the author did not >find a use case for lower_bound on a
> list. No argument is made for why there could *never* be a valid use.
>
> I never said that I want to rule out the algorithm because it was giving
> wrong answers. It's answers are always correct, but we need to take into
> consideration time required to do the process.
>

When you claim that a feature should never be used, then you are claiming
that using the feature is incorrect. It is in that sense of the term that I
use incorrect. I'm not putting words in your mouth here. You are saying
that, when a user chooses to use binary search on a list, that decision is
never correct (proper, good, intelligent, wise).
The author of the paper does not claim that binary searching a list is
never useful. The author only claims that all of his test cases on the
hardware that he selected were slower with binary search.
*You* are the one claiming that the feature must be removed, but you have
not shown that there is *never* *ever* a valid use case. Nor have you shown
that linear search is *always* faster on *every* hardware platform.


>
> >"It's slower in my one use case on my particular hardware" is not an
> >argument for taking it away from everyone else.
> The way the author has chosen the test cases , show us that he has
> considered a variety of test cases.
>

A variety of test cases is not all possible test cases. The author did not
test every possible data structure or every supported hardware platform.
Nor does the author claim to. If you want to remove the functionality, and
your argument for removing the functionality is "binary search is always
slower", then you need to prove it.
Are you going to ignore my point that binary search over a list<list<x>>
could be faster than linear search?


>
> >4) We also know that std::list itself is in almost all cases slower than
> std::vector. So if "it's almost always slower" is an argument for removing
> something, then it seems like std::list is >the problem -- not lower_bound.
> If efficiency is our measuring stick for keeping or removing something, why
> shouldn't we just remove std::list?
>
> LinkedLists have their own use. When you cannot allocate contiguous memory
> locations , due to issues like memory to be allocated , or size of memory,
> then we don't have any other option than to use a list. Hence, it cannot be
> ruled out. Moreover , the problem is not std::list or std::binary_search.
> The problem is using binary search to search a list.
>

I agree that list has a different use case than vector. List can do some
things that vector cannot do. My point is that binary searches *also* have
a different use case from linear searches. Binary search can do things that
linear search cannot do (minimize the number of comparisons). You can't
just blindly replace binary search on a list with forward search on a list
and guarantee it will always be "better". A paper with 5 or  6 tests on one
type of hardware is not rigorous evidence.


>
> >5) The efficiency of an operation is not always the only or the most
> important engineering trade-off. Some use-cases may be slower when using
> lower_bound but also have made >that choice intelligently as a broader
> engineering decision.
>
> Users of the standard Template Library blindly use the algorithm for
> searching on any data structure. The point is that if a naive approach
> works better than the algorithm , then there is no point of implementing it
> on lists.
>

I repeat: The efficiency of an operation is not always the only or the most
important engineering trade-off. I do not accept the premise that faster is
always better, nor do I accept the premise that linear search is always
faster than binary search on a list.


>
> >1) It fails to consider the impact of custom allocators which could
> dramatically reduce the cost of iteration
>
> I don't understand how the use of custom allocators will reduce the cost
> of iteration
>
>
Iterating a list is slow on many modern CPUs primarily due to memory access
patterns. Allocators can dramatically improve memory access patterns.

If I have a list that is fast to iterate because I've improved the memory
access patterns (for example, a pool allocator), then changing my binary
search to a linear search could worsen performance.

--
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/CADbh%2BeQgxVq5OL9NuUM29y-9%2Bb%2BO%3DC9qk_dCBoPtNxKH-BARFg%40mail.gmail.com.

--94eb2c190326e4600b0550ae6345
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 Mon, May 29, 2017 at 1:02 PM, jay pokarna <span dir=3D"ltr">&lt;<a h=
ref=3D"mailto:jay.pokarna10@gmail.com" target=3D"_blank">jay.pokarna10@gmai=
l.com</a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left=
:1ex"><div dir=3D"ltr"><span class=3D"gmail-"><font color=3D"#999999">&gt;3=
) The paper does not appear to make any case for why the feature is incorre=
ct and should be removed. It only suggests, from an engineering perspective=
, that the author did not &gt;find a use case for lower_bound on a list. No=
 argument is made for why there could *never* be a valid use.=C2=A0</font><=
div><font color=3D"#999999"><br></font></div></span><div><div>I never said =
that I want to rule out the algorithm because it was giving wrong answers. =
It&#39;s answers are always correct, but we need to take into consideration=
 time required to do the process.=C2=A0</div></div></div></blockquote><div>=
<br></div><div>When you claim that a feature should never be used, then you=
 are claiming that using the feature is incorrect. It is in that sense of t=
he term that I use incorrect. I&#39;m not putting words in your mouth here.=
 You are saying that, when a user chooses to use binary search on a list, t=
hat decision is never correct (proper, good, intelligent, wise).</div><div>=
The author of the paper does not claim that binary searching a list is neve=
r useful. The author only claims that all of his test cases on the hardware=
 that he selected were slower with binary search.</div><div>*You* are the o=
ne claiming that the feature must be removed, but you have not shown that t=
here is *never* *ever* a valid use case. Nor have you shown that linear sea=
rch is *always* faster on *every* hardware platform.</div><div>=C2=A0</div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div><br=
></div><div><span class=3D"gmail-"><font color=3D"#999999">&gt;&quot;It&#39=
;s slower in my one use case on my particular hardware&quot; is not an &gt;=
argument for taking it away from everyone else.</font></span><div>The way t=
he author has chosen the test cases , show us that he has considered a vari=
ety of test cases.</div></div></div></blockquote><div><br></div><div>A vari=
ety of test cases is not all possible test cases. The author did not test e=
very possible data structure or every supported hardware platform. Nor does=
 the author claim to. If you want to remove the functionality, and your arg=
ument for removing the functionality is &quot;binary search is always slowe=
r&quot;, then you need to prove it.</div><div>Are you going to ignore my po=
int that binary search over a list&lt;list&lt;x&gt;&gt; could be faster tha=
n linear search?</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" st=
yle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padd=
ing-left:1ex"><div dir=3D"ltr"><div><span class=3D"gmail-"><div><br></div><=
div><font color=3D"#999999">&gt;4) We also know that std::list itself is in=
 almost all cases slower than std::vector. So if &quot;it&#39;s almost alwa=
ys slower&quot; is an argument for removing something, then it seems like s=
td::list is &gt;the problem -- not lower_bound. If efficiency is our measur=
ing stick for keeping or removing something, why shouldn&#39;t we just remo=
ve std::list?</font><br></div><div><br></div></span><div><font color=3D"#00=
0000">LinkedLists have their own use. When you cannot allocate contiguous m=
emory locations , due to issues like memory to be allocated , or size of me=
mory, then we don&#39;t have any other option than to use a list. Hence, it=
 cannot be ruled out. Moreover , the problem is not std::list or std::binar=
y_search. The problem is using binary search to search a list.</font></div>=
</div></div></blockquote><div><br></div><div>I agree that list has a differ=
ent use case than vector. List can do some things that vector cannot do. My=
 point is that binary searches *also* have a different use case from linear=
 searches. Binary search can do things that linear search cannot do (minimi=
ze the number of comparisons). You can&#39;t just blindly replace binary se=
arch on a list with forward search on a list and guarantee it will always b=
e &quot;better&quot;. A paper with 5 or =C2=A06 tests on one type of hardwa=
re is not rigorous evidence.</div><div>=C2=A0</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"><div><span class=3D"gmail-"><div=
><font color=3D"#999999"><br></font></div><div><font color=3D"#999999">&gt;=
5) The efficiency of an operation is not always the only or the most import=
ant engineering trade-off. Some use-cases may be slower when using lower_bo=
und but also have made &gt;that choice intelligently as a broader engineeri=
ng decision.</font><font color=3D"#000000"><br></font></div><div><font colo=
r=3D"#999999"><br></font></div></span><div><div>Users of the standard Templ=
ate Library blindly use the algorithm for searching on any data structure. =
The point is that if a naive approach works better than the algorithm , the=
n there is no point of implementing it on lists.<br></div></div></div></div=
></blockquote><div><br></div><div>I repeat: The efficiency of an operation =
is not always the only or the most important engineering trade-off. I do no=
t accept the premise that faster is always better, nor do I accept the prem=
ise that linear search is always faster than binary search on a list.</div>=
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr"><div><div><div></div></div><span class=3D"gmail-"><div><br></div><=
div><span style=3D"background-color:rgb(255,255,255)"><font color=3D"#99999=
9">&gt;1) It fails to consider the impact of custom allocators which could =
dramatically reduce the cost of iteration</font></span><br></div><div><span=
 style=3D"background-color:rgb(255,255,255)"><font color=3D"#999999"><br></=
font></span></div></span><div><span style=3D"background-color:rgb(255,255,2=
55)"><font color=3D"#000000">I don&#39;t understand how the use of custom a=
llocators will reduce the cost of iteration</font></span></div><div><br></d=
iv></div></div></blockquote><div><br></div><div>Iterating a list is slow on=
 many modern CPUs primarily due to memory access patterns. Allocators can d=
ramatically improve memory access patterns.</div><div><br></div><div>If I h=
ave a list that is fast to iterate because I&#39;ve improved the memory acc=
ess patterns (for example, a pool allocator), then changing my binary searc=
h to a linear search could worsen performance.</div></div></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/CADbh%2BeQgxVq5OL9NuUM29y-9%2Bb%2BO%3=
DC9qk_dCBoPtNxKH-BARFg%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfoo=
ter">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CADbh%2Be=
QgxVq5OL9NuUM29y-9%2Bb%2BO%3DC9qk_dCBoPtNxKH-BARFg%40mail.gmail.com</a>.<br=
 />

--94eb2c190326e4600b0550ae6345--

.

------=_Part_3030_1560420456.1496085319548
Content-Type: multipart/alternative;
 boundary="----=_Part_3031_1218803223.1496085319548"

------=_Part_3031_1218803223.1496085319548
Content-Type: text/plain; charset="UTF-8"

On Monday, May 29, 2017 at 1:07:14 PM UTC-4, Thiago Macieira wrote:
>
> On segunda-feira, 29 de maio de 2017 08:28:02 PDT jay pokarna wrote:
> > To make this change , we need to make std::lower_bound incompatible with
> > lists, which is justified due to performance issues.
>
> How do you propose that be done, concretely? Please include QLinkedList in
> your answer.
>

Does `QLinkedList` have random access iterators? Because that's essentially
what the paper is suggesting: that `lower_bound` and its ilk be limited to
types with random access iterators.

--
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/88349a5a-89ea-442b-8a63-b2f0fdfc6080%40isocpp.org.

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

<div dir=3D"ltr">On Monday, May 29, 2017 at 1:07:14 PM UTC-4, Thiago Maciei=
ra wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: =
0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On segunda-feira, 29 =
de maio de 2017 08:28:02 PDT jay pokarna wrote:
<br>&gt; To make this change , we need to make std::lower_bound incompatibl=
e with
<br>&gt; lists, which is justified due to performance issues.
<br>
<br>How do you propose that be done, concretely? Please include QLinkedList=
 in=20
<br>your answer.
<br></blockquote><div><br>Does `QLinkedList` have random access iterators? =
Because that&#39;s essentially what the paper is suggesting: that `lower_bo=
und` and its ilk be limited to types with random access iterators.<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/88349a5a-89ea-442b-8a63-b2f0fdfc6080%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/88349a5a-89ea-442b-8a63-b2f0fdfc6080=
%40isocpp.org</a>.<br />

------=_Part_3031_1218803223.1496085319548--

------=_Part_3030_1560420456.1496085319548--

.

On 29 May 2017 at 22:15, Nicol Bolas <jmckesson@gmail.com> wrote:
> On Monday, May 29, 2017 at 1:07:14 PM UTC-4, Thiago Macieira wrote:
>>
>> On segunda-feira, 29 de maio de 2017 08:28:02 PDT jay pokarna wrote:
>> > To make this change , we need to make std::lower_bound incompatible with
>> > lists, which is justified due to performance issues.
>>
>> How do you propose that be done, concretely? Please include QLinkedList in
>> your answer.
>
>
> Does `QLinkedList` have random access iterators? Because that's essentially

No.


> what the paper is suggesting: that `lower_bound` and its ilk be limited to
> types with random access iterators.


I believe Thiago's point is that making this breaking change breaks
more than just users of std::list.

--
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/CAFk2RUY27eORGCsBeE9yciK7cDgeo9FFiOiD%2ByWhz5XONsVfrw%40mail.gmail.com.

.

------=_Part_3075_1089113796.1496085818258
Content-Type: multipart/alternative;
 boundary="----=_Part_3076_705896837.1496085818258"

------=_Part_3076_705896837.1496085818258
Content-Type: text/plain; charset="UTF-8"

On Monday, May 29, 2017 at 3:17:15 PM UTC-4, Ville Voutilainen wrote:
>
> On 29 May 2017 at 22:15, Nicol Bolas <jmck...@gmail.com <javascript:>>
> wrote:
> > On Monday, May 29, 2017 at 1:07:14 PM UTC-4, Thiago Macieira wrote:
> >>
> >> On segunda-feira, 29 de maio de 2017 08:28:02 PDT jay pokarna wrote:
> >> > To make this change , we need to make std::lower_bound incompatible
> with
> >> > lists, which is justified due to performance issues.
> >>
> >> How do you propose that be done, concretely? Please include QLinkedList
> in
> >> your answer.
> >
> >
> > Does `QLinkedList` have random access iterators? Because that's
> essentially
>
> No.
>
>
> > what the paper is suggesting: that `lower_bound` and its ilk be limited
> to
> > types with random access iterators.
>
>
> I believe Thiago's point is that making this breaking change breaks
> more than just users of std::list.
>

Oh it absolutely does. Which is why, if this change ought to be made, it
should be made on the incoming `lower_bound` in Ranges TS, not on the
current `lower_bound`.

--
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/f534fea6-f5cc-4eeb-9d66-4d62434ef34b%40isocpp.org.

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

<div dir=3D"ltr">On Monday, May 29, 2017 at 3:17:15 PM UTC-4, Ville Voutila=
inen wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left=
: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 29 May 2017 at 2=
2:15, Nicol Bolas &lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfusca=
ted-mailto=3D"61So-fC7BwAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#3=
9;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&#3=
9;;return true;">jmck...@gmail.com</a>&gt; wrote:
<br>&gt; On Monday, May 29, 2017 at 1:07:14 PM UTC-4, Thiago Macieira wrote=
:
<br>&gt;&gt;
<br>&gt;&gt; On segunda-feira, 29 de maio de 2017 08:28:02 PDT jay pokarna =
wrote:
<br>&gt;&gt; &gt; To make this change , we need to make std::lower_bound in=
compatible with
<br>&gt;&gt; &gt; lists, which is justified due to performance issues.
<br>&gt;&gt;
<br>&gt;&gt; How do you propose that be done, concretely? Please include QL=
inkedList in
<br>&gt;&gt; your answer.
<br>&gt;
<br>&gt;
<br>&gt; Does `QLinkedList` have random access iterators? Because that&#39;=
s essentially
<br>
<br>No.
<br>
<br>
<br>&gt; what the paper is suggesting: that `lower_bound` and its ilk be li=
mited to
<br>&gt; types with random access iterators.
<br>
<br>
<br>I believe Thiago&#39;s point is that making this breaking change breaks
<br>more than just users of std::list.
<br></blockquote><div><br>Oh it absolutely does. Which is why, if this chan=
ge ought to be made, it should be made on the incoming `lower_bound` in Ran=
ges TS, not on the current `lower_bound`.<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/f534fea6-f5cc-4eeb-9d66-4d62434ef34b%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/f534fea6-f5cc-4eeb-9d66-4d62434ef34b=
%40isocpp.org</a>.<br />

------=_Part_3076_705896837.1496085818258--

------=_Part_3075_1089113796.1496085818258--

.

On 29 May 2017 at 22:23, Nicol Bolas <jmckesson@gmail.com> wrote:
>> I believe Thiago's point is that making this breaking change breaks
>> more than just users of std::list.
>
>
> Oh it absolutely does. Which is why, if this change ought to be made, it
> should be made on the incoming `lower_bound` in Ranges TS, not on the
> current `lower_bound`.

And then we should think about why this change should be made. It's
convenient to be
able to binary search non-RAiter ranges, so where's the evidence that
it's bad to allow doing so,
and where's the evidence that there is no code that uses binary search
on such ranges correctly
and happily? What exactly is that code supposed to be rewritten as?

--
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/CAFk2RUbdqNRocSufe53UKW_v7dCNKsNP3_MESi3jwiM9D-0o4A%40mail.gmail.com.

.

--Apple-Mail=_28B08DB3-BE4F-4CD0-A544-CAA04DFDEA1B
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="UTF-8"

On May 29, 2017, at 11:28 AM, jay pokarna <jay.pokarna10@gmail.com> wrote:
>=20
> Hey,
>          The present implementations of the std::binary_search has arbitr=
ary forward iterators as arguments. But it has been found that when the und=
erlying data structure is a list, linear search beats binary search. ( Find=
 the link of the paper attached )
>=20
> The difference in performance of binary search and linear search in the c=
ase of lists is huge ,hence , it is necessary to make changes.
>=20
> I therefore, propose to make std::binary_search incompatible with lists.
>=20
> To make this change , we need to make std::lower_bound incompatible with =
lists, which is justified due to performance issues.
>=20
> Paper

The logic needed to come to this conclusion is that no comparison operation=
 exists that is more expensive than that of 33 character strings with the f=
irst 28 characters being identical.

No doubt that assumption is true a great majority of the time.  But _some_ =
of the time there will be a need to operate on objects with very expensive =
comparison operations.  For example one might be doing a shape optimization=
 using a stress analysis, where each comparison consists of finding the str=
ess at a stress concentration point using finite elements for a given shape=
..  And it might be inconvenient for whatever reason to put your shapes into=
 a container which supports random access iteration.

Another example of an expensive comparison operation is that of a git bisec=
t:  Bisect your commit list until you find the point where you introduced a=
 bug in your code:  Each =E2=80=9Ccomparison operation=E2=80=9D is running =
some kind of a test to see if a bug exists.

As the expense of your comparison operator rises, there will be a point whe=
re the number of comparisons of the search dominates the expense of the alg=
orithm (linear vs binary).  To be maximally useful, the std::lib has to max=
imally flexible.  This means that it can=E2=80=99t be a nanny-lib that prio=
ritizes hand-holding over flexibility.

Otherwise, following this same logic, we should also just remove std::list.=
  Because std::vector is almost always faster.

Howard

--=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/234F418A-8BA4-4114-9D35-3F5B8D17F101%40gmail.com=
..

--Apple-Mail=_28B08DB3-BE4F-4CD0-A544-CAA04DFDEA1B
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename=signature.asc
Content-Type: application/pgp-signature;
 name=signature.asc
Content-Description: Message signed with OpenPGP

-----BEGIN PGP SIGNATURE-----

iQIcBAEBCAAGBQJZLIjwAAoJEGbcHCxKqhWCdnQP/3XJMzwHFSlmYvCD0va3Xd76
7URtbJoS6y3ta7ES1hnVb78BiIxbllsKIGbxL5jeOdR+e/uKlZ5EYwiEOkGcWG80
jo30BLnhBMfkB6rIpwB1RLV9VgLZAug3iYdEw8rO85G0tnr+biiiyH6dpYN9VBob
OBuBeJ11Uv6BZr/P+sxcbJiHiwQKeIeoc99Z4gOvm3w1HSeq0noBColk+eTytlyF
L2tVnzqnMymeTqbzMQif5ISNlAiNEy1N2rFftmrcjOpEzrRojhu4ecYJ2ctI7nq4
ubGpOh+yb1LVVCpeowVjk3sfDBwS1pxKQXxEveld3oX1/5Mq79Dt2phT8+Cc2uqT
ULdbpERqC3u7XeGlrN6n9GhpZFxukThdKNwsXTWLksYxzHrh1I2tdN6TDwYiM5mh
68T6/cB/CRqM4i2USWFMD2AWXOvKMn/rRfhjcgSIa8yz1+zvHIMpGdhuDSBwTJ5x
7uUTYkWF90vJtbAca/tt5u4DU8CGtYkOm6EBpGuX3OhOpbPvcwNAw+aHU7FD5tpf
cQ5wpYERFUcyMXaP/q0S155WojbxrbXXA8qL0QHCMFQRxBQZ5PZ4iN6J8/Rf7pcB
dqPCpYbxCsZg9gINoKk1V9qQ53bcygAOTO0Ba9R09TL/nI3hhw3YBfHeyW1ebK5/
Pseb3zUb2YOYZai0tykx
=APTh
-----END PGP SIGNATURE-----

--Apple-Mail=_28B08DB3-BE4F-4CD0-A544-CAA04DFDEA1B--

.

------=_Part_3026_1988282112.1496093703583
Content-Type: multipart/alternative;
 boundary="----=_Part_3027_601926361.1496093703583"

------=_Part_3027_601926361.1496093703583
Content-Type: text/plain; charset="UTF-8"

On Monday, May 29, 2017 at 3:26:59 PM UTC-4, Ville Voutilainen wrote:
>
> On 29 May 2017 at 22:23, Nicol Bolas <jmck...@gmail.com <javascript:>>
> wrote:
> >> I believe Thiago's point is that making this breaking change breaks
> >> more than just users of std::list.
> >
> >
> > Oh it absolutely does. Which is why, if this change ought to be made, it
> > should be made on the incoming `lower_bound` in Ranges TS, not on the
> > current `lower_bound`.
>
> And then we should think about why this change should be made. It's
> convenient to be
> able to binary search non-RAiter ranges, so where's the evidence that
> it's bad to allow doing so,
> and where's the evidence that there is no code that uses binary search
> on such ranges correctly
> and happily? What exactly is that code supposed to be rewritten as?
>

Presumably, it would be rewritten as `std::find/find_if`.

--
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/6832de4d-1814-477c-8718-c544e182c5d9%40isocpp.org.

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

<div dir=3D"ltr">On Monday, May 29, 2017 at 3:26:59 PM UTC-4, Ville Voutila=
inen wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left=
: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 29 May 2017 at 2=
2:23, Nicol Bolas &lt;<a href=3D"javascript:" target=3D"_blank" gdf-obfusca=
ted-mailto=3D"e4Ij0Xi8BwAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#3=
9;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39;javascript:&#3=
9;;return true;">jmck...@gmail.com</a>&gt; wrote:
<br>&gt;&gt; I believe Thiago&#39;s point is that making this breaking chan=
ge breaks
<br>&gt;&gt; more than just users of std::list.
<br>&gt;
<br>&gt;
<br>&gt; Oh it absolutely does. Which is why, if this change ought to be ma=
de, it
<br>&gt; should be made on the incoming `lower_bound` in Ranges TS, not on =
the
<br>&gt; current `lower_bound`.
<br>
<br>And then we should think about why this change should be made. It&#39;s
<br>convenient to be
<br>able to binary search non-RAiter ranges, so where&#39;s the evidence th=
at
<br>it&#39;s bad to allow doing so,
<br>and where&#39;s the evidence that there is no code that uses binary sea=
rch
<br>on such ranges correctly
<br>and happily? What exactly is that code supposed to be rewritten as?
<br></blockquote><div><br>Presumably, it would be rewritten as `std::find/f=
ind_if`.<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/6832de4d-1814-477c-8718-c544e182c5d9%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/6832de4d-1814-477c-8718-c544e182c5d9=
%40isocpp.org</a>.<br />

------=_Part_3027_601926361.1496093703583--

------=_Part_3026_1988282112.1496093703583--

.

On 29 May 2017, at 21:47, Howard Hinnant <howard.hinnant@gmail.com> wrote:
> Otherwise, following this same logic, we should also just remove std::lis=
t.  Because std::vector is almost always faster.

I'm sure Howard is aware: the key advantage of std::list over std::vector i=
sn't related to speed of operation. Instead, it is stability of references =
and iterators to elements in the std::list.

Where stability is a concern and the comparison operator is expensive, std:=
:lower_bound() makes a differnece compared to std::find() (I haven't found =
a use-case for std::binary_search() as it mere yields a bool rather than th=
e position of the object). Deprectaing or even removing any of these algori=
thms on any iterator category would be ill-advised. If you (the original po=
ster,  ot Howard, obviously) think these algorithms are unfit for your use-=
case(s) don't use them but don't break other uses.

--=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/7B339AF2-212E-4DC4-A4CA-E0B559D55F2D%40gmail.com=
..

.

------=_Part_3205_275168085.1496094738672
Content-Type: multipart/alternative;
 boundary="----=_Part_3206_1106557375.1496094738672"

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

On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>
> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com=20
> <javascript:>> wrote:=20
> > Otherwise, following this same logic, we should also just remove=20
> std::list.  Because std::vector is almost always faster.=20
>
> I'm sure Howard is aware: the key advantage of std::list over std::vector=
=20
> isn't related to speed of operation. Instead, it is stability of referenc=
es=20
> and iterators to elements in the std::list.


Then can we get `stable_vector` standardized? It may not have stability of=
=20
iterators, but it does have stability of references. And that's good enough=
=20
for many cases.

Where stability is a concern and the comparison operator is expensive,=20
> std::lower_bound() makes a differnece compared to std::find() (I haven't=
=20
> found a use-case for std::binary_search() as it mere yields a bool rather=
=20
> than the position of the object). Deprectaing or even removing any of the=
se=20
> algorithms on any iterator category would be ill-advised. If you (the=20
> original poster,  ot Howard, obviously) think these algorithms are unfit=
=20
> for your use-case(s) don't use them but don't break other uses.


I think the point the OP is making is that applying these functions to=20
non-random access containers is a performance trap. It's a tool that is=20
easier to use in inefficient cases than it is to use in the most=20
appropriate ones.

Now, that being said, that point does apply to `std::list` as a whole. If=
=20
we had `stable_vector` (along with splice behavior, which the Boost type=20
doesn't have), `list` would find most of its valid use cases disappearing.=
=20
That would make `list` something of a performance trap itself; something=20
that's seems like the right solution but isn't in most cases.

I don't necessarily agree with the OP's suggestion. But it would be nice if=
=20
there was some way to segregate these kinds of performance traps away from=
=20
regular types/functions. Like a special namespace for special-case tools.=
=20
`std::lower_bound` would only be available for random access iterators, but=
=20
`std::corner::lower_bound` would be available for forward iterators. That=
=20
way, a user makes it clear that they're in a corner case.

--=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/fc7120d4-77d2-4916-8b5b-fbfe63201c5d%40isocpp.or=
g.

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

<div dir=3D"ltr">On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=
=BChl wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-lef=
t: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On 29 May 2017, at=
 21:47, Howard Hinnant &lt;<a href=3D"javascript:" target=3D"_blank" gdf-ob=
fuscated-mailto=3D"zvU5yrbDBwAJ" rel=3D"nofollow" onmousedown=3D"this.href=
=3D&#39;javascript:&#39;;return true;" onclick=3D"this.href=3D&#39;javascri=
pt:&#39;;return true;">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list. =C2=A0Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br><br></div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: =
1ex;">Where stability is a concern and the comparison operator is expensive=
, std::lower_bound() makes a differnece compared to std::find() (I haven&#3=
9;t found a use-case for std::binary_search() as it mere yields a bool rath=
er than the position of the object). Deprectaing or even removing any of th=
ese algorithms on any iterator category would be ill-advised. If you (the o=
riginal poster, =C2=A0ot Howard, obviously) think these algorithms are unfi=
t for your use-case(s) don&#39;t use them but don&#39;t break other uses.</=
blockquote><div><br>I think the point the OP is making is that applying the=
se functions to non-random access containers is a performance trap. It&#39;=
s a tool that is easier to use in inefficient cases than it is to use in th=
e most appropriate ones.<br><br>Now, that being said, that point does apply=
 to `std::list` as a whole. If we had `stable_vector` (along with splice be=
havior, which the Boost type doesn&#39;t have), `list` would find most of i=
ts valid use cases disappearing. That would make `list` something of a perf=
ormance trap itself; something that&#39;s seems like the right solution but=
 isn&#39;t in most cases.<br><br>I don&#39;t necessarily agree with the OP&=
#39;s suggestion. But it would be nice if there was some way to segregate t=
hese kinds of performance traps away from regular types/functions. Like a s=
pecial namespace for special-case tools. `std::lower_bound` would only be a=
vailable for random access iterators, but `std::corner::lower_bound` would =
be available for forward iterators. That way, a user makes it clear that th=
ey&#39;re in a corner case.<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/fc7120d4-77d2-4916-8b5b-fbfe63201c5d%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/fc7120d4-77d2-4916-8b5b-fbfe63201c5d=
%40isocpp.org</a>.<br />

------=_Part_3206_1106557375.1496094738672--

------=_Part_3205_275168085.1496094738672--

.

--Apple-Mail=_348B51AC-C74E-4EAE-AD1A-A788A994FD04
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="UTF-8"

On May 29, 2017, at 5:39 PM, Dietmar K=C3=BChl <dietmar.kuehl@gmail.com> wr=
ote:
>=20
> On 29 May 2017, at 21:47, Howard Hinnant <howard.hinnant@gmail.com> wrote=
:
>> Otherwise, following this same logic, we should also just remove std::li=
st.  Because std::vector is almost always faster.
>=20
> I'm sure Howard is aware: the key advantage of std::list over std::vector=
 isn't related to speed of operation. Instead, it is stability of reference=
s and iterators to elements in the std::list.
>=20
> Where stability is a concern and the comparison operator is expensive, st=
d::lower_bound() makes a differnece compared to std::find() (I haven't foun=
d a use-case for std::binary_search() as it mere yields a bool rather than =
the position of the object). Deprectaing or even removing any of these algo=
rithms on any iterator category would be ill-advised. If you (the original =
poster,  ot Howard, obviously) think these algorithms are unfit for your us=
e-case(s) don't use them but don't break other uses.

Yup, this is a good time to mention vector<unique_ptr<T>>.  Stable referenc=
es, though not stable iterators.  The std::lib has all kinds of good flexib=
ility.  And (agreeing with Dietmar) we shouldn=E2=80=99t outlaw any of the =
existing std::lib because it=E2=80=99s use case is correct but small.  Brea=
king existing code is a serious affair.  We do it sometimes.  But the motiv=
ation for doing so should be high, with more attractive (and easy) migratio=
n provided at the same time.

Howard

--=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/4F8A17D5-8958-4473-AFF1-FFDC1C036990%40gmail.com=
..

--Apple-Mail=_348B51AC-C74E-4EAE-AD1A-A788A994FD04
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename=signature.asc
Content-Type: application/pgp-signature;
 name=signature.asc
Content-Description: Message signed with OpenPGP

-----BEGIN PGP SIGNATURE-----

iQIcBAEBCAAGBQJZLM4TAAoJEGbcHCxKqhWCqAMP/iCDmfO0hgnncsMvkzPCTDeV
MV43KLXzKlryNh7s4O4XIVkT8Quq5JBv8jJc5aoZSG4EVag3aFd5ulFbiRqw3eYC
6HooDxHOcYyqe2k0D+Nb3H6m2z0T2/exQ7W6xr/Qin7e2xmF2jNmapJvN3sY9nUs
ctgcdUsia8JYJIpDMsZyPBCDZ1uPmZ1OUBVYcCm1kWEU52s07uSDmclT4iz5ow02
09L15WgCkf+Wb3NiRpmpdxKHcMoGjU3z6/R4HpLEFYEfNSxKDVBmjlJj7NovDccH
Z6kDQJ1OUYzEVF/sJ6xxc4Heh2UcWQiPicnxIefQ3Q3Olufus2miN/L9hZs5FkAx
vq4qXHRcbxV8ZmDuZZp1TUcFRkKTQP3oDXD6u8+raEg7U7e2k/ROBSf35yIjtvo8
WXrig+l4nQPzNRNzX2wFIKuBbLpx5wpr8FPutDRS2SPMMJoV+HVPYwL61O4v70Ea
7l87oTpycNZVsorosDMpa1CWia48nfYNeTUEQxya6JSwSWIcUgW0v4ak4JKxHJsA
pDUNuh77FvXnYzlswie2UfOYcdJoSD1nqsF1lCZ448UwWNJXbeRLZknRTfFAJ5Bk
NXLiumlUR9lneiVI0/J3J7ke8bVbqVILhPxg+7CwB7NLci59HEZtmFifcpHsd20b
aout2lm1yQfwPLk8gIYW
=4fKX
-----END PGP SIGNATURE-----

--Apple-Mail=_348B51AC-C74E-4EAE-AD1A-A788A994FD04--

.

------=_Part_3316_936722180.1496123837723
Content-Type: multipart/alternative;
 boundary="----=_Part_3317_997939845.1496123837723"

------=_Part_3317_997939845.1496123837723
Content-Type: text/plain; charset="UTF-8"

So basically we should use , the binary_search operation on lists when the
cost of comparison is huge as compared to other operations. In other cases
, we should use linear search.

Is there something that I am missing out here?

--
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/75948422-2b81-4820-8f70-fc52d141c29b%40isocpp.org.

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

<div dir=3D"ltr"><div>So basically we should use , the binary_search operat=
ion on lists when the cost of comparison is huge as compared to other opera=
tions. In other cases , we should use linear search.</div><div><br></div><d=
iv>Is there something that I am missing out here? =C2=A0<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/75948422-2b81-4820-8f70-fc52d141c29b%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/75948422-2b81-4820-8f70-fc52d141c29b=
%40isocpp.org</a>.<br />

------=_Part_3317_997939845.1496123837723--

------=_Part_3316_936722180.1496123837723--

.

------=_Part_3289_793133193.1496129826966
Content-Type: multipart/alternative;
 boundary="----=_Part_3290_1348982332.1496129826966"

------=_Part_3290_1348982332.1496129826966
Content-Type: text/plain; charset="UTF-8"

A general doubt :
                        What is the cost of comparison of equality of 2
iterators in c++?

--
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/3a43841b-0e56-48b5-9254-cc77275ca05b%40isocpp.org.

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

<div dir=3D"ltr">A general doubt :=C2=A0<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 What is the cost of=
 comparison of equality of 2 iterators in c++?</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/3a43841b-0e56-48b5-9254-cc77275ca05b%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/3a43841b-0e56-48b5-9254-cc77275ca05b=
%40isocpp.org</a>.<br />

------=_Part_3290_1348982332.1496129826966--

------=_Part_3289_793133193.1496129826966--

.

On 30 May 2017 at 10:37, jay pokarna <jay.pokarna10@gmail.com> wrote:
> A general doubt :
>                         What is the cost of comparison of equality of 2
> iterators in c++?


What does that cost have to do with binary_search?

--
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/CAFk2RUaaFZs-5u2JTqvXd5W6poDBi6-eh_UKEj3_87SVBpAe7w%40mail.gmail.com.

.

------=_Part_2532_1660252464.1496139390710
Content-Type: multipart/alternative;
 boundary="----=_Part_2533_1666834408.1496139390710"

------=_Part_2533_1666834408.1496139390710
Content-Type: text/plain; charset="UTF-8"

Binary_search just calls lower_bound function and does some operations. So
, the working of binary_search is dependent on lower_bound.

The distance method in the lower_bound algorithm does comparison of
iterators after incrementing it. This is the case with lists. The code is
as below:

template <class ForwardIterator, class T>
ForwardIterator
lower_bound(ForwardIterator first, ForwardIterator last, const T& value)
{
 typedef typename iterator_traits<ForwardIterator>::difference_type
difference_type;
difference_type len = distance(first, last);
while (len > 0)
 {
ForwardIterator i = first;
difference_type len2 = len / 2;
advance(i, len2);
if (*i < value)
 {
first = ++i;
len -= len2 + 1;
 }
else
 len = len2;
 }
 return first;
}

For lists , the distance function is implemented as:

template <class InputIterator>
inline
typename iterator_traits<InputIterator>::difference_type
__distance(InputIterator first, InputIterator last, input_iterator_tag)
{
 typename iterator_traits<InputIterator>::difference_type result = 0;
for (; first *!= *last; ++first)
++result;
return result;
}

If the cost of comparison of iterators is amortized constant time , then it
is fine. But if the cost of comparison of iterators , is proportional to
the cost of comparison of the record itself , then binary search algorithm
doesn't decrease the number of comparisons done.

--
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/07f519ba-2cd1-40d6-8c35-350a173f0800%40isocpp.org.

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

<div dir=3D"ltr"><div>Binary_search just calls lower_bound function and doe=
s some operations. So , the working of binary_search is dependent on lower_=
bound.</div><div><br></div>The distance method in the lower_bound algorithm=
 does comparison of iterators after incrementing it. This is the case with =
lists. The code is as below:<div><br></div><div><div><font face=3D"courier =
new, monospace">template &lt;class ForwardIterator, class T&gt;</font></div=
><div><font face=3D"courier new, monospace">ForwardIterator</font></div><di=
v><font face=3D"courier new, monospace">lower_bound(ForwardIterator first, =
ForwardIterator last, const T&amp; value)</font></div><div><font face=3D"co=
urier new, monospace">{</font></div><div><font face=3D"courier new, monospa=
ce">=C2=A0typedef typename iterator_traits&lt;ForwardIterator&gt;::differen=
ce_type difference_type;</font></div><div><font face=3D"courier new, monosp=
ace">difference_type len =3D distance(first, last);</font></div><div><font =
face=3D"courier new, monospace">while (len &gt; 0)</font></div><div><font f=
ace=3D"courier new, monospace">=C2=A0{</font></div><div><font face=3D"couri=
er new, monospace">ForwardIterator i =3D first;</font></div><div><font face=
=3D"courier new, monospace">difference_type len2 =3D len / 2;</font></div><=
div><font face=3D"courier new, monospace">advance(i, len2);</font></div><di=
v><font face=3D"courier new, monospace">if (*i &lt; value)</font></div><div=
><font face=3D"courier new, monospace">=C2=A0{</font></div><div><font face=
=3D"courier new, monospace">first =3D ++i;</font></div><div><font face=3D"c=
ourier new, monospace">len -=3D len2 + 1;</font></div><div><font face=3D"co=
urier new, monospace">=C2=A0}</font></div><div><font face=3D"courier new, m=
onospace">else</font></div><div><font face=3D"courier new, monospace">=C2=
=A0len =3D len2;</font></div><div><font face=3D"courier new, monospace">=C2=
=A0}</font></div><div><font face=3D"courier new, monospace">=C2=A0return fi=
rst;</font></div><div><font face=3D"courier new, monospace">}</font></div><=
/div><div><br></div><div>For lists , the distance function is implemented a=
s:</div><div><br></div><div><div><font face=3D"courier new, monospace">temp=
late &lt;class InputIterator&gt;</font></div><div><font face=3D"courier new=
, monospace">inline</font></div><div><font face=3D"courier new, monospace">=
typename iterator_traits&lt;InputIterator&gt;::difference_type</font></div>=
<div><font face=3D"courier new, monospace">__distance(InputIterator first, =
InputIterator last, input_iterator_tag)</font></div><div><font face=3D"cour=
ier new, monospace">{</font></div><div><font face=3D"courier new, monospace=
">=C2=A0typename iterator_traits&lt;InputIterator&gt;::difference_type resu=
lt =3D 0;</font></div><div><font face=3D"courier new, monospace">for (; fir=
st=C2=A0<b><i><u>!=3D</u>=C2=A0</i></b>last; ++first)</font></div><div><fon=
t face=3D"courier new, monospace">++result;</font></div><div><font face=3D"=
courier new, monospace">return result;</font></div><div><font face=3D"couri=
er new, monospace">}</font></div></div><div><br></div><div>If the cost of c=
omparison of iterators is amortized constant time , then it is fine. But if=
 the cost of comparison of iterators , is proportional to the cost of compa=
rison of the record itself , then binary search algorithm doesn&#39;t decre=
ase the number of comparisons done.</div><div><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/07f519ba-2cd1-40d6-8c35-350a173f0800%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/07f519ba-2cd1-40d6-8c35-350a173f0800=
%40isocpp.org</a>.<br />

------=_Part_2533_1666834408.1496139390710--

------=_Part_2532_1660252464.1496139390710--

.

On 30 May 2017 at 13:16, jay pokarna <jay.pokarna10@gmail.com> wrote:
> is fine. But if the cost of comparison of iterators , is proportional to the
> cost of comparison of the record itself , then binary search algorithm


It isn't.

--
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/CAFk2RUanCJHz-%2BbJ2%3DEpyTsEmJtzUyKCrcsR4vC4zP7Lpx1xhw%40mail.gmail.com.

.

------=_Part_2634_218488899.1496143430662
Content-Type: multipart/alternative;
 boundary="----=_Part_2635_1448368321.1496143430662"

------=_Part_2635_1448368321.1496143430662
Content-Type: text/plain; charset="UTF-8"

I wanted to know if it is constant time. If it isn't then what is the order
of its cost?
 I mean logarithmic or linear or something else.

--
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/cdbcb63c-367e-445e-8c3d-404c219c0bad%40isocpp.org.

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

<div dir=3D"ltr">I wanted to know if it is constant time. If it isn&#39;t t=
hen what is the order of its cost?<div>=C2=A0I mean logarithmic or linear o=
r something else.</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/cdbcb63c-367e-445e-8c3d-404c219c0bad%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/cdbcb63c-367e-445e-8c3d-404c219c0bad=
%40isocpp.org</a>.<br />

------=_Part_2635_1448368321.1496143430662--

------=_Part_2634_218488899.1496143430662--

.

On 30 May 2017 at 14:23, jay pokarna <jay.pokarna10@gmail.com> wrote:
> I wanted to know if it is constant time. If it isn't then what is the order
> of its cost?
>  I mean logarithmic or linear or something else.

It's constant, and has nothing to do with the comparison the cost of
which discussion has been about,
which is the element comparison.

--
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/CAFk2RUYVi_iGf9Bo2ud6uTiqjsEfzSzq10io7RCRt7s4y2DECg%40mail.gmail.com.

.

On 2017-05-29 14:02, jay pokarna wrote:
> LinkedLists have their own use. When you cannot allocate contiguous memory
> locations , due to issues like memory to be allocated , or size of memory,
> then we don't have any other option than to use a list. Hence, it cannot be
> ruled out. Moreover , the problem is not std::list or std::binary_search.
> The problem is using binary search to search a list.

Some of this could be solved by an STL container that has the API of
vector<T> but is implemented more like vector<unique_ptr<T>>. (Yes, I
would like such a class; an *actual* vector<unique_ptr<T>> imposes
awkward indirections and lack of pure value semantics on its users that
can be eliminated by a dedicated container type.)

--
Matthew

--
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/21823b95-8c77-b45a-b7be-8af7b434f765%40gmail.com.

.

On Tuesday, 30 May 2017 11:13:20 PDT Matthew Woehlke wrote:
> On 2017-05-29 14:02, jay pokarna wrote:
> > LinkedLists have their own use. When you cannot allocate contiguous memory
> > locations , due to issues like memory to be allocated , or size of memory,
> > then we don't have any other option than to use a list. Hence, it cannot
> > be
> > ruled out. Moreover , the problem is not std::list or std::binary_search.
> > The problem is using binary search to search a list.
>
> Some of this could be solved by an STL container that has the API of
> vector<T> but is implemented more like vector<unique_ptr<T>>. (Yes, I
> would like such a class; an *actual* vector<unique_ptr<T>> imposes
> awkward indirections and lack of pure value semantics on its users that
> can be eliminated by a dedicated container type.)

And that's exactly what QList is for most T and we're trying hard to get rid
of it...

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel Open Source Technology Center

--
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/10321925.RW9JP66qb1%40tjmaciei-mobl1.

.

------=_Part_3838_1253987251.1496170393924
Content-Type: multipart/alternative;
 boundary="----=_Part_3839_57310978.1496170393924"

------=_Part_3839_57310978.1496170393924
Content-Type: text/plain; charset="UTF-8"

On Tuesday, May 30, 2017 at 2:17:35 PM UTC-4, Thiago Macieira wrote:
>
> On Tuesday, 30 May 2017 11:13:20 PDT Matthew Woehlke wrote:
> > On 2017-05-29 14:02, jay pokarna wrote:
> > > LinkedLists have their own use. When you cannot allocate contiguous
> memory
> > > locations , due to issues like memory to be allocated , or size of
> memory,
> > > then we don't have any other option than to use a list. Hence, it
> cannot
> > > be
> > > ruled out. Moreover , the problem is not std::list or
> std::binary_search.
> > > The problem is using binary search to search a list.
> >
> > Some of this could be solved by an STL container that has the API of
> > vector<T> but is implemented more like vector<unique_ptr<T>>. (Yes, I
> > would like such a class; an *actual* vector<unique_ptr<T>> imposes
> > awkward indirections and lack of pure value semantics on its users that
> > can be eliminated by a dedicated container type.)
>
> And that's exactly what QList is for most T and we're trying hard to get
> rid
> of it...
>

Well it's a bad thing when you *don't* want it. But that doesn't mean it
isn't a useful tool to have in your toolbox. `stable_vector` (which is what
we're talking about) is a good and useful class for certain situations.

It's just that you need to know that's what you're getting. `QList` has a
short name, which encourages people to use it by default. And that's the
wrong type to be using "by default".

Also, `QList` allows you to provide your own `T*`s, so that you can put
derived classes into a `QList<Base>`. `stable_vector` explicitly hides the
fact that it's dynamically allocating the `T`'s.

--
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/1130b172-7112-4379-9177-569dee5f7f07%40isocpp.org.

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

<div dir=3D"ltr">On Tuesday, May 30, 2017 at 2:17:35 PM UTC-4, Thiago Macie=
ira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Tuesday, 30 May 2=
017 11:13:20 PDT Matthew Woehlke wrote:
<br>&gt; On 2017-05-29 14:02, jay pokarna wrote:
<br>&gt; &gt; LinkedLists have their own use. When you cannot allocate cont=
iguous memory
<br>&gt; &gt; locations , due to issues like memory to be allocated , or si=
ze of memory,
<br>&gt; &gt; then we don&#39;t have any other option than to use a list. H=
ence, it cannot
<br>&gt; &gt; be
<br>&gt; &gt; ruled out. Moreover , the problem is not std::list or std::bi=
nary_search.
<br>&gt; &gt; The problem is using binary search to search a list.
<br>&gt;=20
<br>&gt; Some of this could be solved by an STL container that has the API =
of
<br>&gt; vector&lt;T&gt; but is implemented more like vector&lt;unique_ptr&=
lt;T&gt;&gt;. (Yes, I
<br>&gt; would like such a class; an *actual* vector&lt;unique_ptr&lt;T&gt;=
&gt; imposes
<br>&gt; awkward indirections and lack of pure value semantics on its users=
 that
<br>&gt; can be eliminated by a dedicated container type.)
<br>
<br>And that&#39;s exactly what QList is for most T and we&#39;re trying ha=
rd to get rid=20
<br>of it...
<br></blockquote><div><br>Well it&#39;s a bad thing when you <i>don&#39;t</=
i> want it. But that doesn&#39;t mean it isn&#39;t a useful tool to have in=
 your toolbox. `stable_vector` (which is what we&#39;re talking about) is a=
 good and useful class for certain situations.<br><br>It&#39;s just that yo=
u need to know that&#39;s what you&#39;re getting. `QList` has a short name=
, which encourages people to use it by default. And that&#39;s the wrong ty=
pe to be using &quot;by default&quot;.<br><br>Also, `QList` allows you to p=
rovide your own `T*`s, so that you can put derived classes into a `QList&lt=
;Base&gt;`. `stable_vector` explicitly hides the fact that it&#39;s dynamic=
ally allocating the `T`&#39;s.<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/1130b172-7112-4379-9177-569dee5f7f07%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/1130b172-7112-4379-9177-569dee5f7f07=
%40isocpp.org</a>.<br />

------=_Part_3839_57310978.1496170393924--

------=_Part_3838_1253987251.1496170393924--

.

------=_Part_3725_640524219.1496170451614
Content-Type: multipart/alternative;
 boundary="----=_Part_3726_82339755.1496170451614"

------=_Part_3726_82339755.1496170451614
Content-Type: text/plain; charset="UTF-8"



On Tuesday, May 30, 2017 at 2:53:14 PM UTC-4, Nicol Bolas wrote:
>
> On Tuesday, May 30, 2017 at 2:17:35 PM UTC-4, Thiago Macieira wrote:
>>
>> On Tuesday, 30 May 2017 11:13:20 PDT Matthew Woehlke wrote:
>> > On 2017-05-29 14:02, jay pokarna wrote:
>> > > LinkedLists have their own use. When you cannot allocate contiguous
>> memory
>> > > locations , due to issues like memory to be allocated , or size of
>> memory,
>> > > then we don't have any other option than to use a list. Hence, it
>> cannot
>> > > be
>> > > ruled out. Moreover , the problem is not std::list or
>> std::binary_search.
>> > > The problem is using binary search to search a list.
>> >
>> > Some of this could be solved by an STL container that has the API of
>> > vector<T> but is implemented more like vector<unique_ptr<T>>. (Yes, I
>> > would like such a class; an *actual* vector<unique_ptr<T>> imposes
>> > awkward indirections and lack of pure value semantics on its users that
>> > can be eliminated by a dedicated container type.)
>>
>> And that's exactly what QList is for most T and we're trying hard to get
>> rid
>> of it...
>>
>
> Well it's a bad thing when you *don't* want it. But that doesn't mean it
> isn't a useful tool to have in your toolbox. `stable_vector` (which is what
> we're talking about) is a good and useful class for certain situations.
>
> It's just that you need to know that's what you're getting. `QList` has a
> short name, which encourages people to use it by default. And that's the
> wrong type to be using "by default".
>
> Also, `QList` allows you to provide your own `T*`s, so that you can put
> derived classes into a `QList<Base>`. `stable_vector` explicitly hides the
> fact that it's dynamically allocating the `T`'s.
>

No wait, sorry; skip that last paragraph. I was thinking about the wrong
type.

--
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/90098642-72fd-46f3-9d64-9952896e6da5%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Tuesday, May 30, 2017 at 2:53:14 PM UTC-4, Nico=
l Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
>On Tuesday, May 30, 2017 at 2:17:35 PM UTC-4, Thiago Macieira wrote:<block=
quote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left=
:1px #ccc solid;padding-left:1ex">On Tuesday, 30 May 2017 11:13:20 PDT Matt=
hew Woehlke wrote:
<br>&gt; On 2017-05-29 14:02, jay pokarna wrote:
<br>&gt; &gt; LinkedLists have their own use. When you cannot allocate cont=
iguous memory
<br>&gt; &gt; locations , due to issues like memory to be allocated , or si=
ze of memory,
<br>&gt; &gt; then we don&#39;t have any other option than to use a list. H=
ence, it cannot
<br>&gt; &gt; be
<br>&gt; &gt; ruled out. Moreover , the problem is not std::list or std::bi=
nary_search.
<br>&gt; &gt; The problem is using binary search to search a list.
<br>&gt;=20
<br>&gt; Some of this could be solved by an STL container that has the API =
of
<br>&gt; vector&lt;T&gt; but is implemented more like vector&lt;unique_ptr&=
lt;T&gt;&gt;. (Yes, I
<br>&gt; would like such a class; an *actual* vector&lt;unique_ptr&lt;T&gt;=
&gt; imposes
<br>&gt; awkward indirections and lack of pure value semantics on its users=
 that
<br>&gt; can be eliminated by a dedicated container type.)
<br>
<br>And that&#39;s exactly what QList is for most T and we&#39;re trying ha=
rd to get rid=20
<br>of it...
<br></blockquote><div><br>Well it&#39;s a bad thing when you <i>don&#39;t</=
i> want it. But that doesn&#39;t mean it isn&#39;t a useful tool to have in=
 your toolbox. `stable_vector` (which is what we&#39;re talking about) is a=
 good and useful class for certain situations.<br><br>It&#39;s just that yo=
u need to know that&#39;s what you&#39;re getting. `QList` has a short name=
, which encourages people to use it by default. And that&#39;s the wrong ty=
pe to be using &quot;by default&quot;.<br><br>Also, `QList` allows you to p=
rovide your own `T*`s, so that you can put derived classes into a `QList&lt=
;Base&gt;`. `stable_vector` explicitly hides the fact that it&#39;s dynamic=
ally allocating the `T`&#39;s.<br></div></div></blockquote><div><br>No wait=
, sorry; skip that last paragraph. I was thinking about the wrong type. <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/90098642-72fd-46f3-9d64-9952896e6da5%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/90098642-72fd-46f3-9d64-9952896e6da5=
%40isocpp.org</a>.<br />

------=_Part_3726_82339755.1496170451614--

------=_Part_3725_640524219.1496170451614--

.

On Tuesday, 30 May 2017 11:53:13 PDT Nicol Bolas wrote:
> > And that's exactly what QList is for most T and we're trying hard to get
> > rid
> > of it...
>
> Well it's a bad thing when you *don't* want it. But that doesn't mean it
> isn't a useful tool to have in your toolbox. `stable_vector` (which is what
> we're talking about) is a good and useful class for certain situations.
>
> It's just that you need to know that's what you're getting. `QList` has a
> short name, which encourages people to use it by default. And that's the
> wrong type to be using "by default".

Indeed.

It also has a problem that it's schizophrenic and chooses whether to be a
vector or a stable_vector depending on the type T, so it may be good for some
types of T, but not others. And that may vary per platform, because the
decision depends on the size of a pointer.

There's a discussion on what to do for Qt 6. We'll probably keep the "stable
vector" functionality, just under a different name and without the selection.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel Open Source Technology Center

--
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/2382175.NIxEvJXn1D%40tjmaciei-mobl1.

.

------=_Part_4175_158710982.1496184778718
Content-Type: multipart/alternative;
 boundary="----=_Part_4176_1708212959.1496184778718"

------=_Part_4176_1708212959.1496184778718
Content-Type: text/plain; charset="UTF-8"

On Tuesday, May 30, 2017 at 1:12:58 PM UTC-6, Thiago Macieira wrote:
>
> On Tuesday, 30 May 2017 11:53:13 PDT Nicol Bolas wrote:
> > > And that's exactly what QList is for most T and we're trying hard to
> get
> > > rid
> > > of it...
> >
> > Well it's a bad thing when you *don't* want it. But that doesn't mean it
> > isn't a useful tool to have in your toolbox. `stable_vector` (which is
> what
> > we're talking about) is a good and useful class for certain situations.
> >



>
> It also has a problem that it's schizophrenic and chooses whether to be a
> vector or a stable_vector depending on the type T, so it may be good for
> some
> types of T, but not others. And that may vary per platform, because the
> decision depends on the size of a pointer.
>

As for the awkward indirection semantics of vector<unique_ptr<T>>, I like
the direction towards polymorphic value semantics that a number of people
have been pushing towards, such as with Sean Parent's 'inheritance is the
base class of evil', and various recent conversations in this reflector
about automatic proxies from concepts, or 'runtime concepts' ideas.

I've also seen recent libraries such as value_ptr
(https://hackernoon.com/value-ptr-the-missing-c-smart-pointer-1f515664153e),
which if I understand it, aims to give value semantics to
freestore-allocated objects (which to me seems to be a sub-case of general
pushes towards polymorphic value semantics).

It seems to me that if all these general efforts towards polymorphic values
could be unified and standardized, then vector<PolymorphicValue> would be
preferable to having a whole new container type similar to vector.  (That
is, assuming that polymorphic value semantics can solve all the use cases
for the similar container types).  If polymorphic value semantics can be
made composable with the existing STL, it could potentially solve the
problem for the whole STL, not just vector<>, and might provide other more
general solutions.

-Andy

--
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/43fa883b-310f-476d-b0ab-dfcebde1ebab%40isocpp.org.

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

<div dir=3D"ltr">On Tuesday, May 30, 2017 at 1:12:58 PM UTC-6, Thiago Macie=
ira wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px 0px 0.=
8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">On Tues=
day, 30 May 2017 11:53:13 PDT Nicol Bolas wrote:=C2=A0<br>&gt; &gt; And tha=
t&#39;s exactly what QList is for most T and we&#39;re trying hard to get=
=C2=A0<br>&gt; &gt; rid=C2=A0<br>&gt; &gt; of it...=C2=A0<br>&gt;=C2=A0<br>=
&gt; Well it&#39;s a bad thing when you *don&#39;t* want it. But that doesn=
&#39;t mean it=C2=A0<br>&gt; isn&#39;t a useful tool to have in your toolbo=
x. `stable_vector` (which is what=C2=A0<br>&gt; we&#39;re talking about) is=
 a good and useful class for certain situations.=C2=A0<br>&gt;</blockquote>=
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0px 0px=
 0px 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">=
<br>It also has a problem that it&#39;s schizophrenic and chooses whether t=
o be a=C2=A0<br>vector or a stable_vector depending on the type T, so it ma=
y be good for some=C2=A0<br>types of T, but not others. And that may vary p=
er platform, because the=C2=A0<br>decision depends on the size of a pointer=
..=C2=A0<br></blockquote><div>=C2=A0</div>As for the awkward indirection sem=
antics of vector&lt;unique_ptr&lt;T&gt;&gt;, I like the direction towards p=
olymorphic value semantics that a number of people have been pushing toward=
s, such as with Sean Parent&#39;s &#39;inheritance is the base class of evi=
l&#39;, and various recent conversations in this reflector about automatic =
proxies from concepts, or &#39;runtime concepts&#39; ideas.<br><br>I&#39;ve=
 also seen recent libraries such as value_ptr (https://hackernoon.com/value=
-ptr-the-missing-c-smart-pointer-1f515664153e), which if I understand it, a=
ims to give value semantics to freestore-allocated objects (which to me see=
ms to be a sub-case of general pushes towards polymorphic value semantics).=
<br><br>It seems to me that if all these general efforts towards polymorphi=
c values could be unified and standardized, then vector&lt;PolymorphicValue=
&gt; would be preferable to having a whole new container type similar to ve=
ctor. =C2=A0(That is, assuming that polymorphic value semantics can solve a=
ll the use cases for the similar container types). =C2=A0If polymorphic val=
ue semantics can be made composable with the existing STL, it could potenti=
ally solve the problem for the whole STL, not just vector&lt;&gt;, and migh=
t provide other more general solutions.<div><br></div><div>-Andy</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/43fa883b-310f-476d-b0ab-dfcebde1ebab%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/43fa883b-310f-476d-b0ab-dfcebde1ebab=
%40isocpp.org</a>.<br />

------=_Part_4176_1708212959.1496184778718--

------=_Part_4175_158710982.1496184778718--

.

------=_Part_4114_236862562.1496186329257
Content-Type: multipart/alternative;
 boundary="----=_Part_4115_1947552013.1496186329258"

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

On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:
>
> On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>>
>> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com> wrote:=
=20
>> > Otherwise, following this same logic, we should also just remove=20
>> std::list.  Because std::vector is almost always faster.=20
>>
>> I'm sure Howard is aware: the key advantage of std::list over std::vecto=
r=20
>> isn't related to speed of operation. Instead, it is stability of referen=
ces=20
>> and iterators to elements in the std::list.
>
>
> Then can we get `stable_vector` standardized? It may not have stability o=
f=20
> iterators, but it does have stability of references. And that's good enou=
gh=20
> for many cases.
>

I found a thing called Boost.stable_vector, but from the documentation I=20
cannot tell what makes it different from std::deque<T>.  std::deque<T> has=
=20
stability of references (if insertion is happening only at the front or=20
back) and instability of iterators (unless insertion is happening only at=
=20
the back, in practice, although I'm not sure if you can count on this).
Nicol, I know this is a tangent, but could you explain what's missing from=
=20
std::deque<T> and how you'd propose for a new container to fix it?


I think the point the OP is making is that applying these functions to=20
> non-random access containers is a performance trap. It's a tool that is=
=20
> easier to use in inefficient cases than it is to use in the most=20
> appropriate ones.
>
> Now, that being said, that point does apply to `std::list` as a whole. If=
=20
> we had `stable_vector` (along with splice behavior, which the Boost type=
=20
> doesn't have), `list` would find most of its valid use cases disappearing=
..=20
> That would make `list` something of a performance trap itself; something=
=20
> that's seems like the right solution but isn't in most cases.
>
> I don't necessarily agree with the OP's suggestion. But it would be nice=
=20
> if there was some way to segregate these kinds of performance traps away=
=20
> from regular types/functions. Like a special namespace for special-case=
=20
> tools. `std::lower_bound` would only be available for random access=20
> iterators, but `std::corner::lower_bound` would be available for forward=
=20
> iterators. That way, a user makes it clear that they're in a corner case.
>

That's an interesting idea; but doesn't that completely break generic=20
programming?  Now anytime I want to implement, let's say, my::equal_range()=
=20
=E2=80=94 [Because I need an example of an algorithm that might plausibly d=
epend on=20
std::lower_bound(), let's pretend std::equal_range() doesn't exist.] =E2=80=
=94 I=20
can't just write

auto equal_range(It first, It last, T value) {
    auto it =3D std::lower_bound(first, last, value);
    auto jt =3D std::upper_bound(it, last, value);
    return std::pair{it, jt};
}

Instead I'll have to write... this?

auto equal_range(It first, It last, T value) {
    auto it =3D std::corner::lower_bound(first, last, value);
    auto jt =3D std::corner::upper_bound(it, last, value);
    return std::pair{it, jt};
}

Or perhaps this?

// SFINAE'd for just the non-corner case
auto equal_range(It first, It last, T value,=20
void_t<decltype(std::lower_bound(first, last, value))>* =3D nullptr) {
    auto it =3D std::lower_bound(first, last, value);
    auto jt =3D std::upper_bound(it, last, value);
    return std::pair{it, jt};
}

// SFINAE'd for the corner case =E2=80=94 does this overload belong in name=
space=20
my::corner now?
auto equal_range(It first, It last, T value,=20
void_t<decltype(std::corner::lower_bound(first, last, value))>* =3D nullptr=
) {
    auto it =3D std::corner::lower_bound(first, last, value);
    auto jt =3D std::corner::upper_bound(it, last, value);
    return std::pair{it, jt};
}

It just seems like a lot of boilerplate for zero benefit.

Meanwhile, it's easy (although not trivial) for any STL vendor to give a=20
non-fatal diagnostic=20
<https://stackoverflow.com/questions/8936063/does-there-exist-a-static-warn=
ing>=20
on e.g. lower_bound of a BidirectionalIterator, if they really *wanted* to.=
=20
 There's definitely room for a clang-tidy check there, too.  However, many=
=20
knowledgeable people who *could* be working on that problem are *not*=20
working on it, apparently because they have more important things to do.=20
 If this problem is really important to OP, maybe OP should work on it? :)

=E2=80=93Arthur

--=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/6d90b3ff-5129-44f2-9188-1e695b91703e%40isocpp.or=
g.

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

<div dir=3D"ltr">On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas w=
rote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr">On Monda=
y, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:<blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #cc=
c solid;padding-left:1ex">On 29 May 2017, at 21:47, Howard Hinnant &lt;<a r=
el=3D"nofollow">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list. =C2=A0Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br></div></div></blockquote><div><br></div><div>I fo=
und a thing called Boost.stable_vector, but from the documentation I cannot=
 tell what makes it different from std::deque&lt;T&gt;. =C2=A0std::deque&lt=
;T&gt; has stability of references (if insertion is happening only at the f=
ront or back) and instability of iterators (unless insertion is happening o=
nly at the back, in practice, although I&#39;m not sure if you can count on=
 this).</div><div>Nicol, I know this is a tangent, but could you explain wh=
at&#39;s missing from std::deque&lt;T&gt; and how you&#39;d propose for a n=
ew container to fix it?</div><div><br></div><div><br></div><blockquote clas=
s=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #c=
cc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>I think the point the OP=
 is making is that applying these functions to non-random access containers=
 is a performance trap. It&#39;s a tool that is easier to use in inefficien=
t cases than it is to use in the most appropriate ones.<br></div><div><br>N=
ow, that being said, that point does apply to `std::list` as a whole. If we=
 had `stable_vector` (along with splice behavior, which the Boost type does=
n&#39;t have), `list` would find most of its valid use cases disappearing. =
That would make `list` something of a performance trap itself; something th=
at&#39;s seems like the right solution but isn&#39;t in most cases.<br><br>=
I don&#39;t necessarily agree with the OP&#39;s suggestion. But it would be=
 nice if there was some way to segregate these kinds of performance traps a=
way from regular types/functions. Like a special namespace for special-case=
 tools. `std::lower_bound` would only be available for random access iterat=
ors, but `std::corner::lower_bound` would be available for forward iterator=
s. That way, a user makes it clear that they&#39;re in a corner case.<br></=
div></div></blockquote><div><br></div><div>That&#39;s an interesting idea; =
but doesn&#39;t that completely break generic programming? =C2=A0Now anytim=
e I want to implement, let&#39;s say, my::equal_range() =E2=80=94 [Because =
I need an example of an algorithm that might plausibly depend on std::lower=
_bound(), let&#39;s pretend std::equal_range() doesn&#39;t exist.] =E2=80=
=94 I can&#39;t just write</div><div><br></div><div>auto equal_range(It fir=
st, It last, T value) {</div><div>=C2=A0 =C2=A0 auto it =3D std::lower_boun=
d(first, last, value);</div><div>=C2=A0 =C2=A0 auto jt =3D std::upper_bound=
(it, last, value);</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div><=
div>}</div><div><br></div><div>Instead I&#39;ll have to write... this?</div=
><div><br></div><div><div>auto equal_range(It first, It last, T value) {</d=
iv><div>=C2=A0 =C2=A0 auto it =3D std::corner::lower_bound(first, last, val=
ue);</div><div>=C2=A0 =C2=A0 auto jt =3D std::corner::upper_bound(it, last,=
 value);</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div><div>}</div=
></div><div><br></div><div>Or perhaps this?</div><div><br></div><div>// SFI=
NAE&#39;d for just the non-corner case</div><div><div>auto equal_range(It f=
irst, It last, T value, void_t&lt;decltype(std::lower_bound(first, last, va=
lue))&gt;* =3D nullptr) {</div><div>=C2=A0 =C2=A0 auto it =3D std::lower_bo=
und(first, last, value);</div><div>=C2=A0 =C2=A0 auto jt =3D std::upper_bou=
nd(it, last, value);</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div=
><div>}</div></div><div><br></div><div>// SFINAE&#39;d for the corner case =
=E2=80=94 does this overload belong in namespace my::corner now?</div><div>=
<div><div>auto equal_range(It first, It last, T value, void_t&lt;decltype(s=
td::corner::lower_bound(first, last, value))&gt;* =3D nullptr) {</div><div>=
=C2=A0 =C2=A0 auto it =3D std::corner::lower_bound(first, last, value);</di=
v><div>=C2=A0 =C2=A0 auto jt =3D std::corner::upper_bound(it, last, value);=
</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div><div>}</div></div><=
/div><div><br></div><div>It just seems like a lot of boilerplate for zero b=
enefit.</div><div><br></div><div>Meanwhile, it&#39;s easy (although not tri=
vial) for any STL vendor to <a href=3D"https://stackoverflow.com/questions/=
8936063/does-there-exist-a-static-warning">give a non-fatal diagnostic</a> =
on e.g. lower_bound of a BidirectionalIterator, if they really <i>wanted</i=
> to. =C2=A0There&#39;s definitely room for a clang-tidy check there, too. =
=C2=A0However, many knowledgeable people who <i>could</i> be working on tha=
t problem are <i>not</i> working on it, apparently because they have more i=
mportant things to do. =C2=A0If this problem is really important to OP, may=
be OP should work on it? :)</div><div><br></div><div>=E2=80=93Arthur</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/6d90b3ff-5129-44f2-9188-1e695b91703e%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/6d90b3ff-5129-44f2-9188-1e695b91703e=
%40isocpp.org</a>.<br />

------=_Part_4115_1947552013.1496186329258--

------=_Part_4114_236862562.1496186329257--

.

------=_Part_4127_1640639436.1496188805578
Content-Type: multipart/alternative;
 boundary="----=_Part_4128_384428520.1496188805578"

------=_Part_4128_384428520.1496188805578
Content-Type: text/plain; charset="UTF-8"



On Tuesday, May 30, 2017 at 6:52:58 PM UTC-4, Anthony Hall wrote:
>
> On Tuesday, May 30, 2017 at 1:12:58 PM UTC-6, Thiago Macieira wrote:
>>
>> On Tuesday, 30 May 2017 11:53:13 PDT Nicol Bolas wrote:
>> > > And that's exactly what QList is for most T and we're trying hard to
>> get
>> > > rid
>> > > of it...
>> >
>> > Well it's a bad thing when you *don't* want it. But that doesn't mean
>> it
>> > isn't a useful tool to have in your toolbox. `stable_vector` (which is
>> what
>> > we're talking about) is a good and useful class for certain situations.
>> >
>
>
>
>>
>> It also has a problem that it's schizophrenic and chooses whether to be a
>> vector or a stable_vector depending on the type T, so it may be good for
>> some
>> types of T, but not others. And that may vary per platform, because the
>> decision depends on the size of a pointer.
>>
>
> As for the awkward indirection semantics of vector<unique_ptr<T>>, I like
> the direction towards polymorphic value semantics that a number of people
> have been pushing towards, such as with Sean Parent's 'inheritance is the
> base class of evil', and various recent conversations in this reflector
> about automatic proxies from concepts, or 'runtime concepts' ideas.
>
> I've also seen recent libraries such as value_ptr (
> https://hackernoon.com/value-ptr-the-missing-c-smart-pointer-1f515664153e),
> which if I understand it, aims to give value semantics to
> freestore-allocated objects (which to me seems to be a sub-case of general
> pushes towards polymorphic value semantics).
>
> It seems to me that if all these general efforts towards polymorphic
> values could be unified and standardized, then vector<PolymorphicValue>
> would be preferable to having a whole new container type similar to vector.
>  (That is, assuming that polymorphic value semantics can solve all the use
> cases for the similar container types).  If polymorphic value semantics can
> be made composable with the existing STL, it could potentially solve the
> problem for the whole STL, not just vector<>, and might provide other more
> general solutions.
>

The point of a polymorphic value is to be *polymorphic*. The point of a
`stable_vector` is to be *stable*; it doesn't care about polymorphism with
regard to `T`, nor should it. `stable_vector<T>` would not hold things
derived from `T` or values that can have operations forwarded to look like
a `T`. It would store *actual* `T`'s, just like `vector<T>` stores actual
`T`s. It would not be able to adopt `T*`s allocated by the user, nor would
it be able to release ownership of `T*`s from the user.

`stable_vector` is not just a slightly fancy wrapper around
`vector<unique_ptr<T>>` or a `boost::ptr_vector<T>`. They may be
implemented in a similar way, but the interfaces are different.

--
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/0ad6ba08-a3e8-4e3f-ab22-4dc8b778ab0e%40isocpp.org.

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

<div dir=3D"ltr"><br><br>On Tuesday, May 30, 2017 at 6:52:58 PM UTC-4, Anth=
ony Hall wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-=
left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr=
">On Tuesday, May 30, 2017 at 1:12:58 PM UTC-6, Thiago Macieira wrote:<bloc=
kquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:=
1px solid rgb(204,204,204);padding-left:1ex">On Tuesday, 30 May 2017 11:53:=
13 PDT Nicol Bolas wrote:=C2=A0<br>&gt; &gt; And that&#39;s exactly what QL=
ist is for most T and we&#39;re trying hard to get=C2=A0<br>&gt; &gt; rid=
=C2=A0<br>&gt; &gt; of it...=C2=A0<br>&gt;=C2=A0<br>&gt; Well it&#39;s a ba=
d thing when you *don&#39;t* want it. But that doesn&#39;t mean it=C2=A0<br=
>&gt; isn&#39;t a useful tool to have in your toolbox. `stable_vector` (whi=
ch is what=C2=A0<br>&gt; we&#39;re talking about) is a good and useful clas=
s for certain situations.=C2=A0<br>&gt;</blockquote><div>=C2=A0</div><block=
quote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1=
px solid rgb(204,204,204);padding-left:1ex"><br>It also has a problem that =
it&#39;s schizophrenic and chooses whether to be a=C2=A0<br>vector or a sta=
ble_vector depending on the type T, so it may be good for some=C2=A0<br>typ=
es of T, but not others. And that may vary per platform, because the=C2=A0<=
br>decision depends on the size of a pointer.=C2=A0<br></blockquote><div>=
=C2=A0</div>As for the awkward indirection semantics of vector&lt;unique_pt=
r&lt;T&gt;&gt;, I like the direction towards polymorphic value semantics th=
at a number of people have been pushing towards, such as with Sean Parent&#=
39;s &#39;inheritance is the base class of evil&#39;, and various recent co=
nversations in this reflector about automatic proxies from concepts, or &#3=
9;runtime concepts&#39; ideas.<br><br>I&#39;ve also seen recent libraries s=
uch as value_ptr (<a href=3D"https://hackernoon.com/value-ptr-the-missing-c=
-smart-pointer-1f515664153e" target=3D"_blank" rel=3D"nofollow" onmousedown=
=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fhackerno=
on.com%2Fvalue-ptr-the-missing-c-smart-pointer-1f515664153e\x26sa\x3dD\x26s=
ntz\x3d1\x26usg\x3dAFQjCNEEBIgbBqCupXuFWwrtkpyuGypNiA&#39;;return true;" on=
click=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fhac=
kernoon.com%2Fvalue-ptr-the-missing-c-smart-pointer-1f515664153e\x26sa\x3dD=
\x26sntz\x3d1\x26usg\x3dAFQjCNEEBIgbBqCupXuFWwrtkpyuGypNiA&#39;;return true=
;">https://hackernoon.com/value-<wbr>ptr-the-missing-c-smart-<wbr>pointer-1=
f515664153e</a>), which if I understand it, aims to give value semantics to=
 freestore-allocated objects (which to me seems to be a sub-case of general=
 pushes towards polymorphic value semantics).<br><br>It seems to me that if=
 all these general efforts towards polymorphic values could be unified and =
standardized, then vector&lt;PolymorphicValue&gt; would be preferable to ha=
ving a whole new container type similar to vector. =C2=A0(That is, assuming=
 that polymorphic value semantics can solve all the use cases for the simil=
ar container types). =C2=A0If polymorphic value semantics can be made compo=
sable with the existing STL, it could potentially solve the problem for the=
 whole STL, not just vector&lt;&gt;, and might provide other more general s=
olutions.</div></blockquote><div><br>The point of a polymorphic value is to=
 be <i>polymorphic</i>. The point of a `stable_vector` is to be <i>stable</=
i>; it doesn&#39;t care about polymorphism with regard to `T`, nor should i=
t. `stable_vector&lt;T&gt;` would not hold things derived from `T` or value=
s that can have operations forwarded to look like a `T`. It would store <i>=
actual</i> `T`&#39;s, just like `vector&lt;T&gt;` stores actual `T`s. It wo=
uld not be able to adopt `T*`s allocated by the user, nor would it be able =
to release ownership of `T*`s from the user.<br><br>`stable_vector` is not =
just a slightly fancy wrapper around `vector&lt;unique_ptr&lt;T&gt;&gt;` or=
 a `boost::ptr_vector&lt;T&gt;`. They may be implemented in a similar way, =
but the interfaces are different.<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/0ad6ba08-a3e8-4e3f-ab22-4dc8b778ab0e%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/0ad6ba08-a3e8-4e3f-ab22-4dc8b778ab0e=
%40isocpp.org</a>.<br />

------=_Part_4128_384428520.1496188805578--

------=_Part_4127_1640639436.1496188805578--

.

------=_Part_3973_562602432.1496190448863
Content-Type: multipart/alternative;
 boundary="----=_Part_3974_1597145489.1496190448863"

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



On Tuesday, May 30, 2017 at 7:18:49 PM UTC-4, Arthur O'Dwyer wrote:
>
> On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:
>>
>> On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>>>
>>> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com> wrote:=
=20
>>> > Otherwise, following this same logic, we should also just remove=20
>>> std::list.  Because std::vector is almost always faster.=20
>>>
>>> I'm sure Howard is aware: the key advantage of std::list over=20
>>> std::vector isn't related to speed of operation. Instead, it is stabili=
ty=20
>>> of references and iterators to elements in the std::list.
>>
>>
>> Then can we get `stable_vector` standardized? It may not have stability=
=20
>> of iterators, but it does have stability of references. And that's good=
=20
>> enough for many cases.
>>
>
> I found a thing called Boost.stable_vector, but from the documentation I=
=20
> cannot tell what makes it different from std::deque<T>.
>
std::deque<T> has stability of references (if insertion is happening only=
=20
> at the front or back) and instability of iterators (unless insertion is=
=20
> happening only at the back, in practice, although I'm not sure if you can=
=20
> count on this).=20
>
Nicol, I know this is a tangent, but could you explain what's missing from=
=20
> std::deque<T> and how you'd propose for a new container to fix it?
>

Broadly speaking, `deque` has stability of references *and* iterators if=20
removal happens at either end. Well, obviously references and iterators of=
=20
the areas being removed are invalidated, but iterators and references to=20
other elements are fine. For insertion, references are never invalidated if=
=20
the insertion happens at either end. In all other operations, all=20
references and iterators are invalidated (again, broadly speaking. The=20
rules are very specific to the specific operations in question).

`stable_vector` has the same reference stability as `std::list`. That is,=
=20
references will never be invalidated by any insertion or removal operation=
=20
(again, unless you're talking about the removed elements). Iterator=20
invalidation would work like `vector`.

So `stable_vector` effectively fills the niche of `list` users who need=20
stability of references, but *not* stability of iteration. The object needs=
=20
to always be around (until it is directly removed), but the user doesn't=20
need to be able to maintain the power to iterate from one item to another.

Basically, `stable_vector` is a lot more like `list` than `deque`. It has=
=20
the ability to have fast iterator swapping like `list`, it can have=20
`list`'s splicing behavior (though not the iterator rules under splicing),=
=20
and so forth. But it is random access rather than bidirectional, so for=20
algorithms like `lower_bound`, you can get good performance.

Implementation-wise, `stable_vector<T>` is just a `vector<unique_ptr<T>>`,=
=20
except that it allocates actual `T`s when you insert items, and it returns=
=20
`T&` rather than `T*` or ` unique_ptr<T>&` from its iterators.

I think the point the OP is making is that applying these functions to=20
>> non-random access containers is a performance trap. It's a tool that is=
=20
>> easier to use in inefficient cases than it is to use in the most=20
>> appropriate ones.
>>
>> Now, that being said, that point does apply to `std::list` as a whole. I=
f=20
>> we had `stable_vector` (along with splice behavior, which the Boost type=
=20
>> doesn't have), `list` would find most of its valid use cases disappearin=
g.=20
>> That would make `list` something of a performance trap itself; something=
=20
>> that's seems like the right solution but isn't in most cases.
>>
>> I don't necessarily agree with the OP's suggestion. But it would be nice=
=20
>> if there was some way to segregate these kinds of performance traps away=
=20
>> from regular types/functions. Like a special namespace for special-case=
=20
>> tools. `std::lower_bound` would only be available for random access=20
>> iterators, but `std::corner::lower_bound` would be available for forward=
=20
>> iterators. That way, a user makes it clear that they're in a corner case=
..
>>
>
> That's an interesting idea; but doesn't that completely break generic=20
> programming?  Now anytime I want to implement, let's say, my::equal_range=
()=20
> =E2=80=94 [Because I need an example of an algorithm that might plausibly=
 depend on=20
> std::lower_bound(), let's pretend std::equal_range() doesn't exist.] =E2=
=80=94 I=20
> can't just write
>
> auto equal_range(It first, It last, T value) {
>     auto it =3D std::lower_bound(first, last, value);
>     auto jt =3D std::upper_bound(it, last, value);
>     return std::pair{it, jt};
> }
>
> Instead I'll have to write... this?
>
> auto equal_range(It first, It last, T value) {
>     auto it =3D std::corner::lower_bound(first, last, value);
>     auto jt =3D std::corner::upper_bound(it, last, value);
>     return std::pair{it, jt};
> }
>

We're talking about things in terms of a Ranges TS implementation. So we=20
have Concepts, as well as the Ranges concept definitions.

So the question is this: what concept do you want those iterators to=20
implement? Does `my::equal_range` need to handle all forward iterators, or=
=20
is just random-access iterators good enough?

This is the same question you'd have when deciding whether to call=20
`lower_bound` or `corner::lower_bound`.

Or perhaps this?
>
> // SFINAE'd for just the non-corner case
> auto equal_range(It first, It last, T value,=20
> void_t<decltype(std::lower_bound(first, last, value))>* =3D nullptr) {
>     auto it =3D std::lower_bound(first, last, value);
>     auto jt =3D std::upper_bound(it, last, value);
>     return std::pair{it, jt};
> }
>
> // SFINAE'd for the corner case =E2=80=94 does this overload belong in na=
mespace=20
> my::corner now?
> auto equal_range(It first, It last, T value,=20
> void_t<decltype(std::corner::lower_bound(first, last, value))>* =3D nullp=
tr) {
>     auto it =3D std::corner::lower_bound(first, last, value);
>     auto jt =3D std::corner::upper_bound(it, last, value);
>     return std::pair{it, jt};
> }
>
> It just seems like a lot of boilerplate for zero benefit.
>
> Meanwhile, it's easy (although not trivial) for any STL vendor to give a=
=20
> non-fatal diagnostic=20
> <https://stackoverflow.com/questions/8936063/does-there-exist-a-static-wa=
rning>=20
> on e.g. lower_bound of a BidirectionalIterator, if they really *wanted*=
=20
> to.
>

So how would you turn it off when you actually meant to use it?

There's definitely room for a clang-tidy check there, too.  However, many=
=20
> knowledgeable people who *could* be working on that problem are *not*=20
> working on it, apparently because they have more important things to do.=
=20
>  If this problem is really important to OP, maybe OP should work on it? :=
)
>

--=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/aa702074-dd2c-4123-a83a-16feebb474e9%40isocpp.or=
g.

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

<div dir=3D"ltr"><br><br>On Tuesday, May 30, 2017 at 7:18:49 PM UTC-4, Arth=
ur O&#39;Dwyer wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:<bl=
ockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-l=
eft:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monday, May 29, 20=
17 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:<blockquote class=3D"gmail_=
quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;paddi=
ng-left:1ex">On 29 May 2017, at 21:47, Howard Hinnant &lt;<a rel=3D"nofollo=
w">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list. =C2=A0Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br></div></div></blockquote><div><br></div><div>I fo=
und a thing called Boost.stable_vector, but from the documentation I cannot=
 tell what makes it different from std::deque&lt;T&gt;.</div></div></blockq=
uote><div></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin=
-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"lt=
r"><div>std::deque&lt;T&gt; has stability of references (if insertion is ha=
ppening only at the front or back) and instability of iterators (unless ins=
ertion is happening only at the back, in practice, although I&#39;m not sur=
e if you can count on this).=C2=A0</div></div></blockquote><blockquote clas=
s=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #c=
cc solid;padding-left: 1ex;"><div dir=3D"ltr"><div>Nicol, I know this is a =
tangent, but could you explain what&#39;s missing from std::deque&lt;T&gt; =
and how you&#39;d propose for a new container to fix it?</div></div></block=
quote><div><br>Broadly speaking, `deque` has stability of references <i>and=
</i> iterators if removal happens at either end. Well, obviously references=
 and=20
iterators of the areas being removed are invalidated, but iterators and=20
references to other elements are fine. For insertion, references are never =
invalidated if the insertion happens at either end. In all other operations=
, all references and iterators are invalidated (again, broadly speaking. Th=
e rules are very specific to the specific operations in question).<br><br>`=
stable_vector` has the same reference stability as `std::list`. That is, re=
ferences will never be invalidated by any insertion or removal operation (a=
gain, unless you&#39;re talking about the removed elements). Iterator inval=
idation would work like `vector`.<br><br>So `stable_vector` effectively fil=
ls the niche of `list` users who need stability of references, but <i>not</=
i> stability of iteration. The object needs to always be around (until it i=
s directly removed), but the user doesn&#39;t need to be able to maintain t=
he power to iterate from one item to another.<br><br>Basically, `stable_vec=
tor` is a lot more like `list` than `deque`. It has the ability to have fas=
t iterator swapping like `list`, it can have `list`&#39;s splicing behavior=
 (though not the iterator rules under splicing), and so forth. But it is ra=
ndom access rather than bidirectional, so for algorithms like `lower_bound`=
, you can get good performance.<br><br>Implementation-wise, `stable_vector&=
lt;T&gt;` is just a=20
`vector&lt;unique_ptr&lt;T&gt;&gt;`, except that it allocates actual=20
`T`s when you insert items, and it returns `T&amp;` rather than `T*` or `
 unique_ptr&lt;T&gt;&amp;` from its iterators.<br><br></div><blockquote cla=
ss=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #=
ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div dir=3D"ltr"><div>I think the point the OP is ma=
king is that applying these functions to non-random access containers is a =
performance trap. It&#39;s a tool that is easier to use in inefficient case=
s than it is to use in the most appropriate ones.<br></div><div><br>Now, th=
at being said, that point does apply to `std::list` as a whole. If we had `=
stable_vector` (along with splice behavior, which the Boost type doesn&#39;=
t have), `list` would find most of its valid use cases disappearing. That w=
ould make `list` something of a performance trap itself; something that&#39=
;s seems like the right solution but isn&#39;t in most cases.<br><br>I don&=
#39;t necessarily agree with the OP&#39;s suggestion. But it would be nice =
if there was some way to segregate these kinds of performance traps away fr=
om regular types/functions. Like a special namespace for special-case tools=
.. `std::lower_bound` would only be available for random access iterators, b=
ut `std::corner::lower_bound` would be available for forward iterators. Tha=
t way, a user makes it clear that they&#39;re in a corner case.<br></div></=
div></blockquote><div><br></div><div>That&#39;s an interesting idea; but do=
esn&#39;t that completely break generic programming? =C2=A0Now anytime I wa=
nt to implement, let&#39;s say, my::equal_range() =E2=80=94 [Because I need=
 an example of an algorithm that might plausibly depend on std::lower_bound=
(), let&#39;s pretend std::equal_range() doesn&#39;t exist.] =E2=80=94 I ca=
n&#39;t just write</div><div><br></div><div>auto equal_range(It first, It l=
ast, T value) {</div><div>=C2=A0 =C2=A0 auto it =3D std::lower_bound(first,=
 last, value);</div><div>=C2=A0 =C2=A0 auto jt =3D std::upper_bound(it, las=
t, value);</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div><div>}</d=
iv><div><br></div><div>Instead I&#39;ll have to write... this?</div><div><b=
r></div><div><div>auto equal_range(It first, It last, T value) {</div><div>=
=C2=A0 =C2=A0 auto it =3D std::corner::lower_bound(<wbr>first, last, value)=
;</div><div>=C2=A0 =C2=A0 auto jt =3D std::corner::upper_bound(it, last, va=
lue);</div><div>=C2=A0 =C2=A0 return std::pair{it, jt};</div><div>}</div></=
div></div></blockquote><div><br>We&#39;re talking about things in terms of =
a Ranges TS implementation. So we have Concepts, as well as the Ranges conc=
ept definitions.<br><br>So the question is this: what concept do you want t=
hose iterators to implement? Does `my::equal_range` need to handle all forw=
ard iterators, or is just random-access iterators good enough?<br><br>This =
is the same question you&#39;d have when deciding whether to call `lower_bo=
und` or `corner::lower_bound`.<br><br></div><blockquote class=3D"gmail_quot=
e" style=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;paddin=
g-left: 1ex;"><div dir=3D"ltr"><div></div><div>Or perhaps this?</div><div><=
br></div><div>// SFINAE&#39;d for just the non-corner case</div><div><div>a=
uto equal_range(It first, It last, T value, void_t&lt;decltype(std::lower_<=
wbr>bound(first, last, value))&gt;* =3D nullptr) {</div><div>=C2=A0 =C2=A0 =
auto it =3D std::lower_bound(first, last, value);</div><div>=C2=A0 =C2=A0 a=
uto jt =3D std::upper_bound(it, last, value);</div><div>=C2=A0 =C2=A0 retur=
n std::pair{it, jt};</div><div>}</div></div><div><br></div><div>// SFINAE&#=
39;d for the corner case =E2=80=94 does this overload belong in namespace m=
y::corner now?</div><div><div><div>auto equal_range(It first, It last, T va=
lue, void_t&lt;decltype(std::corner::<wbr>lower_bound(first, last, value))&=
gt;* =3D nullptr) {</div><div>=C2=A0 =C2=A0 auto it =3D std::corner::lower_=
bound(<wbr>first, last, value);</div><div>=C2=A0 =C2=A0 auto jt =3D std::co=
rner::upper_bound(it, last, value);</div><div>=C2=A0 =C2=A0 return std::pai=
r{it, jt};</div><div>}</div></div></div><div><br></div><div>It just seems l=
ike a lot of boilerplate for zero benefit.</div><div><br></div><div>Meanwhi=
le, it&#39;s easy (although not trivial) for any STL vendor to <a href=3D"h=
ttps://stackoverflow.com/questions/8936063/does-there-exist-a-static-warnin=
g" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;https=
://www.google.com/url?q\x3dhttps%3A%2F%2Fstackoverflow.com%2Fquestions%2F89=
36063%2Fdoes-there-exist-a-static-warning\x26sa\x3dD\x26sntz\x3d1\x26usg\x3=
dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return true;" onclick=3D"this.href=
=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fstackoverflow.com%2Fq=
uestions%2F8936063%2Fdoes-there-exist-a-static-warning\x26sa\x3dD\x26sntz\x=
3d1\x26usg\x3dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return true;">give a =
non-fatal diagnostic</a> on e.g. lower_bound of a BidirectionalIterator, if=
 they really <i>wanted</i> to.</div></div></blockquote><div><br>So how woul=
d you turn it off when you actually meant to use it?<br><br></div><blockquo=
te class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left:=
 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div> There&#39;s defi=
nitely room for a clang-tidy check there, too. =C2=A0However, many knowledg=
eable people who <i>could</i> be working on that problem are <i>not</i> wor=
king on it, apparently because they have more important things to do. =C2=
=A0If this problem is really important to OP, maybe OP should work on it? :=
)</div></div></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/aa702074-dd2c-4123-a83a-16feebb474e9%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/aa702074-dd2c-4123-a83a-16feebb474e9=
%40isocpp.org</a>.<br />

------=_Part_3974_1597145489.1496190448863--

------=_Part_3973_562602432.1496190448863--

.

On Tuesday, 30 May 2017 17:27:28 PDT Nicol Bolas wrote:
> So `stable_vector` effectively fills the niche of `list` users who need
> stability of references, but *not* stability of iteration. The object needs
> to always be around (until it is directly removed), but the user doesn't
> need to be able to maintain the power to iterate from one item to another.

And it has O(1) random access search time, even though it does O(n)
allocations like std::list.

--
Thiago Macieira - thiago (AT) macieira.info - thiago (AT) kde.org
   Software Architect - Intel Open Source Technology Center

--
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/3734681.f2vzkCiB4r%40tjmaciei-mobl1.

.

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

On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <jmckesson@gmail.com> wrote:

> On Tuesday, May 30, 2017 at 7:18:49 PM UTC-4, Arthur O'Dwyer wrote:
>>
>> On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:
>>>
>>> On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>>>>
>>>> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com> wrote:
>>>> > Otherwise, following this same logic, we should also just remove
>>>> std::list.  Because std::vector is almost always faster.
>>>>
>>>> I'm sure Howard is aware: the key advantage of std::list over
>>>> std::vector isn't related to speed of operation. Instead, it is stabil=
ity
>>>> of references and iterators to elements in the std::list.
>>>
>>>
>>> Then can we get `stable_vector` standardized? It may not have stability
>>> of iterators, but it does have stability of references. And that's good
>>> enough for many cases.
>>>
>>
>> I found a thing called Boost.stable_vector, but from the documentation I
>> cannot tell what makes it different from std::deque<T>.
>>
> std::deque<T> has stability of references (if insertion is happening only
>> at the front or back) and instability of iterators (unless insertion is
>> happening only at the back, in practice, although I'm not sure if you ca=
n
>> count on this).
>>
> Nicol, I know this is a tangent, but could you explain what's missing fro=
m
>> std::deque<T> and how you'd propose for a new container to fix it?
>>
>
> Broadly speaking, `deque` has stability of references *and* iterators if
> removal happens at either end. Well, obviously references and iterators o=
f
> the areas being removed are invalidated, but iterators and references to
> other elements are fine. For insertion, references are never invalidated =
if
> the insertion happens at either end. In all other operations, all
> references and iterators are invalidated (again, broadly speaking. The
> rules are very specific to the specific operations in question).
>
> `stable_vector` has the same reference stability as `std::list`. That is,
> references will never be invalidated by any insertion or removal operatio=
n
> (again, unless you're talking about the removed elements). Iterator
> invalidation would work like `vector`.
>
> So `stable_vector` effectively fills the niche of `list` users who need
> stability of references, but *not* stability of iteration.
> [...]
> Implementation-wise, `stable_vector<T>` is just a `vector<unique_ptr<T>>`=
,
> except that it allocates actual `T`s when you insert items, and it return=
s
> `T&` rather than `T*` or ` unique_ptr<T>&` from its iterators.
>

So the use-case is "I want to insert in the middle of this very long
sequence, and also random-access it."  I suppose that's a reasonable set of
requirements if you have a really long sequence that you're trying to keep
sorted =E2=80=94 basically flat_set.
Oh =E2=80=94 except that insertion in the middle is still O(N) because you =
have to
shuffle all those pointers, right? It's O(1) in "moves of T objects" but
O(N) in "moves of unique_ptr<T> objects."  So the use-case isn't even "a
really long sequence"; it's got to be "a long sequence of some really
expensive-to-move T", which I think is less plausible these days. The only
use-case I can immediately think of is if T is actually immobile, like a
mutex or something; but then this sounds like a really niche use-case and
I'd think the programmer should just suck it up and use
vector<unique_ptr<T>>.

Certainly "stable_vector" is a bad name for this thing if its elements are
not contiguous. Contiguity is the number-one defining characteristic of a
"vector", in my book.

I also notice that this container is exactly congruent to a std::deque<T>
with a block size of 1.  (Typical block sizes in libc++ and libstdc++ are
between 16 to 4096 depending on sizeof(T), and are not configurable by the
programmer. But if they were configurable via a template parameter or
something, bam! Problem solved. This suggests to me that a better name
might be "std::small_block_deque<T, 1>".)


I don't necessarily agree with the OP's suggestion. But it would be nice if
>>> there was some way to segregate these kinds of performance traps away f=
rom
>>> regular types/functions. Like a special namespace for special-case tool=
s.
>>> `std::lower_bound` would only be available for random access iterators,=
 but
>>> `std::corner::lower_bound` would be available for forward iterators. Th=
at
>>> way, a user makes it clear that they're in a corner case.
>>>
>>
>> That's an interesting idea; but doesn't that completely break generic
>> programming?  Now anytime I want to implement, let's say, my::equal_rang=
e()
>> =E2=80=94 [Because I need an example of an algorithm that might plausibl=
y depend on
>> std::lower_bound(), let's pretend std::equal_range() doesn't exist.] =E2=
=80=94 I
>> can't just write [...]
>>
>

> We're talking about things in terms of a Ranges TS implementation. So we
> have Concepts, as well as the Ranges concept definitions.
>
> So the question is this: what concept do you want those iterators to
> implement? Does `my::equal_range` need to handle all forward iterators, o=
r
> is just random-access iterators good enough?
>
> This is the same question you'd have when deciding whether to call
> `lower_bound` or `corner::lower_bound`.
>

Right. And the status quo is that I don't even need to think about it; both
my generic-programmed `equal_range` and the standard's generic-programmed
`lower_bound` work naturally with all kinds of iterators, as long as those
iterators support the necessary operations =E2=80=94 which is to say `std::=
advance`
and copying =E2=80=94 which is to say, as long as they model the ForwardIte=
rator
concept. This makes perfect sense to me.

So the question is, what would we gain by splitting up std::lower_bound
into a new `lower_bound` that is artificially constrained to work only with
RandomAccessIterators and a new `corner::lower_bound` that is equivalent to
the `lower_bound` we have today?  I contend that the answer is "nothing
except we might have to go add `corner::` to some generic code that used to
work, so that it will work again."  That's what I mean by "a lot of
boilerplate for zero benefit."


Meanwhile, it's easy (although not trivial) for any STL vendor to give a
>> non-fatal diagnostic
>> <https://stackoverflow.com/questions/8936063/does-there-exist-a-static-w=
arning>
>> on e.g. lower_bound of a BidirectionalIterator, if they really *wanted*
>> to.
>>
>
> So how would you turn it off when you actually meant to use it?
>

The same way you turn off vendor-provided STL extensions today. For
example, Visual Studio's STL ships with "checked iterators" which you can
turn off by fiddling with the macro _ITERATOR_DEBUG_LEVEL
<https://docs.microsoft.com/en-us/cpp/standard-library/iterator-debug-level=
>.
In libstdc++, a similar feature is controlled with _GLIBCXX_DEBUG
<https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_using.html#debu=
g_mode.using.mode>
..
Ah, but you mean, what if I have a program where I know that *one* piece of
it (and suppose it's in a .h file included everywhere) needs the current
`lower_bound`, but everywhere *else* in the program I'd like to get a
warning if I use `lower_bound` with anything other than a
RandomAccessIterator?  ...Well, that's harder. I suspect it's doable, but
only by fiddling with something in the vicinity of the offending usage
itself.  Your suggestion boils down to "The vendor could provide a back
door via std::corner::lower_bound." The vendor could also provide a back
door via a #pragma or something else cleverer than I'm currently thinking
of.  I dunno, I guess it comes down to how much effort we want to put into
breaking-and-then-fixing old code as opposed to just letting it keep
working as is. ;)

=E2=80=93Arthur

--=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/CADvuK0J8mbsc-mL7cSKa62gGfsov5cQTJ4As8emM51qKyMv=
MaA%40mail.gmail.com.

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

<div dir=3D"ltr">On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <span dir=3D"=
ltr">&lt;<a href=3D"mailto:jmckesson@gmail.com" target=3D"_blank">jmckesson=
@gmail.com</a>&gt;</span> wrote:<br><div class=3D"gmail_extra"><div class=
=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Tuesday=
, May 30, 2017 at 7:18:49 PM UTC-4, Arthur O&#39;Dwyer wrote:<blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #cc=
c solid;padding-left:1ex"><div dir=3D"ltr">On Monday, May 29, 2017 at 2:52:=
18 PM UTC-7, Nicol Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"m=
argin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div=
 dir=3D"ltr">On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl=
 wrote:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8e=
x;border-left:1px #ccc solid;padding-left:1ex">On 29 May 2017, at 21:47, Ho=
ward Hinnant &lt;<a rel=3D"nofollow">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list.=C2=A0 Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br></div></div></blockquote><div><br></div><div>I fo=
und a thing called Boost.stable_vector, but from the documentation I cannot=
 tell what makes it different from std::deque&lt;T&gt;.</div></div></blockq=
uote><div></div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-=
left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><d=
iv>std::deque&lt;T&gt; has stability of references (if insertion is happeni=
ng only at the front or back) and instability of iterators (unless insertio=
n is happening only at the back, in practice, although I&#39;m not sure if =
you can count on this).=C2=A0</div></div></blockquote><blockquote class=3D"=
gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr"><div>Nicol, I know this is a tangent, b=
ut could you explain what&#39;s missing from std::deque&lt;T&gt; and how yo=
u&#39;d propose for a new container to fix it?</div></div></blockquote><div=
><br>Broadly speaking, `deque` has stability of references <i>and</i> itera=
tors if removal happens at either end. Well, obviously references and=20
iterators of the areas being removed are invalidated, but iterators and=20
references to other elements are fine. For insertion, references are never =
invalidated if the insertion happens at either end. In all other operations=
, all references and iterators are invalidated (again, broadly speaking. Th=
e rules are very specific to the specific operations in question).<br><br>`=
stable_vector` has the same reference stability as `std::list`. That is, re=
ferences will never be invalidated by any insertion or removal operation (a=
gain, unless you&#39;re talking about the removed elements). Iterator inval=
idation would work like `vector`.<br><br>So `stable_vector` effectively fil=
ls the niche of `list` users who need stability of references, but <i>not</=
i> stability of iteration.<br>[...]<br>Implementation-wise, `stable_vector&=
lt;T&gt;` is just a=20
`vector&lt;unique_ptr&lt;T&gt;&gt;`, except that it allocates actual=20
`T`s when you insert items, and it returns `T&amp;` rather than `T*` or `
 unique_ptr&lt;T&gt;&amp;` from its iterators.<br></div></div></blockquote>=
<div><br></div><div>So the use-case is &quot;I want to insert in the middle=
 of this very long sequence, and also random-access it.&quot; =C2=A0I suppo=
se that&#39;s a reasonable set of requirements if you have a really long se=
quence that you&#39;re trying to keep sorted =E2=80=94 basically flat_set.<=
/div><div>Oh =E2=80=94 except that insertion in the middle is still O(N) be=
cause you have to shuffle all those pointers, right? It&#39;s O(1) in &quot=
;moves of T objects&quot; but O(N) in &quot;moves of unique_ptr&lt;T&gt; ob=
jects.&quot; =C2=A0So the use-case isn&#39;t even &quot;a really long seque=
nce&quot;; it&#39;s got to be &quot;a long sequence of some really expensiv=
e-to-move T&quot;, which I think is less plausible these days. The only use=
-case I can immediately think of is if T is actually immobile, like a mutex=
 or something; but then this sounds like a really niche use-case and I&#39;=
d think the programmer should just suck it up and use vector&lt;unique_ptr&=
lt;T&gt;&gt;.</div><div><br></div><div>Certainly &quot;stable_vector&quot; =
is a bad name for this thing if its elements are not contiguous. Contiguity=
 is the number-one defining characteristic of a &quot;vector&quot;, in my b=
ook.</div><div><br></div><div>I also notice that this container is exactly =
congruent to a std::deque&lt;T&gt; with a block size of 1. =C2=A0(Typical b=
lock sizes in libc++ and libstdc++ are between 16 to 4096 depending on size=
of(T), and are not configurable by the programmer. But if they were configu=
rable via a template parameter or something, bam! Problem solved. This sugg=
ests to me that a better name might be &quot;std::small_block_deque&lt;T, 1=
&gt;&quot;.)</div><div><br></div><div><br></div><blockquote class=3D"gmail_=
quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1=
ex"><div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;ma=
rgin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"lt=
r"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>I don&#39;=
t necessarily agree with the OP&#39;s suggestion. But it would be nice if t=
here was some way to segregate these kinds of performance traps away from r=
egular types/functions. Like a special namespace for special-case tools. `s=
td::lower_bound` would only be available for random access iterators, but `=
std::corner::lower_bound` would be available for forward iterators. That wa=
y, a user makes it clear that they&#39;re in a corner case.<br></div></div>=
</blockquote><div><br></div><div>That&#39;s an interesting idea; but doesn&=
#39;t that completely break generic programming?=C2=A0 Now anytime I want t=
o implement, let&#39;s say, my::equal_range() =E2=80=94 [Because I need an =
example of an algorithm that might plausibly depend on std::lower_bound(), =
let&#39;s pretend std::equal_range() doesn&#39;t exist.] =E2=80=94 I can&#3=
9;t just write [...]</div></div></blockquote><div></div></div></blockquote>=
<div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8=
ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>We&#3=
9;re talking about things in terms of a Ranges TS implementation. So we hav=
e Concepts, as well as the Ranges concept definitions.<br><br>So the questi=
on is this: what concept do you want those iterators to implement? Does `my=
::equal_range` need to handle all forward iterators, or is just random-acce=
ss iterators good enough?<br><br>This is the same question you&#39;d have w=
hen deciding whether to call `lower_bound` or `corner::lower_bound`.<br></d=
iv></div></blockquote><div><br></div><div>Right. And the status quo is that=
 I don&#39;t even need to think about it; both my generic-programmed `equal=
_range` and the standard&#39;s generic-programmed `lower_bound` work natura=
lly with all kinds of iterators, as long as those iterators support the nec=
essary operations =E2=80=94 which is to say `std::advance` and copying =E2=
=80=94 which is to say, as long as they model the ForwardIterator concept. =
This makes perfect sense to me.</div><div><br></div><div>So the question is=
, what would we gain by splitting up std::lower_bound into a new `lower_bou=
nd` that is artificially constrained to work only with RandomAccessIterator=
s and a new `corner::lower_bound` that is equivalent to the `lower_bound` w=
e have today?=C2=A0 I contend that the answer is &quot;nothing except we mi=
ght have to go add `corner::` to some generic code that used to work, so th=
at it will work again.&quot; =C2=A0That&#39;s what I mean by &quot;a lot of=
 boilerplate for zero benefit.&quot;</div><div><br></div><div><br></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"><blockquote class=3D"gmail_quo=
te" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-=
left:1ex"><div dir=3D"ltr"><div>Meanwhile, it&#39;s easy (although not triv=
ial) for any STL vendor to <a href=3D"https://stackoverflow.com/questions/8=
936063/does-there-exist-a-static-warning" rel=3D"nofollow" target=3D"_blank=
">give a non-fatal diagnostic</a> on e.g. lower_bound of a BidirectionalIte=
rator, if they really <i>wanted</i> to.<br></div></div></blockquote><div><b=
r>So how would you turn it off when you actually meant to use it?<br></div>=
</div></blockquote><div><br></div><div>The same way you turn off vendor-pro=
vided STL extensions today. For example, Visual Studio&#39;s STL ships with=
 &quot;checked iterators&quot; which you can turn off by fiddling with the =
macro=C2=A0<a href=3D"https://docs.microsoft.com/en-us/cpp/standard-library=
/iterator-debug-level">_ITERATOR_DEBUG_LEVEL</a>.=C2=A0 In libstdc++, a sim=
ilar feature is controlled with <a href=3D"https://gcc.gnu.org/onlinedocs/l=
ibstdc++/manual/debug_mode_using.html#debug_mode.using.mode">_GLIBCXX_DEBUG=
</a>.</div><div>Ah, but you mean, what if I have a program where I know tha=
t=C2=A0<i>one</i> piece of it (and suppose it&#39;s in a .h file included e=
verywhere) needs the current `lower_bound`, but everywhere <i>else</i> in t=
he program I&#39;d like to get a warning if I use `lower_bound` with anythi=
ng other than a RandomAccessIterator? =C2=A0...Well, that&#39;s harder. I s=
uspect it&#39;s doable, but only by fiddling with something in the vicinity=
 of the offending usage itself.=C2=A0 Your suggestion boils down to &quot;T=
he vendor could provide a back door via std::corner::lower_bound.&quot; The=
 vendor could also provide a back door via a #pragma or something else clev=
erer than I&#39;m currently thinking of.=C2=A0 I dunno, I guess it comes do=
wn to how much effort we want to put into breaking-and-then-fixing old code=
 as opposed to just letting it keep working as is. ;)</div><div><br></div><=
div>=E2=80=93Arthur</div></div></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/CADvuK0J8mbsc-mL7cSKa62gGfsov5cQTJ4As=
8emM51qKyMvMaA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">htt=
ps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CADvuK0J8mbsc-mL7=
cSKa62gGfsov5cQTJ4As8emM51qKyMvMaA%40mail.gmail.com</a>.<br />

--f403045c0ca2bbf9a30550c93065--

.

On 2017-05-30 15:12, Thiago Macieira wrote:
> [QList] also has a problem that it's schizophrenic and chooses
> whether to be a vector or a stable_vector depending on the type T, so
> it may be good for some types of T, but not others. And that may vary
> per platform, because the decision depends on the size of a pointer.
>
> There's a discussion on what to do for Qt 6. We'll probably keep the
> "stable vector" functionality, just under a different name and
> without the selection.
Indeed, and note that in my previous message, I didn't say anything
about the class having "magical" change of behavior based on sizeof(T).

On 2017-05-30 20:00, Nicol Bolas wrote:
> It would store *actual* `T`'s, just like `vector<T>` stores actual
> `T`s. It would not be able to adopt `T*`s allocated by the user, nor
> would it be able to release ownership of `T*`s from the user.>
> `stable_vector` is not just a slightly fancy wrapper around
> `vector<unique_ptr<T>>` or a `boost::ptr_vector<T>`. They may be
> implemented in a similar way, but the interfaces are different.
Pedantically, though, a vector<unique_ptr<T>> *could* store a T*
allocated by the user, whereas I guess a stable_vector<T> would "lose"
that functionality. (But that may not be a bad thing; if you *need*
that, the extra indirection of vector<unique_ptr<T>> may help to remind
you that you might be dealing with polymorphic types...)

--
Matthew

--
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/a0c28b95-214e-82c4-a2bf-72b70427a12c%40gmail.com.

.

On 31/05/2017 16:22, Matthew Woehlke wrote:
> Pedantically, though, a vector<unique_ptr<T>> *could* store a T*
> allocated by the user, whereas I guess a stable_vector<T> would "lose"
> that functionality. (But that may not be a bad thing; if you *need*
> that, the extra indirection of vector<unique_ptr<T>> may help to remind
> you that you might be dealing with polymorphic types...)

If you need polymorphic storage, then maybe the recently accepted
Boost.PolyCollection is what you need:

https://github.com/joaquintides/poly_collection

Best,

Ion


--
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/bd19033b-cd54-736a-842e-b3cad5c52877%40gmail.com.

.

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

>
> On 31/05/2017 16:22, Matthew Woehlke wrote:
>
>> Pedantically, though, a vector<unique_ptr<T>> *could* store a T*
>> allocated by the user, whereas I guess a stable_vector<T> would "lose"
>> that functionality. (But that may not be a bad thing; if you *need*
>> that, the extra indirection of vector<unique_ptr<T>> may help to remind
>> you that you might be dealing with polymorphic types...)
>>
>
> If you need polymorphic storage, then maybe the recently accepted
> Boost.PolyCollection is what you need:
>
> https://github.com/joaquintides/poly_collection
>
> Best,
>
> Ion


Actually, what I was getting at (as a side point not really germane to the
discussion about stable_vector) is that I wonder if things such as
Boost.PolyCollection would be unnecessary if we had polymorphic value
semantics: if in that case we could just use the STL containers
parameterized by polymorphic value types, without needing the usual
reference semantics required for polymorphism.  It seem like it could save
the extra work and complexity of creating new kinds of containers if
polymorphic value semantics were added in a way that compose well with
existing language and standard library facilities.

-Andy

--
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/CAApgN5-%2BpUKR__dji_FzhhxgCCCejvyPGTRwo8DBbaFk6A8GeA%40mail.gmail.com.

--001a11410fbe320a8a0550d91c21
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"><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c=
cc solid;padding-left:1ex"><span class=3D"">On 31/05/2017 16:22, Matthew Wo=
ehlke wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Pedantically, though, a vector&lt;unique_ptr&lt;T&gt;&gt; *could* store a T=
*<br>
allocated by the user, whereas I guess a stable_vector&lt;T&gt; would &quot=
;lose&quot;<br>
that functionality. (But that may not be a bad thing; if you *need*<br>
that, the extra indirection of vector&lt;unique_ptr&lt;T&gt;&gt; may help t=
o remind<br>
you that you might be dealing with polymorphic types...)<br>
</blockquote>
<br></span>
If you need polymorphic storage, then maybe the recently accepted Boost.Pol=
yCollection is what you need:<br>
<br>
<a href=3D"https://github.com/joaquintides/poly_collection" rel=3D"noreferr=
er" target=3D"_blank">https://github.com/joaquintide<wbr>s/poly_collection<=
/a><br>
<br>
Best,<br>
<br>
Ion</blockquote><div>=C2=A0</div><div>Actually, what I was getting at (as a=
 side point not really germane to the discussion about stable_vector) is th=
at I wonder if things such as Boost.PolyCollection would be unnecessary if =
we had polymorphic value semantics: if in that case we could just use the S=
TL containers parameterized by polymorphic value types, without needing the=
 usual reference semantics required for polymorphism.=C2=A0 It seem like it=
 could save the extra work and complexity of creating new kinds of containe=
rs if polymorphic value semantics were added in a way that compose well wit=
h existing language and standard library facilities.</div><div><br></div><d=
iv>-Andy</div></div></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/CAApgN5-%2BpUKR__dji_FzhhxgCCCejvyPGT=
Rwo8DBbaFk6A8GeA%40mail.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">h=
ttps://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAApgN5-%2BpUKR=
__dji_FzhhxgCCCejvyPGTRwo8DBbaFk6A8GeA%40mail.gmail.com</a>.<br />

--001a11410fbe320a8a0550d91c21--

.

--Apple-Mail-677D1862-7BD8-4E76-BA19-F8DA824E915D
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

polymorphic_value is making progress through the C++ standards committee.

Latest draft paper and reference implementation are available here:
https://github.com/jbcoe/polymorphic_value

On 31 May 2017, at 23:04, Anthony Hall <anthrond@gmail.com> wrote:

>> On 31/05/2017 16:22, Matthew Woehlke wrote:
>>> Pedantically, though, a vector<unique_ptr<T>> *could* store a T*
>>> allocated by the user, whereas I guess a stable_vector<T> would "lose"
>>> that functionality. (But that may not be a bad thing; if you *need*
>>> that, the extra indirection of vector<unique_ptr<T>> may help to remind
>>> you that you might be dealing with polymorphic types...)
>>=20
>> If you need polymorphic storage, then maybe the recently accepted Boost.=
PolyCollection is what you need:
>>=20
>> https://github.com/joaquintides/poly_collection
>>=20
>> Best,
>>=20
>> Ion
> =20
> Actually, what I was getting at (as a side point not really germane to th=
e discussion about stable_vector) is that I wonder if things such as Boost.=
PolyCollection would be unnecessary if we had polymorphic value semantics: =
if in that case we could just use the STL containers parameterized by polym=
orphic value types, without needing the usual reference semantics required =
for polymorphism.  It seem like it could save the extra work and complexity=
 of creating new kinds of containers if polymorphic value semantics were ad=
ded in a way that compose well with existing language and standard library =
facilities.
>=20
> -Andy
> --=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=
 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/isoc=
pp.org/d/msgid/std-proposals/CAApgN5-%2BpUKR__dji_FzhhxgCCCejvyPGTRwo8DBbaF=
k6A8GeA%40mail.gmail.com.

--=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/AD6ACEB3-EAF7-46FB-9AE6-7E6713CD7566%40gmail.com=
..

--Apple-Mail-677D1862-7BD8-4E76-BA19-F8DA824E915D
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=
=3Dutf-8"></head><body dir=3D"auto"><div></div><div>polymorphic_value is ma=
king progress through the C++ standards committee.</div><div><br></div><div=
>Latest draft paper and reference implementation are available here:</div><=
div><a href=3D"https://github.com/jbcoe/polymorphic_value">https://github.c=
om/jbcoe/polymorphic_value</a></div><div><br>On 31 May 2017, at 23:04, Anth=
ony Hall &lt;<a href=3D"mailto:anthrond@gmail.com">anthrond@gmail.com</a>&g=
t; wrote:<br><br></div><blockquote type=3D"cite"><div><div dir=3D"ltr"><div=
 class=3D"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmai=
l_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left=
:1ex"><span class=3D"">On 31/05/2017 16:22, Matthew Woehlke wrote:<br>
<blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1p=
x #ccc solid;padding-left:1ex">
Pedantically, though, a vector&lt;unique_ptr&lt;T&gt;&gt; *could* store a T=
*<br>
allocated by the user, whereas I guess a stable_vector&lt;T&gt; would "lose=
"<br>
that functionality. (But that may not be a bad thing; if you *need*<br>
that, the extra indirection of vector&lt;unique_ptr&lt;T&gt;&gt; may help t=
o remind<br>
you that you might be dealing with polymorphic types...)<br>
</blockquote>
<br></span>
If you need polymorphic storage, then maybe the recently accepted Boost.Pol=
yCollection is what you need:<br>
<br>
<a href=3D"https://github.com/joaquintides/poly_collection" rel=3D"noreferr=
er" target=3D"_blank">https://github.com/joaquintide<wbr>s/poly_collection<=
/a><br>
<br>
Best,<br>
<br>
Ion</blockquote><div>&nbsp;</div><div>Actually, what I was getting at (as a=
 side point not really germane to the discussion about stable_vector) is th=
at I wonder if things such as Boost.PolyCollection would be unnecessary if =
we had polymorphic value semantics: if in that case we could just use the S=
TL containers parameterized by polymorphic value types, without needing the=
 usual reference semantics required for polymorphism.&nbsp; It seem like it=
 could save the extra work and complexity of creating new kinds of containe=
rs if polymorphic value semantics were added in a way that compose well wit=
h existing language and standard library facilities.</div><div><br></div><d=
iv>-Andy</div></div></div></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups "=
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>
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/CAApgN5-%2BpUKR__dji_FzhhxgCCCejvyPGT=
Rwo8DBbaFk6A8GeA%40mail.gmail.com?utm_medium=3Demail&amp;utm_source=3Dfoote=
r">https://groups.google.com/a/isocpp.org/d/msgid/std-proposals/CAApgN5-%2B=
pUKR__dji_FzhhxgCCCejvyPGTRwo8DBbaFk6A8GeA%40mail.gmail.com</a>.<br>
</div></blockquote></body></html>

<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/AD6ACEB3-EAF7-46FB-9AE6-7E6713CD7566%=
40gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.c=
om/a/isocpp.org/d/msgid/std-proposals/AD6ACEB3-EAF7-46FB-9AE6-7E6713CD7566%=
40gmail.com</a>.<br />

--Apple-Mail-677D1862-7BD8-4E76-BA19-F8DA824E915D--

.

On 01/06/2017 0:04, Anthony Hall wrote:
> Actually, what I was getting at (as a side point not really germane to
> the discussion about stable_vector) is that I wonder if things such as
> Boost.PolyCollection would be unnecessary if we had polymorphic value
> semantics: if in that case we could just use the STL containers
> parameterized by polymorphic value types, without needing the usual
> reference semantics required for polymorphism.  It seem like it could
> save the extra work and complexity of creating new kinds of containers
> if polymorphic value semantics were added in a way that compose well
> with existing language and standard library facilities.

I can't see how the C++ object model (or any other object model) can
support polymorphic values in a very efficient way. It would certainly
require a memory allocation for each object (except those that fit in
the small object optimization game). For a collection of polymophic
types I don't see how vector<whatever> could beat poly_collection in
most operations.

Ion

--
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/49b5b3c1-0f68-6960-8f5e-43a408739ecb%40gmail.com.

.

------=_Part_5306_623049164.1496324920320
Content-Type: multipart/alternative;
 boundary="----=_Part_5307_815502802.1496324920320"

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



On Wednesday, 31 May 2017 08:35:22 UTC+5:30, Arthur O'Dwyer wrote:
>
> On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <jmck...@gmail.com=20
> <javascript:>> wrote:
>
>> On Tuesday, May 30, 2017 at 7:18:49 PM UTC-4, Arthur O'Dwyer wrote:
>>>
>>> On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:
>>>>
>>>> On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>>>>>
>>>>> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com>=20
>>>>> wrote:=20
>>>>> > Otherwise, following this same logic, we should also just remove=20
>>>>> std::list.  Because std::vector is almost always faster.=20
>>>>>
>>>>> I'm sure Howard is aware: the key advantage of std::list over=20
>>>>> std::vector isn't related to speed of operation. Instead, it is stabi=
lity=20
>>>>> of references and iterators to elements in the std::list.
>>>>
>>>>
>>>> Then can we get `stable_vector` standardized? It may not have stabilit=
y=20
>>>> of iterators, but it does have stability of references. And that's goo=
d=20
>>>> enough for many cases.
>>>>
>>>
>>> I found a thing called Boost.stable_vector, but from the documentation =
I=20
>>> cannot tell what makes it different from std::deque<T>.
>>>
>> std::deque<T> has stability of references (if insertion is happening onl=
y=20
>>> at the front or back) and instability of iterators (unless insertion is=
=20
>>> happening only at the back, in practice, although I'm not sure if you c=
an=20
>>> count on this).=20
>>>
>> Nicol, I know this is a tangent, but could you explain what's missing=20
>>> from std::deque<T> and how you'd propose for a new container to fix it?
>>>
>>
>> Broadly speaking, `deque` has stability of references *and* iterators if=
=20
>> removal happens at either end. Well, obviously references and iterators =
of=20
>> the areas being removed are invalidated, but iterators and references to=
=20
>> other elements are fine. For insertion, references are never invalidated=
 if=20
>> the insertion happens at either end. In all other operations, all=20
>> references and iterators are invalidated (again, broadly speaking. The=
=20
>> rules are very specific to the specific operations in question).
>>
>> `stable_vector` has the same reference stability as `std::list`. That is=
,=20
>> references will never be invalidated by any insertion or removal operati=
on=20
>> (again, unless you're talking about the removed elements). Iterator=20
>> invalidation would work like `vector`.
>>
>> So `stable_vector` effectively fills the niche of `list` users who need=
=20
>> stability of references, but *not* stability of iteration.
>> [...]
>> Implementation-wise, `stable_vector<T>` is just a=20
>> `vector<unique_ptr<T>>`, except that it allocates actual `T`s when you=
=20
>> insert items, and it returns `T&` rather than `T*` or ` unique_ptr<T>&`=
=20
>> from its iterators.
>>
>
> So the use-case is "I want to insert in the middle of this very long=20
> sequence, and also random-access it."  I suppose that's a reasonable set =
of=20
> requirements if you have a really long sequence that you're trying to kee=
p=20
> sorted =E2=80=94 basically flat_set.
> Oh =E2=80=94 except that insertion in the middle is still O(N) because yo=
u have to=20
> shuffle all those pointers, right? It's O(1) in "moves of T objects" but=
=20
> O(N) in "moves of unique_ptr<T> objects."  So the use-case isn't even "a=
=20
> really long sequence"; it's got to be "a long sequence of some really=20
> expensive-to-move T", which I think is less plausible these days. The onl=
y=20
> use-case I can immediately think of is if T is actually immobile, like a=
=20
> mutex or something; but then this sounds like a really niche use-case and=
=20
> I'd think the programmer should just suck it up and use=20
> vector<unique_ptr<T>>.
>
> Certainly "stable_vector" is a bad name for this thing if its elements ar=
e=20
> not contiguous. Contiguity is the number-one defining characteristic of a=
=20
> "vector", in my book.
>
> Though stable vector is implemented like  vector<unique_ptr<T>>,  the `T`=
=20
here is not value_type, but rather struct node{T value; void** up;}; In=20
philosophy it is very close to vector, rather than list or deque. It is the=
=20
up pointer, that makes sure iterators are valid against insert/erase at any=
=20
location & re-index properly. It is almost drop in replacement of vector=20
where iterator and reference stability is needed except, &it[n] =3D=3D &(*i=
t)+n=20
.. The detail is described in a nice blog by author=20
here. http://bannalia.blogspot.in/2008/08/stable-vectors.html
This technique is also used as backbone for random access indexing of=20
boost::multi_index. I find the technique as beautiful one, and its usage=20
are wide enough to make it standard.=20

> I also notice that this container is exactly congruent to a std::deque<T>=
=20
> with a block size of 1.  (Typical block sizes in libc++ and libstdc++ are=
=20
> between 16 to 4096 depending on sizeof(T), and are not configurable by th=
e=20
> programmer. But if they were configurable via a template parameter or=20
> something, bam! Problem solved. This suggests to me that a better name=20
> might be "std::small_block_deque<T, 1>".)
>
>
> I don't necessarily agree with the OP's suggestion. But it would be nice=
=20
>>>> if there was some way to segregate these kinds of performance traps aw=
ay=20
>>>> from regular types/functions. Like a special namespace for special-cas=
e=20
>>>> tools. `std::lower_bound` would only be available for random access=20
>>>> iterators, but `std::corner::lower_bound` would be available for forwa=
rd=20
>>>> iterators. That way, a user makes it clear that they're in a corner ca=
se.
>>>>
>>>
>>> That's an interesting idea; but doesn't that completely break generic=
=20
>>> programming?  Now anytime I want to implement, let's say, my::equal_ran=
ge()=20
>>> =E2=80=94 [Because I need an example of an algorithm that might plausib=
ly depend on=20
>>> std::lower_bound(), let's pretend std::equal_range() doesn't exist.] =
=E2=80=94 I=20
>>> can't just write [...]
>>>
>> =20
>
>> We're talking about things in terms of a Ranges TS implementation. So we=
=20
>> have Concepts, as well as the Ranges concept definitions.
>>
>> So the question is this: what concept do you want those iterators to=20
>> implement? Does `my::equal_range` need to handle all forward iterators, =
or=20
>> is just random-access iterators good enough?
>>
>> This is the same question you'd have when deciding whether to call=20
>> `lower_bound` or `corner::lower_bound`.
>>
>
> Right. And the status quo is that I don't even need to think about it;=20
> both my generic-programmed `equal_range` and the standard's=20
> generic-programmed `lower_bound` work naturally with all kinds of=20
> iterators, as long as those iterators support the necessary operations =
=E2=80=94=20
> which is to say `std::advance` and copying =E2=80=94 which is to say, as =
long as=20
> they model the ForwardIterator concept. This makes perfect sense to me.
>
> So the question is, what would we gain by splitting up std::lower_bound=
=20
> into a new `lower_bound` that is artificially constrained to work only wi=
th=20
> RandomAccessIterators and a new `corner::lower_bound` that is equivalent =
to=20
> the `lower_bound` we have today?  I contend that the answer is "nothing=
=20
> except we might have to go add `corner::` to some generic code that used =
to=20
> work, so that it will work again."  That's what I mean by "a lot of=20
> boilerplate for zero benefit."
>
>
> Meanwhile, it's easy (although not trivial) for any STL vendor to give a=
=20
>>> non-fatal diagnostic=20
>>> <https://stackoverflow.com/questions/8936063/does-there-exist-a-static-=
warning>=20
>>> on e.g. lower_bound of a BidirectionalIterator, if they really *wanted*=
=20
>>> to.
>>>
>>
>> So how would you turn it off when you actually meant to use it?
>>
>
> The same way you turn off vendor-provided STL extensions today. For=20
> example, Visual Studio's STL ships with "checked iterators" which you can=
=20
> turn off by fiddling with the macro _ITERATOR_DEBUG_LEVEL=20
> <https://docs.microsoft.com/en-us/cpp/standard-library/iterator-debug-lev=
el>. =20
> In libstdc++, a similar feature is controlled with _GLIBCXX_DEBUG=20
> <https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_using.html#de=
bug_mode.using.mode>
> .
> Ah, but you mean, what if I have a program where I know that *one* piece=
=20
> of it (and suppose it's in a .h file included everywhere) needs the curre=
nt=20
> `lower_bound`, but everywhere *else* in the program I'd like to get a=20
> warning if I use `lower_bound` with anything other than a=20
> RandomAccessIterator?  ...Well, that's harder. I suspect it's doable, but=
=20
> only by fiddling with something in the vicinity of the offending usage=20
> itself.  Your suggestion boils down to "The vendor could provide a back=
=20
> door via std::corner::lower_bound." The vendor could also provide a back=
=20
> door via a #pragma or something else cleverer than I'm currently thinking=
=20
> of.  I dunno, I guess it comes down to how much effort we want to put int=
o=20
> breaking-and-then-fixing old code as opposed to just letting it keep=20
> working as is. ;)
>
> =E2=80=93Arthur
>

--=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/10c5e235-572d-4e2c-91bd-33288a6ed600%40isocpp.or=
g.

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

<div dir=3D"ltr"><br><br>On Wednesday, 31 May 2017 08:35:22 UTC+5:30, Arthu=
r O&#39;Dwyer  wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=
=3D"ltr">On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <span dir=3D"ltr">&lt=
;<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"hu4QHMS=
PCAAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:&#39;;re=
turn true;" onclick=3D"this.href=3D&#39;javascript:&#39;;return true;">jmck=
....@gmail.com</a>&gt;</span> wrote:<br><div><div class=3D"gmail_quote"><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c=
cc solid;padding-left:1ex"><div dir=3D"ltr">On Tuesday, May 30, 2017 at 7:1=
8:49 PM UTC-4, Arthur O&#39;Dwyer wrote:<blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:=
1ex"><div dir=3D"ltr">On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bo=
las wrote:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0=
..8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monda=
y, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:<blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #cc=
c solid;padding-left:1ex">On 29 May 2017, at 21:47, Howard Hinnant &lt;<a r=
el=3D"nofollow">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list.=C2=A0 Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br></div></div></blockquote><div><br></div><div>I fo=
und a thing called Boost.stable_vector, but from the documentation I cannot=
 tell what makes it different from std::deque&lt;T&gt;.</div></div></blockq=
uote><div></div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-=
left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><d=
iv>std::deque&lt;T&gt; has stability of references (if insertion is happeni=
ng only at the front or back) and instability of iterators (unless insertio=
n is happening only at the back, in practice, although I&#39;m not sure if =
you can count on this).=C2=A0</div></div></blockquote><blockquote class=3D"=
gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr"><div>Nicol, I know this is a tangent, b=
ut could you explain what&#39;s missing from std::deque&lt;T&gt; and how yo=
u&#39;d propose for a new container to fix it?</div></div></blockquote><div=
><br>Broadly speaking, `deque` has stability of references <i>and</i> itera=
tors if removal happens at either end. Well, obviously references and=20
iterators of the areas being removed are invalidated, but iterators and=20
references to other elements are fine. For insertion, references are never =
invalidated if the insertion happens at either end. In all other operations=
, all references and iterators are invalidated (again, broadly speaking. Th=
e rules are very specific to the specific operations in question).<br><br>`=
stable_vector` has the same reference stability as `std::list`. That is, re=
ferences will never be invalidated by any insertion or removal operation (a=
gain, unless you&#39;re talking about the removed elements). Iterator inval=
idation would work like `vector`.<br><br>So `stable_vector` effectively fil=
ls the niche of `list` users who need stability of references, but <i>not</=
i> stability of iteration.<br>[...]<br>Implementation-wise, `stable_vector&=
lt;T&gt;` is just a=20
`vector&lt;unique_ptr&lt;T&gt;&gt;`, except that it allocates actual=20
`T`s when you insert items, and it returns `T&amp;` rather than `T*` or `
 unique_ptr&lt;T&gt;&amp;` from its iterators.<br></div></div></blockquote>=
<div><br></div><div>So the use-case is &quot;I want to insert in the middle=
 of this very long sequence, and also random-access it.&quot; =C2=A0I suppo=
se that&#39;s a reasonable set of requirements if you have a really long se=
quence that you&#39;re trying to keep sorted =E2=80=94 basically flat_set.<=
/div><div>Oh =E2=80=94 except that insertion in the middle is still O(N) be=
cause you have to shuffle all those pointers, right? It&#39;s O(1) in &quot=
;moves of T objects&quot; but O(N) in &quot;moves of unique_ptr&lt;T&gt; ob=
jects.&quot; =C2=A0So the use-case isn&#39;t even &quot;a really long seque=
nce&quot;; it&#39;s got to be &quot;a long sequence of some really expensiv=
e-to-move T&quot;, which I think is less plausible these days. The only use=
-case I can immediately think of is if T is actually immobile, like a mutex=
 or something; but then this sounds like a really niche use-case and I&#39;=
d think the programmer should just suck it up and use vector&lt;unique_ptr&=
lt;T&gt;&gt;.</div><div><br></div><div>Certainly &quot;stable_vector&quot; =
is a bad name for this thing if its elements are not contiguous. Contiguity=
 is the number-one defining characteristic of a &quot;vector&quot;, in my b=
ook.</div><div><br></div></div></div></div></blockquote><div>Though stable =
vector is implemented like =C2=A0vector&lt;unique_ptr&lt;T&gt;&gt;, =C2=A0t=
he `T` here is not value_type, but rather struct node{T value; void** up;};=
 In philosophy it is very close to vector, rather than list or deque. It is=
 the up pointer, that makes sure iterators are valid against insert/erase a=
t any location &amp; re-index properly. It is almost drop in replacement of=
 vector where iterator and reference stability is needed except, &amp;it[n]=
 =3D=3D &amp;(*it)+n . The detail is described in a nice blog by author her=
e.=C2=A0http://bannalia.blogspot.in/2008/08/stable-vectors.html</div><div>T=
his technique is also used as backbone for random access indexing of boost:=
:multi_index. I find the technique as beautiful one, and its usage are wide=
 enough to make it standard.=C2=A0</div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-le=
ft: 1ex;"><div dir=3D"ltr"><div><div class=3D"gmail_quote"><div></div><div>=
I also notice that this container is exactly congruent to a std::deque&lt;T=
&gt; with a block size of 1. =C2=A0(Typical block sizes in libc++ and libst=
dc++ are between 16 to 4096 depending on sizeof(T), and are not configurabl=
e by the programmer. But if they were configurable via a template parameter=
 or something, bam! Problem solved. This suggests to me that a better name =
might be &quot;std::small_block_deque&lt;T, 1&gt;&quot;.)</div><div><br></d=
iv><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .=
8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><blockquo=
te class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1p=
x #ccc solid;padding-left:1ex"><div dir=3D"ltr"><blockquote class=3D"gmail_=
quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;paddi=
ng-left:1ex"><div dir=3D"ltr"><div>I don&#39;t necessarily agree with the O=
P&#39;s suggestion. But it would be nice if there was some way to segregate=
 these kinds of performance traps away from regular types/functions. Like a=
 special namespace for special-case tools. `std::lower_bound` would only be=
 available for random access iterators, but `std::corner::lower_bound` woul=
d be available for forward iterators. That way, a user makes it clear that =
they&#39;re in a corner case.<br></div></div></blockquote><div><br></div><d=
iv>That&#39;s an interesting idea; but doesn&#39;t that completely break ge=
neric programming?=C2=A0 Now anytime I want to implement, let&#39;s say, my=
::equal_range() =E2=80=94 [Because I need an example of an algorithm that m=
ight plausibly depend on std::lower_bound(), let&#39;s pretend std::equal_r=
ange() doesn&#39;t exist.] =E2=80=94 I can&#39;t just write [...]</div></di=
v></blockquote><div></div></div></blockquote><div>=C2=A0</div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;=
padding-left:1ex"><div dir=3D"ltr"><div>We&#39;re talking about things in t=
erms of a Ranges TS implementation. So we have Concepts, as well as the Ran=
ges concept definitions.<br><br>So the question is this: what concept do yo=
u want those iterators to implement? Does `my::equal_range` need to handle =
all forward iterators, or is just random-access iterators good enough?<br><=
br>This is the same question you&#39;d have when deciding whether to call `=
lower_bound` or `corner::lower_bound`.<br></div></div></blockquote><div><br=
></div><div>Right. And the status quo is that I don&#39;t even need to thin=
k about it; both my generic-programmed `equal_range` and the standard&#39;s=
 generic-programmed `lower_bound` work naturally with all kinds of iterator=
s, as long as those iterators support the necessary operations =E2=80=94 wh=
ich is to say `std::advance` and copying =E2=80=94 which is to say, as long=
 as they model the ForwardIterator concept. This makes perfect sense to me.=
</div><div><br></div><div>So the question is, what would we gain by splitti=
ng up std::lower_bound into a new `lower_bound` that is artificially constr=
ained to work only with RandomAccessIterators and a new `corner::lower_boun=
d` that is equivalent to the `lower_bound` we have today?=C2=A0 I contend t=
hat the answer is &quot;nothing except we might have to go add `corner::` t=
o some generic code that used to work, so that it will work again.&quot; =
=C2=A0That&#39;s what I mean by &quot;a lot of boilerplate for zero benefit=
..&quot;</div><div><br></div><div><br></div><blockquote class=3D"gmail_quote=
" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><=
div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-=
left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><d=
iv>Meanwhile, it&#39;s easy (although not trivial) for any STL vendor to <a=
 href=3D"https://stackoverflow.com/questions/8936063/does-there-exist-a-sta=
tic-warning" rel=3D"nofollow" target=3D"_blank" onmousedown=3D"this.href=3D=
&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fstackoverflow.com%2Fques=
tions%2F8936063%2Fdoes-there-exist-a-static-warning\x26sa\x3dD\x26sntz\x3d1=
\x26usg\x3dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return true;" onclick=3D=
"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fstackoverfl=
ow.com%2Fquestions%2F8936063%2Fdoes-there-exist-a-static-warning\x26sa\x3dD=
\x26sntz\x3d1\x26usg\x3dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return true=
;">give a non-fatal diagnostic</a> on e.g. lower_bound of a BidirectionalIt=
erator, if they really <i>wanted</i> to.<br></div></div></blockquote><div><=
br>So how would you turn it off when you actually meant to use it?<br></div=
></div></blockquote><div><br></div><div>The same way you turn off vendor-pr=
ovided STL extensions today. For example, Visual Studio&#39;s STL ships wit=
h &quot;checked iterators&quot; which you can turn off by fiddling with the=
 macro=C2=A0<a href=3D"https://docs.microsoft.com/en-us/cpp/standard-librar=
y/iterator-debug-level" target=3D"_blank" rel=3D"nofollow" onmousedown=3D"t=
his.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fdocs.microsof=
t.com%2Fen-us%2Fcpp%2Fstandard-library%2Fiterator-debug-level\x26sa\x3dD\x2=
6sntz\x3d1\x26usg\x3dAFQjCNEBeT9EaBwAVcHq47CkH_x-frImrQ&#39;;return true;" =
onclick=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fd=
ocs.microsoft.com%2Fen-us%2Fcpp%2Fstandard-library%2Fiterator-debug-level\x=
26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEBeT9EaBwAVcHq47CkH_x-frImrQ&#39;;re=
turn true;">_ITERATOR_DEBUG_LEVEL</a>.=C2=A0 In libstdc++, a similar featur=
e is controlled with <a href=3D"https://gcc.gnu.org/onlinedocs/libstdc++/ma=
nual/debug_mode_using.html#debug_mode.using.mode" target=3D"_blank" rel=3D"=
nofollow" onmousedown=3D"this.href=3D&#39;https://www.google.com/url?q\x3dh=
ttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2Flibstdc%2B%2B%2Fmanual%2Fdebug_mode=
_using.html%23debug_mode.using.mode\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjC=
NFFuW8W0eJTlM2i3nkYWEQ92slU2g&#39;;return true;" onclick=3D"this.href=3D&#3=
9;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2F=
libstdc%2B%2B%2Fmanual%2Fdebug_mode_using.html%23debug_mode.using.mode\x26s=
a\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFFuW8W0eJTlM2i3nkYWEQ92slU2g&#39;;retur=
n true;">_GLIBCXX_DEBUG</a>.</div><div>Ah, but you mean, what if I have a p=
rogram where I know that=C2=A0<i>one</i> piece of it (and suppose it&#39;s =
in a .h file included everywhere) needs the current `lower_bound`, but ever=
ywhere <i>else</i> in the program I&#39;d like to get a warning if I use `l=
ower_bound` with anything other than a RandomAccessIterator? =C2=A0...Well,=
 that&#39;s harder. I suspect it&#39;s doable, but only by fiddling with so=
mething in the vicinity of the offending usage itself.=C2=A0 Your suggestio=
n boils down to &quot;The vendor could provide a back door via std::corner:=
:lower_bound.&quot; The vendor could also provide a back door via a #pragma=
 or something else cleverer than I&#39;m currently thinking of.=C2=A0 I dun=
no, I guess it comes down to how much effort we want to put into breaking-a=
nd-then-fixing old code as opposed to just letting it keep working as is. ;=
)</div><div><br></div><div>=E2=80=93Arthur</div></div></div></div>
</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/10c5e235-572d-4e2c-91bd-33288a6ed600%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/10c5e235-572d-4e2c-91bd-33288a6ed600=
%40isocpp.org</a>.<br />

------=_Part_5307_815502802.1496324920320--

------=_Part_5306_623049164.1496324920320--

.

------=_Part_5362_1703877326.1496331602370
Content-Type: multipart/alternative;
 boundary="----=_Part_5363_1301401447.1496331602371"

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

On Tuesday, May 30, 2017 at 11:05:22 PM UTC-4, Arthur O'Dwyer wrote:
>
> On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <jmck...@gmail.com=20
> <javascript:>> wrote:
>
>> On Tuesday, May 30, 2017 at 7:18:49 PM UTC-4, Arthur O'Dwyer wrote:
>>>
>>> On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrote:
>>>>
>>>> On Monday, May 29, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:
>>>>>
>>>>> On 29 May 2017, at 21:47, Howard Hinnant <howard....@gmail.com>=20
>>>>> wrote:=20
>>>>> > Otherwise, following this same logic, we should also just remove=20
>>>>> std::list.  Because std::vector is almost always faster.=20
>>>>>
>>>>> I'm sure Howard is aware: the key advantage of std::list over=20
>>>>> std::vector isn't related to speed of operation. Instead, it is stabi=
lity=20
>>>>> of references and iterators to elements in the std::list.
>>>>
>>>>
>>>> Then can we get `stable_vector` standardized? It may not have stabilit=
y=20
>>>> of iterators, but it does have stability of references. And that's goo=
d=20
>>>> enough for many cases.
>>>>
>>>
>>> I found a thing called Boost.stable_vector, but from the documentation =
I=20
>>> cannot tell what makes it different from std::deque<T>.
>>>
>> std::deque<T> has stability of references (if insertion is happening onl=
y=20
>>> at the front or back) and instability of iterators (unless insertion is=
=20
>>> happening only at the back, in practice, although I'm not sure if you c=
an=20
>>> count on this).=20
>>>
>> Nicol, I know this is a tangent, but could you explain what's missing=20
>>> from std::deque<T> and how you'd propose for a new container to fix it?
>>>
>>
>> Broadly speaking, `deque` has stability of references *and* iterators if=
=20
>> removal happens at either end. Well, obviously references and iterators =
of=20
>> the areas being removed are invalidated, but iterators and references to=
=20
>> other elements are fine. For insertion, references are never invalidated=
 if=20
>> the insertion happens at either end. In all other operations, all=20
>> references and iterators are invalidated (again, broadly speaking. The=
=20
>> rules are very specific to the specific operations in question).
>>
>> `stable_vector` has the same reference stability as `std::list`. That is=
,=20
>> references will never be invalidated by any insertion or removal operati=
on=20
>> (again, unless you're talking about the removed elements). Iterator=20
>> invalidation would work like `vector`.
>>
>> So `stable_vector` effectively fills the niche of `list` users who need=
=20
>> stability of references, but *not* stability of iteration.
>> [...]
>> Implementation-wise, `stable_vector<T>` is just a=20
>> `vector<unique_ptr<T>>`, except that it allocates actual `T`s when you=
=20
>> insert items, and it returns `T&` rather than `T*` or ` unique_ptr<T>&`=
=20
>> from its iterators.
>>
>
> So the use-case is "I want to insert in the middle of this very long=20
> sequence, and also random-access it."  I suppose that's a reasonable set =
of=20
> requirements if you have a really long sequence that you're trying to kee=
p=20
> sorted =E2=80=94 basically flat_set.
> Oh =E2=80=94 except that insertion in the middle is still O(N) because yo=
u have to=20
> shuffle all those pointers, right? It's O(1) in "moves of T objects" but=
=20
> O(N) in "moves of unique_ptr<T> objects."  So the use-case isn't even "a=
=20
> really long sequence"; it's got to be "a long sequence of some really=20
> expensive-to-move T", which I think is less plausible these days. The onl=
y=20
> use-case I can immediately think of is if T is actually immobile, like a=
=20
> mutex or something; but then this sounds like a really niche use-case and=
=20
> I'd think the programmer should just suck it up and use=20
> vector<unique_ptr<T>>.
>

I think you're misunderstanding the use case. The use case is effectively=
=20
"most of the times you would reasonably think `list` would be a=20
good/necessary idea". People primarily use `list` because of either fast=20
item swapping or stability of the object (ie: you can rely on it continuing=
=20
to exist until the item is removed from the container). Both of those cases=
=20
are covered by `stable_vector`, and generally speaking you get better=20
performance to boot (that's the point of this thread, after all:=20
`lower_bound`'s terrible performance with `list` iterators). The only thing=
=20
`stable_vector` can't do that `list` can is provide complete stability of=
=20
all iterators.

`stable_vector` may have `vector` in the name, but the use cases it's=20
replacing would otherwise have been filled by `list`.

Certainly "stable_vector" is a bad name for this thing if its elements are=
=20
> not contiguous. Contiguity is the number-one defining characteristic of a=
=20
> "vector", in my book.
>

I can agree with that.

I also notice that this container is exactly congruent to a std::deque<T>=
=20
> with a block size of 1. (Typical block sizes in libc++ and libstdc++ are=
=20
> between 16 to 4096 depending on sizeof(T), and are not configurable by th=
e=20
> programmer. But if they were configurable via a template parameter or=20
> something, bam! Problem solved. This suggests to me that a better name=20
> might be "std::small_block_deque<T, 1>".)
>

It could be implemented as such a thing. But the standard would have the=20
stability requirements of a `deque`, not a `stable_vector`. Not unless=20
there were specialized language in the standard (as well as code) for the=
=20
case of a block size of 1. `deque` also wouldn't have the splicing behavior=
=20
that a specialized `stable_vector` class could provide. And most important=
=20
of all, `stable_vector` is not a double-ended queue.

So there are plenty of reasons why it should be a separate class.

And that ignores the question of whether we should be imposing such=20
implementation-specific, low-level requirements on `deque` at all (that is,=
=20
being implemented through blocks).

I don't necessarily agree with the OP's suggestion. But it would be nice if=
=20
>>>> there was some way to segregate these kinds of performance traps away =
from=20
>>>> regular types/functions. Like a special namespace for special-case too=
ls.=20
>>>> `std::lower_bound` would only be available for random access iterators=
, but=20
>>>> `std::corner::lower_bound` would be available for forward iterators. T=
hat=20
>>>> way, a user makes it clear that they're in a corner case.
>>>>
>>>
>>> That's an interesting idea; but doesn't that completely break generic=
=20
>>> programming?  Now anytime I want to implement, let's say, my::equal_ran=
ge()=20
>>> =E2=80=94 [Because I need an example of an algorithm that might plausib=
ly depend on=20
>>> std::lower_bound(), let's pretend std::equal_range() doesn't exist.] =
=E2=80=94 I=20
>>> can't just write [...]
>>>
>> =20
>
>> We're talking about things in terms of a Ranges TS implementation. So we=
=20
>> have Concepts, as well as the Ranges concept definitions.
>>
>> So the question is this: what concept do you want those iterators to=20
>> implement? Does `my::equal_range` need to handle all forward iterators, =
or=20
>> is just random-access iterators good enough?
>>
>> This is the same question you'd have when deciding whether to call=20
>> `lower_bound` or `corner::lower_bound`.
>>
>
> Right. And the status quo is that I don't even need to think about it;=20
> both my generic-programmed `equal_range` and the standard's=20
> generic-programmed `lower_bound` work naturally with all kinds of=20
> iterators, as long as those iterators support the necessary operations =
=E2=80=94=20
> which is to say `std::advance` and copying =E2=80=94 which is to say, as =
long as=20
> they model the ForwardIterator concept. This makes perfect sense to me.
>
> So the question is, what would we gain by splitting up std::lower_bound=
=20
> into a new `lower_bound` that is artificially constrained to work only wi=
th=20
> RandomAccessIterators and a new `corner::lower_bound` that is equivalent =
to=20
> the `lower_bound` we have today?  I contend that the answer is "nothing=
=20
> except we might have to go add `corner::` to some generic code that used =
to=20
> work, so that it will work again."  That's what I mean by "a lot of=20
> boilerplate for zero benefit."
>

But it has benefits. Namely, it prevents people from accidentally misusing=
=20
it. Which is what this entire thread is about. It may not be benefits to=20
you specifically. But you can't say that it has "zero benefit".
=20

> Meanwhile, it's easy (although not trivial) for any STL vendor to give a=
=20
>>> non-fatal diagnostic=20
>>> <https://stackoverflow.com/questions/8936063/does-there-exist-a-static-=
warning>=20
>>> on e.g. lower_bound of a BidirectionalIterator, if they really *wanted*=
=20
>>> to.
>>>
>>
>> So how would you turn it off when you actually meant to use it?
>>
>
> The same way you turn off vendor-provided STL extensions today. For=20
> example, Visual Studio's STL ships with "checked iterators" which you can=
=20
> turn off by fiddling with the macro _ITERATOR_DEBUG_LEVEL=20
> <https://docs.microsoft.com/en-us/cpp/standard-library/iterator-debug-lev=
el>. =20
> In libstdc++, a similar feature is controlled with _GLIBCXX_DEBUG=20
> <https://gcc.gnu.org/onlinedocs/libstdc++/manual/debug_mode_using.html#de=
bug_mode.using.mode>
> .
>
Ah, but you mean, what if I have a program where I know that *one* piece of=
=20
> it (and suppose it's in a .h file included everywhere) needs the current=
=20
> `lower_bound`, but everywhere *else* in the program I'd like to get a=20
> warning if I use `lower_bound` with anything other than a=20
> RandomAccessIterator?  ...Well, that's harder. I suspect it's doable, but=
=20
> only by fiddling with something in the vicinity of the offending usage=20
> itself.  Your suggestion boils down to "The vendor could provide a back=
=20
> door via std::corner::lower_bound." The vendor could also provide a back=
=20
> door via a #pragma or something else cleverer than I'm currently thinking=
=20
> of.  I dunno, I guess it comes down to how much effort we want to put int=
o=20
> breaking-and-then-fixing old code as opposed to just letting it keep=20
> working as is. ;)
>

--=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/1b46a026-7276-48da-b901-b3e911cab8de%40isocpp.or=
g.

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

<div dir=3D"ltr">On Tuesday, May 30, 2017 at 11:05:22 PM UTC-4, Arthur O&#3=
9;Dwyer wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
>On Tue, May 30, 2017 at 5:27 PM, Nicol Bolas <span dir=3D"ltr">&lt;<a href=
=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=3D"hu4QHMSPCAAJ" r=
el=3D"nofollow" onmousedown=3D"this.href=3D&#39;javascript:&#39;;return tru=
e;" onclick=3D"this.href=3D&#39;javascript:&#39;;return true;">jmck...@gmai=
l.com</a>&gt;</span> wrote:<br><div><div class=3D"gmail_quote"><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr">On Tuesday, May 30, 2017 at 7:18:49 PM =
UTC-4, Arthur O&#39;Dwyer wrote:<blockquote class=3D"gmail_quote" style=3D"=
margin:0;margin-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><di=
v dir=3D"ltr">On Monday, May 29, 2017 at 2:52:18 PM UTC-7, Nicol Bolas wrot=
e:<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;bor=
der-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr">On Monday, May 2=
9, 2017 at 5:39:41 PM UTC-4, Dietmar K=C3=BChl wrote:<blockquote class=3D"g=
mail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid;=
padding-left:1ex">On 29 May 2017, at 21:47, Howard Hinnant &lt;<a rel=3D"no=
follow">howard....@gmail.com</a>&gt; wrote:
<br>&gt; Otherwise, following this same logic, we should also just remove s=
td::list.=C2=A0 Because std::vector is almost always faster.
<br>
<br>I&#39;m sure Howard is aware: the key advantage of std::list over std::=
vector isn&#39;t related to speed of operation. Instead, it is stability of=
 references and iterators to elements in the std::list.</blockquote><div><b=
r>Then can we get `stable_vector` standardized? It may not have stability o=
f iterators, but it does have stability of references. And that&#39;s good =
enough for many cases.<br></div></div></blockquote><div><br></div><div>I fo=
und a thing called Boost.stable_vector, but from the documentation I cannot=
 tell what makes it different from std::deque&lt;T&gt;.</div></div></blockq=
uote><div></div><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-=
left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><d=
iv>std::deque&lt;T&gt; has stability of references (if insertion is happeni=
ng only at the front or back) and instability of iterators (unless insertio=
n is happening only at the back, in practice, although I&#39;m not sure if =
you can count on this).=C2=A0</div></div></blockquote><blockquote class=3D"=
gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr"><div>Nicol, I know this is a tangent, b=
ut could you explain what&#39;s missing from std::deque&lt;T&gt; and how yo=
u&#39;d propose for a new container to fix it?</div></div></blockquote><div=
><br>Broadly speaking, `deque` has stability of references <i>and</i> itera=
tors if removal happens at either end. Well, obviously references and=20
iterators of the areas being removed are invalidated, but iterators and=20
references to other elements are fine. For insertion, references are never =
invalidated if the insertion happens at either end. In all other operations=
, all references and iterators are invalidated (again, broadly speaking. Th=
e rules are very specific to the specific operations in question).<br><br>`=
stable_vector` has the same reference stability as `std::list`. That is, re=
ferences will never be invalidated by any insertion or removal operation (a=
gain, unless you&#39;re talking about the removed elements). Iterator inval=
idation would work like `vector`.<br><br>So `stable_vector` effectively fil=
ls the niche of `list` users who need stability of references, but <i>not</=
i> stability of iteration.<br>[...]<br>Implementation-wise, `stable_vector&=
lt;T&gt;` is just a=20
`vector&lt;unique_ptr&lt;T&gt;&gt;`, except that it allocates actual=20
`T`s when you insert items, and it returns `T&amp;` rather than `T*` or `
 unique_ptr&lt;T&gt;&amp;` from its iterators.<br></div></div></blockquote>=
<div><br></div><div>So the use-case is &quot;I want to insert in the middle=
 of this very long sequence, and also random-access it.&quot; =C2=A0I suppo=
se that&#39;s a reasonable set of requirements if you have a really long se=
quence that you&#39;re trying to keep sorted =E2=80=94 basically flat_set.<=
/div><div>Oh =E2=80=94 except that insertion in the middle is still O(N) be=
cause you have to shuffle all those pointers, right? It&#39;s O(1) in &quot=
;moves of T objects&quot; but O(N) in &quot;moves of unique_ptr&lt;T&gt; ob=
jects.&quot; =C2=A0So the use-case isn&#39;t even &quot;a really long seque=
nce&quot;; it&#39;s got to be &quot;a long sequence of some really expensiv=
e-to-move T&quot;, which I think is less plausible these days. The only use=
-case I can immediately think of is if T is actually immobile, like a mutex=
 or something; but then this sounds like a really niche use-case and I&#39;=
d think the programmer should just suck it up and use vector&lt;unique_ptr&=
lt;T&gt;&gt;.</div></div></div></div></blockquote><div><br>I think you&#39;=
re misunderstanding the use case. The use case is effectively &quot;most of=
 the times you would reasonably think `list` would be a good/necessary idea=
&quot;. People primarily use `list` because of either fast item swapping or=
 stability of the object (ie: you can rely on it continuing to exist until =
the item is removed from the container). Both of those cases are covered by=
 `stable_vector`, and generally speaking you get better performance to boot=
 (that&#39;s the point of this thread, after all: `lower_bound`&#39;s terri=
ble performance with `list` iterators). The only thing `stable_vector` can&=
#39;t do that `list` can is provide complete stability of all iterators.<br=
><br>`stable_vector` may have `vector` in the name, but the use cases it&#3=
9;s replacing would otherwise have been filled by `list`.<br><br></div><blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><div></div><div>Certainly &quot;stable_vector&quot; is a b=
ad name for this thing if its elements are not contiguous. Contiguity is th=
e number-one defining characteristic of a &quot;vector&quot;, in my book.</=
div></div></div></div></blockquote><div><br>I can agree with that.<br><br><=
/div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8e=
x;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><di=
v class=3D"gmail_quote"><div></div><div>I also notice that this container i=
s exactly congruent to a std::deque&lt;T&gt; with a block size of 1. (Typic=
al block sizes in libc++ and libstdc++ are between 16 to 4096 depending on =
sizeof(T), and are not configurable by the programmer. But if they were con=
figurable via a template parameter or something, bam! Problem solved. This =
suggests to me that a better name might be &quot;std::small_block_deque&lt;=
T, 1&gt;&quot;.)</div></div></div></div></blockquote><div><br>It could be i=
mplemented as such a thing. But the standard would have the stability requi=
rements of a `deque`, not a `stable_vector`. Not unless there were speciali=
zed language in the standard (as well as code) for the case of a block size=
 of 1. `deque` also wouldn&#39;t have the splicing behavior that a speciali=
zed `stable_vector` class could provide. And most important of all, `stable=
_vector` is not a double-ended queue.<br><br>So there are plenty of reasons=
 why it should be a separate class.<br><br>And that ignores the question of=
 whether we should be imposing such implementation-specific, low-level requ=
irements on `deque` at all (that is, being implemented through blocks).<br>=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left:=
 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><di=
v><div class=3D"gmail_quote"><div></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div=
 dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin-lef=
t:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><bloc=
kquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-lef=
t:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>I don&#39;t necess=
arily agree with the OP&#39;s suggestion. But it would be nice if there was=
 some way to segregate these kinds of performance traps away from regular t=
ypes/functions. Like a special namespace for special-case tools. `std::lowe=
r_bound` would only be available for random access iterators, but `std::cor=
ner::lower_bound` would be available for forward iterators. That way, a use=
r makes it clear that they&#39;re in a corner case.<br></div></div></blockq=
uote><div><br></div><div>That&#39;s an interesting idea; but doesn&#39;t th=
at completely break generic programming?=C2=A0 Now anytime I want to implem=
ent, let&#39;s say, my::equal_range() =E2=80=94 [Because I need an example =
of an algorithm that might plausibly depend on std::lower_bound(), let&#39;=
s pretend std::equal_range() doesn&#39;t exist.] =E2=80=94 I can&#39;t just=
 write [...]</div></div></blockquote><div></div></div></blockquote><div>=C2=
=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>We&#39;re tal=
king about things in terms of a Ranges TS implementation. So we have Concep=
ts, as well as the Ranges concept definitions.<br><br>So the question is th=
is: what concept do you want those iterators to implement? Does `my::equal_=
range` need to handle all forward iterators, or is just random-access itera=
tors good enough?<br><br>This is the same question you&#39;d have when deci=
ding whether to call `lower_bound` or `corner::lower_bound`.<br></div></div=
></blockquote><div><br></div><div>Right. And the status quo is that I don&#=
39;t even need to think about it; both my generic-programmed `equal_range` =
and the standard&#39;s generic-programmed `lower_bound` work naturally with=
 all kinds of iterators, as long as those iterators support the necessary o=
perations =E2=80=94 which is to say `std::advance` and copying =E2=80=94 wh=
ich is to say, as long as they model the ForwardIterator concept. This make=
s perfect sense to me.</div><div><br></div><div>So the question is, what wo=
uld we gain by splitting up std::lower_bound into a new `lower_bound` that =
is artificially constrained to work only with RandomAccessIterators and a n=
ew `corner::lower_bound` that is equivalent to the `lower_bound` we have to=
day?=C2=A0 I contend that the answer is &quot;nothing except we might have =
to go add `corner::` to some generic code that used to work, so that it wil=
l work again.&quot; =C2=A0That&#39;s what I mean by &quot;a lot of boilerpl=
ate for zero benefit.&quot;</div></div></div></div></blockquote><div><br>Bu=
t it has benefits. Namely, it prevents people from accidentally misusing it=
.. Which is what this entire thread is about. It may not be benefits to you =
specifically. But you can&#39;t say that it has &quot;zero benefit&quot;.<b=
r>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-l=
eft: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"=
><div><div class=3D"gmail_quote"><div></div><blockquote class=3D"gmail_quot=
e" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">=
<div dir=3D"ltr"><blockquote class=3D"gmail_quote" style=3D"margin:0;margin=
-left:0.8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><=
div>Meanwhile, it&#39;s easy (although not trivial) for any STL vendor to <=
a href=3D"https://stackoverflow.com/questions/8936063/does-there-exist-a-st=
atic-warning" rel=3D"nofollow" target=3D"_blank" onmousedown=3D"this.href=
=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fstackoverflow.com%2Fq=
uestions%2F8936063%2Fdoes-there-exist-a-static-warning\x26sa\x3dD\x26sntz\x=
3d1\x26usg\x3dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return true;" onclick=
=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fstackove=
rflow.com%2Fquestions%2F8936063%2Fdoes-there-exist-a-static-warning\x26sa\x=
3dD\x26sntz\x3d1\x26usg\x3dAFQjCNG92RyGigRma4WfR8uywLdXyJ5NHQ&#39;;return t=
rue;">give a non-fatal diagnostic</a> on e.g. lower_bound of a Bidirectiona=
lIterator, if they really <i>wanted</i> to.<br></div></div></blockquote><di=
v><br>So how would you turn it off when you actually meant to use it?<br></=
div></div></blockquote><div><br></div><div>The same way you turn off vendor=
-provided STL extensions today. For example, Visual Studio&#39;s STL ships =
with &quot;checked iterators&quot; which you can turn off by fiddling with =
the macro=C2=A0<a href=3D"https://docs.microsoft.com/en-us/cpp/standard-lib=
rary/iterator-debug-level" target=3D"_blank" rel=3D"nofollow" onmousedown=
=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fdocs.mic=
rosoft.com%2Fen-us%2Fcpp%2Fstandard-library%2Fiterator-debug-level\x26sa\x3=
dD\x26sntz\x3d1\x26usg\x3dAFQjCNEBeT9EaBwAVcHq47CkH_x-frImrQ&#39;;return tr=
ue;" onclick=3D"this.href=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2=
F%2Fdocs.microsoft.com%2Fen-us%2Fcpp%2Fstandard-library%2Fiterator-debug-le=
vel\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEBeT9EaBwAVcHq47CkH_x-frImrQ&#3=
9;;return true;">_ITERATOR_DEBUG_LEVEL</a>.=C2=A0 In libstdc++, a similar f=
eature is controlled with <a href=3D"https://gcc.gnu.org/onlinedocs/libstdc=
++/manual/debug_mode_using.html#debug_mode.using.mode" target=3D"_blank" re=
l=3D"nofollow" onmousedown=3D"this.href=3D&#39;https://www.google.com/url?q=
\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlinedocs%2Flibstdc%2B%2B%2Fmanual%2Fdebug=
_mode_using.html%23debug_mode.using.mode\x26sa\x3dD\x26sntz\x3d1\x26usg\x3d=
AFQjCNFFuW8W0eJTlM2i3nkYWEQ92slU2g&#39;;return true;" onclick=3D"this.href=
=3D&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgcc.gnu.org%2Fonlined=
ocs%2Flibstdc%2B%2B%2Fmanual%2Fdebug_mode_using.html%23debug_mode.using.mod=
e\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFFuW8W0eJTlM2i3nkYWEQ92slU2g&#39;=
;return true;">_GLIBCXX_DEBUG</a>.</div></div></div></div></blockquote><blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><div><div class=
=3D"gmail_quote"><div>Ah, but you mean, what if I have a program where I kn=
ow that=C2=A0<i>one</i> piece of it (and suppose it&#39;s in a .h file incl=
uded everywhere) needs the current `lower_bound`, but everywhere <i>else</i=
> in the program I&#39;d like to get a warning if I use `lower_bound` with =
anything other than a RandomAccessIterator? =C2=A0...Well, that&#39;s harde=
r. I suspect it&#39;s doable, but only by fiddling with something in the vi=
cinity of the offending usage itself.=C2=A0 Your suggestion boils down to &=
quot;The vendor could provide a back door via std::corner::lower_bound.&quo=
t; The vendor could also provide a back door via a #pragma or something els=
e cleverer than I&#39;m currently thinking of.=C2=A0 I dunno, I guess it co=
mes down to how much effort we want to put into breaking-and-then-fixing ol=
d code as opposed to just letting it keep working as is. ;)</div></div></di=
v></div>
</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/1b46a026-7276-48da-b901-b3e911cab8de%=
40isocpp.org?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/a/isocpp.org/d/msgid/std-proposals/1b46a026-7276-48da-b901-b3e911cab8de=
%40isocpp.org</a>.<br />

------=_Part_5363_1301401447.1496331602371--

------=_Part_5362_1703877326.1496331602370--

.