Topic: Faster version of std::find
Author: Marcelo Zimbres <mzimbres@gmail.com>
Date: Tue, 29 Dec 2015 12:27:38 -0200
Raw View
Hi,
I would like to ask you whether a faster (and simpler) version of std::find,
that tests on only one condition, has already been proposed in c++?
The implementations of std::find I found in libstd++ and libcxx are basically
implemented like this (simplified)
for (; first != last; ++first)
if (*first == value)
break;
Which tests two conditions (first != last) and (*first == value) to find the
element.
A faster and simpler version can be written testing only one condition
while (*begin != value)
++begin;
if I assume that the last element in the range [begin, end) is equal to
"value". If we call this faster version as std::find_intrusive it could
be used like this
std::vector<int> data(size + 1); // one element more reserved to find_intrusive.
// fills the data
data.back() = value; // Sets the element we want find.
auto iter = std::find_intrusive(std::begin(data), std::begin(data), value);
Benchmarks showed that benchmarks are non-negligible. Do you think this would
be an interesting addition to c++?
Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Tue, 29 Dec 2015 06:45:34 -0800 (PST)
Raw View
------=_Part_2_1097423139.1451400334536
Content-Type: multipart/alternative;
boundary="----=_Part_3_1498143264.1451400334536"
------=_Part_3_1498143264.1451400334536
Content-Type: text/plain; charset=UTF-8
On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres wrote:
>
> Hi,
>
> I would like to ask you whether a faster (and simpler) version of
> std::find,
> that tests on only one condition, has already been proposed in c++?
>
> The implementations of std::find I found in libstd++ and libcxx are
> basically
> implemented like this (simplified)
>
> for (; first != last; ++first)
> if (*first == value)
> break;
>
> Which tests two conditions (first != last) and (*first == value) to find
> the
> element.
>
> A faster and simpler version can be written testing only one condition
>
> while (*begin != value)
> ++begin;
>
> if I assume that the last element in the range [begin, end) is equal to
> "value". If we call this faster version as std::find_intrusive it could
> be used like this
>
> std::vector<int> data(size + 1); // one element more reserved to
> find_intrusive.
>
> // fills the data
>
> data.back() = value; // Sets the element we want find.
> auto iter = std::find_intrusive(std::begin(data), std::begin(data),
> value);
>
> Benchmarks showed that benchmarks are non-negligible. Do you think this
> would
> be an interesting addition to c++?
>
It's a perfectly valid function for specialized needs. But for the C++
standard? No; it's just way to easy to screw up.
Also, there's no point in even passing the end iterator if you're not going
to actually use it.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_3_1498143264.1451400334536
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br><br>On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>I would like to ask you whether a faster (and simpler) version of std::=
find,
<br>that tests on only one condition, has already been proposed in c++?
<br>
<br>The implementations of std::find I found in libstd++ and libcxx are bas=
ically
<br>implemented like this (simplified)
<br>
<br>=C2=A0 for (; first !=3D last; ++first)
<br>=C2=A0 =C2=A0 if (*first =3D=3D value)
<br>=C2=A0 =C2=A0 =C2=A0 break;
<br>
<br>Which tests two conditions (first !=3D last) and (*first =3D=3D value) =
to find the
<br>element.
<br>
<br>A faster and simpler version can be written testing only one condition
<br>
<br>=C2=A0 while (*begin !=3D value)
<br>=C2=A0 =C2=A0 ++begin;
<br>
<br>if I assume that the last element in the range [begin, end) is equal to
<br>"value". If we call this faster version as std::find_intrusiv=
e it could
<br>be used like this
<br>
<br>std::vector<int> data(size + 1); // one element more reserved to =
find_intrusive.
<br>
<br>// fills the data
<br>
<br>data.back() =3D value; // Sets the element we want find.
<br>auto iter =3D std::find_intrusive(std::<wbr>begin(data), std::begin(dat=
a), value);
<br>
<br>Benchmarks showed that benchmarks are non-negligible. Do you think this=
would
<br>be an interesting addition to c++?<br></blockquote><div><br>It's a =
perfectly valid function for specialized needs. But for the C++ standard? N=
o; it's just way to easy to screw up.<br><br>Also, there's no point=
in even passing the end iterator if you're not going to actually use i=
t.<br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_3_1498143264.1451400334536--
------=_Part_2_1097423139.1451400334536--
.
Author: Marcelo Zimbres <mzimbres@gmail.com>
Date: Tue, 29 Dec 2015 17:17:06 -0200
Raw View
2015-12-29 12:45 GMT-02:00 Nicol Bolas <jmckesson@gmail.com>:
>
>
> On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres wrote:
>>
>> Hi,
>>
>> I would like to ask you whether a faster (and simpler) version of
>> std::find,
>> that tests on only one condition, has already been proposed in c++?
>>
>> The implementations of std::find I found in libstd++ and libcxx are
>> basically
>> implemented like this (simplified)
>>
>> for (; first != last; ++first)
>> if (*first == value)
>> break;
>>
>> Which tests two conditions (first != last) and (*first == value) to find
>> the
>> element.
>>
>> A faster and simpler version can be written testing only one condition
>>
>> while (*begin != value)
>> ++begin;
>>
>> if I assume that the last element in the range [begin, end) is equal to
>> "value". If we call this faster version as std::find_intrusive it could
>> be used like this
>>
>> std::vector<int> data(size + 1); // one element more reserved to
>> find_intrusive.
>>
>> // fills the data
>>
>> data.back() = value; // Sets the element we want find.
>> auto iter = std::find_intrusive(std::begin(data), std::begin(data),
>> value);
>>
>> Benchmarks showed that benchmarks are non-negligible. Do you think this
>> would
>> be an interesting addition to c++?
>
>
> It's a perfectly valid function for specialized needs. But for the C++
> standard? No; it's just way to easy to screw up.
It is also way to easy to screw up with algorithms like std::transform
that assume an iterator points to a big-enough range. I cannot see
this as an argument to accept or reject an algorithm.
> Also, there's no point in even passing the end iterator if you're not going
> to actually use it.
The end iterator is useful to keep the same interface as std::find and
to be returned on failure. It was just the first prototype I though
of.
This find_intrusive algorithm ran 10% faster than std::find in the
worst case scenario (always match the last element), which in my
opinion is quite significant for a simple, widely-used linear search.
Marcelo
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
.
Author: "T. C." <rs2740@gmail.com>
Date: Tue, 29 Dec 2015 15:40:14 -0800 (PST)
Raw View
------=_Part_820_1351985824.1451432414587
Content-Type: multipart/alternative;
boundary="----=_Part_821_1223593847.1451432414587"
------=_Part_821_1223593847.1451432414587
Content-Type: text/plain; charset=UTF-8
On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres wrote:
>
> Hi,
>
> I would like to ask you whether a faster (and simpler) version of
> std::find,
> that tests on only one condition, has already been proposed in c++?
>
> The implementations of std::find I found in libstd++ and libcxx are
> basically
> implemented like this (simplified)
>
> for (; first != last; ++first)
> if (*first == value)
> break;
>
> Which tests two conditions (first != last) and (*first == value) to find
> the
> element.
>
> A faster and simpler version can be written testing only one condition
>
> while (*begin != value)
> ++begin;
>
> if I assume that the last element in the range [begin, end) is equal to
> "value". If we call this faster version as std::find_intrusive it could
> be used like this
>
> std::vector<int> data(size + 1); // one element more reserved to
> find_intrusive.
>
> // fills the data
>
> data.back() = value; // Sets the element we want find.
> auto iter = std::find_intrusive(std::begin(data), std::begin(data),
> value);
>
> Benchmarks showed that benchmarks are non-negligible. Do you think this
> would
> be an interesting addition to c++?
>
> Marcelo
>
This is already addressed by the ranges TS working draft, via the unreachable
sentinel.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_821_1223593847.1451432414587
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br><br>On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres =
wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8=
ex;border-left: 1px #ccc solid;padding-left: 1ex;">Hi,
<br>
<br>I would like to ask you whether a faster (and simpler) version of std::=
find,
<br>that tests on only one condition, has already been proposed in c++?
<br>
<br>The implementations of std::find I found in libstd++ and libcxx are bas=
ically
<br>implemented like this (simplified)
<br>
<br>=C2=A0 for (; first !=3D last; ++first)
<br>=C2=A0 =C2=A0 if (*first =3D=3D value)
<br>=C2=A0 =C2=A0 =C2=A0 break;
<br>
<br>Which tests two conditions (first !=3D last) and (*first =3D=3D value) =
to find the
<br>element.
<br>
<br>A faster and simpler version can be written testing only one condition
<br>
<br>=C2=A0 while (*begin !=3D value)
<br>=C2=A0 =C2=A0 ++begin;
<br>
<br>if I assume that the last element in the range [begin, end) is equal to
<br>"value". If we call this faster version as std::find_intrusiv=
e it could
<br>be used like this
<br>
<br>std::vector<int> data(size + 1); // one element more reserved to =
find_intrusive.
<br>
<br>// fills the data
<br>
<br>data.back() =3D value; // Sets the element we want find.
<br>auto iter =3D std::find_intrusive(std::<wbr>begin(data), std::begin(dat=
a), value);
<br>
<br>Benchmarks showed that benchmarks are non-negligible. Do you think this=
would
<br>be an interesting addition to c++?
<br>
<br>Marcelo
<br></blockquote><div><br></div><div>This is already addressed by the range=
s TS working draft, via the <font face=3D"courier new, monospace">unreachab=
le </font>sentinel.=C2=A0</div><div><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_821_1223593847.1451432414587--
------=_Part_820_1351985824.1451432414587--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Wed, 30 Dec 2015 10:52:41 -0800 (PST)
Raw View
------=_Part_4918_1880484302.1451501561314
Content-Type: multipart/alternative;
boundary="----=_Part_4919_888287653.1451501561314"
------=_Part_4919_888287653.1451501561314
Content-Type: text/plain; charset=UTF-8
On Tuesday, December 29, 2015 at 2:17:09 PM UTC-5, Marcelo Zimbres wrote:
>
> 2015-12-29 12:45 GMT-02:00 Nicol Bolas <jmck...@gmail.com <javascript:>>:
> >
> >
> > On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres
> wrote:
> >>
> >> Hi,
> >>
> >> I would like to ask you whether a faster (and simpler) version of
> >> std::find,
> >> that tests on only one condition, has already been proposed in c++?
> >>
> >> The implementations of std::find I found in libstd++ and libcxx are
> >> basically
> >> implemented like this (simplified)
> >>
> >> for (; first != last; ++first)
> >> if (*first == value)
> >> break;
> >>
> >> Which tests two conditions (first != last) and (*first == value) to
> find
> >> the
> >> element.
> >>
> >> A faster and simpler version can be written testing only one condition
> >>
> >> while (*begin != value)
> >> ++begin;
> >>
> >> if I assume that the last element in the range [begin, end) is equal to
> >> "value". If we call this faster version as std::find_intrusive it could
> >> be used like this
> >>
> >> std::vector<int> data(size + 1); // one element more reserved to
> >> find_intrusive.
> >>
> >> // fills the data
> >>
> >> data.back() = value; // Sets the element we want find.
> >> auto iter = std::find_intrusive(std::begin(data), std::begin(data),
> >> value);
> >>
> >> Benchmarks showed that benchmarks are non-negligible. Do you think this
> >> would
> >> be an interesting addition to c++?
> >
> >
> > It's a perfectly valid function for specialized needs. But for the C++
> > standard? No; it's just way to easy to screw up.
>
> It is also way to easy to screw up with algorithms like std::transform
> that assume an iterator points to a big-enough range. I cannot see
> this as an argument to accept or reject an algorithm.
>
There's a difference. There's absolutely no way to verify that there's a
"big-enough range" for the output. iostream output iterators, container
push-back and insertion iterators, etc, do not have a concept of a "range"
at all. You can keep inserting into them until they run out of memory;
that's the point of them.
So in order to make `transform` generalized for arbitrary kinds of output,
you *have* to take the user's word for it. This danger with
`std::transform` is *inherent* to the very idea of transforming into output
containers/streams/etc.
What you're proposing is *purely* an optimization. There is nothing
inherent about `std::find`'s functionality that requires this. Your
`find_intrusive` is not strictly necessary for the user to get the desired
functionality. It's only an optimization.
If we don't have `std::transform` (or otherwise limit it to only work on a
sized-range), then the STL has lost a valuable tool. If we don't have
`std::find_intrusive`... we simply have slower code. And even then, only in
cases where the item actually is in the list.
So adding a tool to the standard library that is dangerous, solely for
performance reasons? One who's use case is rather narrow? I don't care much
for that idea.
I'm not saying that the function is bad functionality. It's fine. But
should it be *standardized*? I don't feel that the standard is an
appropriate place for such a thing.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_4919_888287653.1451501561314
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Tuesday, December 29, 2015 at 2:17:09 PM UTC-5, Marcelo Zimbres wrote:<b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;">2015-12-29 12:45 GMT-02:00 Nicol=
Bolas <<a href=3D"javascript:" target=3D"_blank" gdf-obfuscated-mailto=
=3D"JWYuIMNJEQAJ" rel=3D"nofollow" onmousedown=3D"this.href=3D'javascri=
pt:';return true;" onclick=3D"this.href=3D'javascript:';return =
true;">jmck...@gmail.com</a>>:
<br>>
<br>>
<br>> On Tuesday, December 29, 2015 at 9:27:40 AM UTC-5, Marcelo Zimbres=
wrote:
<br>>>
<br>>> Hi,
<br>>>
<br>>> I would like to ask you whether a faster (and simpler) version=
of
<br>>> std::find,
<br>>> that tests on only one condition, has already been proposed in=
c++?
<br>>>
<br>>> The implementations of std::find I found in libstd++ and libcx=
x are
<br>>> basically
<br>>> implemented like this (simplified)
<br>>>
<br>>> =C2=A0 for (; first !=3D last; ++first)
<br>>> =C2=A0 =C2=A0 if (*first =3D=3D value)
<br>>> =C2=A0 =C2=A0 =C2=A0 break;
<br>>>
<br>>> Which tests two conditions (first !=3D last) and (*first =3D=
=3D value) to find
<br>>> the
<br>>> element.
<br>>>
<br>>> A faster and simpler version can be written testing only one c=
ondition
<br>>>
<br>>> =C2=A0 while (*begin !=3D value)
<br>>> =C2=A0 =C2=A0 ++begin;
<br>>>
<br>>> if I assume that the last element in the range [begin, end) is=
equal to
<br>>> "value". If we call this faster version as std::find=
_intrusive it could
<br>>> be used like this
<br>>>
<br>>> std::vector<int> data(size + 1); // one element more res=
erved to
<br>>> find_intrusive.
<br>>>
<br>>> // fills the data
<br>>>
<br>>> data.back() =3D value; // Sets the element we want find.
<br>>> auto iter =3D std::find_intrusive(std::<wbr>begin(data), std::=
begin(data),
<br>>> value);
<br>>>
<br>>> Benchmarks showed that benchmarks are non-negligible. Do you t=
hink this
<br>>> would
<br>>> be an interesting addition to c++?
<br>>
<br>>
<br>> It's a perfectly valid function for specialized needs. But for=
the C++
<br>> standard? No; it's just way to easy to screw up.
<br>
<br>It is also way to easy to screw up with algorithms like std::transform
<br>that assume an iterator points to a big-enough range. I cannot see
<br>this as an argument to accept or reject an algorithm.<br></blockquote><=
div><br>There's a difference. There's absolutely no way to verify t=
hat there's a "big-enough range" for the output. iostream out=
put iterators, container push-back and insertion iterators, etc, do not hav=
e a concept of a "range" at all. You can keep inserting into them=
until they run out of memory; that's the point of them.<br><br>So in o=
rder to make `transform` generalized for arbitrary kinds of output, you <i>=
have</i> to take the user's word for it. This danger with `std::transfo=
rm` is *inherent* to the very idea of transforming into output containers/s=
treams/etc.<br><br>What you're proposing is <i>purely</i> an optimizati=
on. There is nothing inherent about `std::find`'s functionality that re=
quires this. Your `find_intrusive` is not strictly necessary for the user t=
o get the desired functionality. It's only an optimization.<br><br>If w=
e don't have `std::transform` (or otherwise limit it to only work on a =
sized-range), then the STL has lost a valuable tool. If we don't have `=
std::find_intrusive`... we simply have slower code. And even then, only in =
cases where the item actually is in the list.<br><br>So adding a tool to th=
e standard library that is dangerous, solely for performance reasons? One w=
ho's use case is rather narrow? I don't care much for that idea.</d=
iv><br>I'm not saying that the function is bad functionality. It's =
fine. But should it be <i>standardized</i>? I don't feel that the stand=
ard is an appropriate place for such a thing.<br>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_4919_888287653.1451501561314--
------=_Part_4918_1880484302.1451501561314--
.
Author: "T. C." <rs2740@gmail.com>
Date: Wed, 30 Dec 2015 11:13:55 -0800 (PST)
Raw View
------=_Part_479_2029354178.1451502835343
Content-Type: multipart/alternative;
boundary="----=_Part_480_1249856041.1451502835343"
------=_Part_480_1249856041.1451502835343
Content-Type: text/plain; charset=UTF-8
On Wednesday, December 30, 2015 at 1:52:41 PM UTC-5, Nicol Bolas wrote:
>
>
> There's a difference. There's absolutely no way to verify that there's a
> "big-enough range" for the output. iostream output iterators, container
> push-back and insertion iterators, etc, do not have a concept of a "range"
> at all. You can keep inserting into them until they run out of memory;
> that's the point of them.
>
> So in order to make `transform` generalized for arbitrary kinds of output,
> you *have* to take the user's word for it. This danger with
> `std::transform` is *inherent* to the very idea of transforming into output
> containers/streams/etc.
>
>
Well, there's binary `transform` (and a few others taking
range-and-a-half), which is a little broken.
In any event, `unreachable` is a much better design.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_480_1249856041.1451502835343
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>On Wednesday, December 30, 2015 at 1:52:41 PM UTC-=
5, Nicol Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div><br>=
There's a difference. There's absolutely no way to verify that ther=
e's a "big-enough range" for the output. iostream output iter=
ators, container push-back and insertion iterators, etc, do not have a conc=
ept of a "range" at all. You can keep inserting into them until t=
hey run out of memory; that's the point of them.<br><br>So in order to =
make `transform` generalized for arbitrary kinds of output, you <i>have</i>=
to take the user's word for it. This danger with `std::transform` is *=
inherent* to the very idea of transforming into output containers/streams/e=
tc.<br><br></div></blockquote><div><br>Well, there's binary `transform`=
(and a few others taking range-and-a-half), which is a little broken.<br><=
/div><div><br></div><div>In any event, `unreachable` is a much better desig=
n.</div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_480_1249856041.1451502835343--
------=_Part_479_2029354178.1451502835343--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Wed, 30 Dec 2015 11:26:22 -0800 (PST)
Raw View
------=_Part_3938_1339694832.1451503582945
Content-Type: multipart/alternative;
boundary="----=_Part_3939_1008462279.1451503582945"
------=_Part_3939_1008462279.1451503582945
Content-Type: text/plain; charset=UTF-8
On Wednesday, December 30, 2015 at 2:13:55 PM UTC-5, T. C. wrote:
>
>
>
> On Wednesday, December 30, 2015 at 1:52:41 PM UTC-5, Nicol Bolas wrote:
>>
>>
>> There's a difference. There's absolutely no way to verify that there's a
>> "big-enough range" for the output. iostream output iterators, container
>> push-back and insertion iterators, etc, do not have a concept of a "range"
>> at all. You can keep inserting into them until they run out of memory;
>> that's the point of them.
>>
>> So in order to make `transform` generalized for arbitrary kinds of
>> output, you *have* to take the user's word for it. This danger with
>> `std::transform` is *inherent* to the very idea of transforming into output
>> containers/streams/etc.
>>
>>
> Well, there's binary `transform` (and a few others taking
> range-and-a-half), which is a little broken.
>
Oh, I'd wiped those things from my memory. Ranges to the rescue!
Too bad that v1 of the Ranges TS won't have adapters, which makes
`transform` more or less obsolete. Even the multi-range version.
> In any event, `unreachable` is a much better design.
>
I don't know that unreachable would fix the specific problem the OP's
asking about. The range equivalent of `find` would have to dereference the
iterator twice: once to see if it's at the end, and once to see if the
value is equal to the given one.
After all, the unreachable value and the find value are not required to be
the same. Of course, an optimized version of `find` could be mandated,
which, for unreachable-based ranges, checks that the `unreachable` and
search values are the same. And if so, uses a faster algorithm.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_3939_1008462279.1451503582945
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<br><br>On Wednesday, December 30, 2015 at 2:13:55 PM UTC-5, T. C. wrote:<b=
lockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;borde=
r-left: 1px #ccc solid;padding-left: 1ex;"><div dir=3D"ltr"><br><br>On Wedn=
esday, December 30, 2015 at 1:52:41 PM UTC-5, Nicol Bolas wrote:<blockquote=
class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px =
#ccc solid;padding-left:1ex"><div><br>There's a difference. There's=
absolutely no way to verify that there's a "big-enough range"=
; for the output. iostream output iterators, container push-back and insert=
ion iterators, etc, do not have a concept of a "range" at all. Yo=
u can keep inserting into them until they run out of memory; that's the=
point of them.<br><br>So in order to make `transform` generalized for arbi=
trary kinds of output, you <i>have</i> to take the user's word for it. =
This danger with `std::transform` is *inherent* to the very idea of transfo=
rming into output containers/streams/etc.<br><br></div></blockquote><div><b=
r>Well, there's binary `transform` (and a few others taking range-and-a=
-half), which is a little broken.<br></div></div></blockquote><div><br>Oh, =
I'd wiped those things from my memory. Ranges to the rescue!<br><br>Too=
bad that v1 of the Ranges TS won't have adapters, which makes `transfo=
rm` more or less obsolete. Even the multi-range version.<br>=C2=A0</div><bl=
ockquote 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><div>=
</div><div>In any event, `unreachable` is a much better design.</div></div>=
</blockquote><div><br>I don't know that unreachable would fix the speci=
fic problem the OP's asking about. The range equivalent of `find` would=
have to dereference the iterator twice: once to see if it's at the end=
, and once to see if the value is equal to the given one.<br><br>After all,=
the unreachable value and the find value are not required to be the same. =
Of course, an optimized version of `find` could be mandated, which, for unr=
eachable-based ranges, checks that the `unreachable` and search values are =
the same. And if so, uses a faster algorithm.<br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_3939_1008462279.1451503582945--
------=_Part_3938_1339694832.1451503582945--
.
Author: "T. C." <rs2740@gmail.com>
Date: Wed, 30 Dec 2015 11:35:18 -0800 (PST)
Raw View
------=_Part_658_787090679.1451504119004
Content-Type: multipart/alternative;
boundary="----=_Part_659_1645520301.1451504119005"
------=_Part_659_1645520301.1451504119005
Content-Type: text/plain; charset=UTF-8
On Wednesday, December 30, 2015 at 2:26:23 PM UTC-5, Nicol Bolas wrote:
>
>
> In any event, `unreachable` is a much better design.
>>
>
> I don't know that unreachable would fix the specific problem the OP's
> asking about. The range equivalent of `find` would have to dereference the
> iterator twice: once to see if it's at the end, and once to see if the
> value is equal to the given one.
>
> After all, the unreachable value and the find value are not required to be
> the same. Of course, an optimized version of `find` could be mandated,
> which, for unreachable-based ranges, checks that the `unreachable` and
> search values are the same. And if so, uses a faster algorithm.
>
I think you are thinking about the wrong sentinel. `unreachable` is the one
where `iter == unreachable()` always returns false.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_659_1645520301.1451504119005
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, December 30, 2015 at 2:26:23 PM UTC-5, Nicol Bolas wrote:<blo=
ckquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-=
left: 1px #ccc solid;padding-left: 1ex;"><br><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>In any event, `unreachable` is a much bette=
r design.</div></div></blockquote><div><br>I don't know that unreachabl=
e would fix the specific problem the OP's asking about. The range equiv=
alent of `find` would have to dereference the iterator twice: once to see i=
f it's at the end, and once to see if the value is equal to the given o=
ne.<br><br>After all, the unreachable value and the find value are not requ=
ired to be the same. Of course, an optimized version of `find` could be man=
dated, which, for unreachable-based ranges, checks that the `unreachable` a=
nd search values are the same. And if so, uses a faster algorithm.<br></div=
></blockquote><div><br></div><div>I think you are thinking about the wrong =
sentinel. `unreachable` is the one where `iter =3D=3D unreachable()` always=
returns false.</div><div><br></div><div><br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_659_1645520301.1451504119005--
------=_Part_658_787090679.1451504119004--
.
Author: Nicol Bolas <jmckesson@gmail.com>
Date: Wed, 30 Dec 2015 11:48:41 -0800 (PST)
Raw View
------=_Part_170_2019560368.1451504921512
Content-Type: multipart/alternative;
boundary="----=_Part_171_313830683.1451504921512"
------=_Part_171_313830683.1451504921512
Content-Type: text/plain; charset=UTF-8
On Wednesday, December 30, 2015 at 2:35:19 PM UTC-5, T. C. wrote:
>
> On Wednesday, December 30, 2015 at 2:26:23 PM UTC-5, Nicol Bolas wrote:
>>
>>
>> In any event, `unreachable` is a much better design.
>>>
>>
>> I don't know that unreachable would fix the specific problem the OP's
>> asking about. The range equivalent of `find` would have to dereference the
>> iterator twice: once to see if it's at the end, and once to see if the
>> value is equal to the given one.
>>
>> After all, the unreachable value and the find value are not required to
>> be the same. Of course, an optimized version of `find` could be mandated,
>> which, for unreachable-based ranges, checks that the `unreachable` and
>> search values are the same. And if so, uses a faster algorithm.
>>
>
> I think you are thinking about the wrong sentinel. `unreachable` is the
> one where `iter == unreachable()` always returns false.
>
Then I'm sure that it wouldn't solve his problem. His `find_intrusive`
stops based on `*iter`, not `iter` itself.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_171_313830683.1451504921512
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
On Wednesday, December 30, 2015 at 2:35:19 PM UTC-5, T. C. wrote:<blockquot=
e class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex;border-left: =
1px #ccc solid;padding-left: 1ex;">On Wednesday, December 30, 2015 at 2:26:=
23 PM UTC-5, 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"><br>=
<blockquote class=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;borde=
r-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div>In any event,=
`unreachable` is a much better design.</div></div></blockquote><div><br>I =
don't know that unreachable would fix the specific problem the OP's=
asking about. The range equivalent of `find` would have to dereference the=
iterator twice: once to see if it's at the end, and once to see if the=
value is equal to the given one.<br><br>After all, the unreachable value a=
nd the find value are not required to be the same. Of course, an optimized =
version of `find` could be mandated, which, for unreachable-based ranges, c=
hecks that the `unreachable` and search values are the same. And if so, use=
s a faster algorithm.<br></div></blockquote><div><br></div><div>I think you=
are thinking about the wrong sentinel. `unreachable` is the one where `ite=
r =3D=3D unreachable()` always returns false.</div></blockquote><div><br>Th=
en I'm sure that it wouldn't solve his problem. His `find_intrusive=
` stops based on `*iter`, not `iter` itself. <br></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_171_313830683.1451504921512--
------=_Part_170_2019560368.1451504921512--
.
Author: "T. C." <rs2740@gmail.com>
Date: Wed, 30 Dec 2015 11:52:46 -0800 (PST)
Raw View
------=_Part_284_618536999.1451505166864
Content-Type: multipart/alternative;
boundary="----=_Part_285_701084706.1451505166864"
------=_Part_285_701084706.1451505166864
Content-Type: text/plain; charset=UTF-8
On Wednesday, December 30, 2015 at 2:48:41 PM UTC-5, Nicol Bolas wrote:
>
> On Wednesday, December 30, 2015 at 2:35:19 PM UTC-5, T. C. wrote:
>>
>>
>> I think you are thinking about the wrong sentinel. `unreachable` is the
>> one where `iter == unreachable()` always returns false.
>>
>
> Then I'm sure that it wouldn't solve his problem. His `find_intrusive`
> stops based on `*iter`, not `iter` itself.
>
Huh? His concern is the first != last comparison in std::find. If you do
find(s.begin(), unreachable(), value) then that comparison (which becomes
iter != unreachable) is always true and optimizes away, leaving
*iter==value as the sole stop criteria.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at https://groups.google.com/a/isocpp.org/group/std-proposals/.
------=_Part_285_701084706.1451505166864
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><br><br>On Wednesday, December 30, 2015 at 2:48:41 PM UTC-=
5, Nicol Bolas wrote:<blockquote class=3D"gmail_quote" style=3D"margin: 0;m=
argin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">On Wednes=
day, December 30, 2015 at 2:35:19 PM UTC-5, T. C. wrote:<blockquote class=
=3D"gmail_quote" style=3D"margin:0;margin-left:0.8ex;border-left:1px #ccc s=
olid;padding-left:1ex"><div><br></div><div>I think you are thinking about t=
he wrong sentinel. `unreachable` is the one where `iter =3D=3D unreachable(=
)` always returns false.</div></blockquote><div><br>Then I'm sure that =
it wouldn't solve his problem. His `find_intrusive` stops based on `*it=
er`, not `iter` itself. <br></div></blockquote><div><br></div><div>Huh? His=
concern is the first !=3D last comparison in std::find. If you do find(s.b=
egin(), unreachable(), value) then that comparison (which becomes iter !=3D=
unreachable) is always true and optimizes away, leaving *iter=3D=3Dvalue a=
s the sole stop criteria.</div><div><br></div><div><br></div></div>
<p></p>
-- <br />
<br />
--- <br />
You received this message because you are subscribed to the Google Groups &=
quot;ISO C++ Standard - Future Proposals" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:std-proposals+unsubscribe@isocpp.org">std-proposa=
ls+unsubscribe@isocpp.org</a>.<br />
To post to this group, send email to <a href=3D"mailto:std-proposals@isocpp=
..org">std-proposals@isocpp.org</a>.<br />
Visit this group at <a href=3D"https://groups.google.com/a/isocpp.org/group=
/std-proposals/">https://groups.google.com/a/isocpp.org/group/std-proposals=
/</a>.<br />
------=_Part_285_701084706.1451505166864--
------=_Part_284_618536999.1451505166864--
.