Topic: Any plans for binary_find ?
Author: nx02columbia@gmail.com
Date: Tue, 9 Apr 2013 07:12:17 -0700 (PDT)
Raw View
------=_Part_70_4665573.1365516737543
Content-Type: text/plain; charset=ISO-8859-1
Hi,
some ppl(for eg. Herb) dont like that binary_search returns bool.
Any plans to add function that operates on sorted range and returns a
iterator?
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
------=_Part_70_4665573.1365516737543
Content-Type: text/html; charset=ISO-8859-1
Hi, <br>some ppl(for eg. Herb) dont like that binary_search returns bool. <br>Any plans to add function that operates on sorted range and returns a iterator? <br>
<p></p>
-- <br />
<br />
--- <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 email to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en">http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en</a>.<br />
<br />
<br />
------=_Part_70_4665573.1365516737543--
.
Author: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= <daniel.kruegler@gmail.com>
Date: Tue, 9 Apr 2013 16:57:48 +0200
Raw View
2013/4/9 <nx02columbia@gmail.com>:
> Hi,
> some ppl(for eg. Herb) dont like that binary_search returns bool.
> Any plans to add function that operates on sorted range and returns a
> iterator?
I haven't heard of such plans.
- Daniel
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
.
Author: kosta-chrome@ks-baumann.de
Date: Tue, 9 Apr 2013 13:08:52 -0700 (PDT)
Raw View
What is wrong with lower_bound and upper_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.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
.
Author: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= <daniel.kruegler@gmail.com>
Date: Tue, 9 Apr 2013 22:16:45 +0200
Raw View
2013/4/9 <kosta-chrome@ks-baumann.de>:
> What is wrong with lower_bound and upper_bound?
In general: Nothing. But they are not an exact replacement for
binary_find: lower/upper_bound don't return the past-the-end iterator,
when they don't find the value exactly. The usual trick is to apply
the predicate on the dereferencable result (if not past-the-end), and
if equivalence does not exist, to return the past-the-end value.
Personally I have only rarely missed binary_find (I think around two
times) and I usually can get away with the two *_bound functions.
- Daniel
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
.
Author: Greg Marr <gregmmarr@gmail.com>
Date: Tue, 9 Apr 2013 13:37:52 -0700 (PDT)
Raw View
------=_Part_419_428444.1365539872754
Content-Type: text/plain; charset=ISO-8859-1
> In general: Nothing. But they are not an exact replacement for
> binary_find: lower/upper_bound don't return the past-the-end iterator,
> when they don't find the value exactly.
i use std::equal_range here. If ret.first == ret.second, then the item
wasn't found.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
------=_Part_419_428444.1365539872754
Content-Type: text/html; charset=ISO-8859-1
<br><blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;">In general: Nothing. But they are not an exact replacement for
<br>binary_find: lower/upper_bound don't return the past-the-end iterator,
<br>when they don't find the value exactly.</blockquote><div><br></div><div>i use std::<span style="font-size: 13px;">equal_range here. If ret.first == ret.second, then the item wasn't found.</span></div><div><br></div>
<p></p>
-- <br />
<br />
--- <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 email to std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href="http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en">http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en</a>.<br />
<br />
<br />
------=_Part_419_428444.1365539872754--
.
Author: =?ISO-8859-1?Q?Daniel_Kr=FCgler?= <daniel.kruegler@gmail.com>
Date: Tue, 9 Apr 2013 23:43:11 +0200
Raw View
2013/4/9 Greg Marr <gregmmarr@gmail.com>:
>
>> In general: Nothing. But they are not an exact replacement for
>> binary_find: lower/upper_bound don't return the past-the-end iterator,
>> when they don't find the value exactly.
>
> i use std::equal_range here. If ret.first == ret.second, then the item
> wasn't found.
This works, but potentially performs a lower_bound call over [f, l)
plus an upper_bound_call over [f, l). Ideally you only need a
lower_bound call over [f, l) plus a single predicate test - the last
one only in 50% of all cases.
- Daniel
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
.
Author: Greg Marr <gregmmarr@gmail.com>
Date: Tue, 9 Apr 2013 15:41:10 -0700 (PDT)
Raw View
------=_Part_686_3749566.1365547270524
Content-Type: text/plain; charset=ISO-8859-1
> This works, but potentially performs a lower_bound call over [f, l)
> plus an upper_bound_call over [f, l). Ideally you only need a
> lower_bound call over [f, l) plus a single predicate test - the last
> one only in 50% of all cases.
>
In VC++10, it's a binary search over [f, l) to find some value m where both
*m < v and v < *m are false, then lower_bound of [f, m) and upper_bound of
[m, e). So yes it more expensive, both in terms of how much of the range
is searched, and how many comparisons on each step.
A binary_find would definitely be better, just like Daniel wrote:
template<typename Iter, typename T>
Iter binary_find(Iter b, Iter e, T const &v)
{
auto i = std::lower_bound(b, e, v);
return(((i == e) || (*i == v)) ? e : i);
}
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
------=_Part_686_3749566.1365547270524
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
<br><blockquote class=3D"gmail_quote" style=3D"margin: 0;margin-left: 0.8ex=
;border-left: 1px #ccc solid;padding-left: 1ex;">This works, but potentiall=
y performs a lower_bound call over [f, l)
<br>plus an upper_bound_call over [f, l). Ideally you only need a
<br>lower_bound call over [f, l) plus a single predicate test - the last
<br>one only in 50% of all cases.
<br></blockquote><div> </div><div><span style=3D"font-size: 13px;">In =
VC++10, it's a binary search over [f, l) to find some value m where both *m=
< v and v < *m are false, then lower_bound of [f, m) and upper_bound=
of [m, e). So yes it more expensive, both in terms of how much of th=
e range is searched, and how many comparisons on each step.</span></div><di=
v><span style=3D"font-size: 13px;"><br></span></div><div><span style=3D"fon=
t-size: 13px;">A binary_find would definitely be better, just like Daniel w=
rote:</span></div><div><span style=3D"font-size: 13px;"><br></span></div><d=
iv><div>template<typename Iter, typename T> </div><div>Iter bina=
ry_find(Iter b, Iter e, T const &v)</div><div> {</div><div=
> auto i =3D std::lower_bound(b, e, v);</div><div>  =
; return(((i =3D=3D e) || (*i =3D=3D v)) ? e : i);</div><div> =
}</div><div style=3D"font-size: 13px;"><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 std-proposals+unsubscribe@isocpp.org.<br />
To post to this group, send email to std-proposals@isocpp.org.<br />
Visit this group at <a href=3D"http://groups.google.com/a/isocpp.org/group/=
std-proposals/?hl=3Den">http://groups.google.com/a/isocpp.org/group/std-pro=
posals/?hl=3Den</a>.<br />
<br />
<br />
------=_Part_686_3749566.1365547270524--
.
Author: Bjorn Reese <breese@mail1.stofanet.dk>
Date: Wed, 10 Apr 2013 11:44:44 +0200
Raw View
On 04/09/2013 04:12 PM, nx02columbia@gmail.com wrote:
> Any plans to add function that operates on sorted range and returns a
> iterator?
Just adding another idea. How about a binary_sort, which sorts the data
according to the binary (or any other) traversal order? In other words,
it sorts the data according to its comparator as usual, but the data is
stored in a traversal order. This means that if you iterate through the
sorted container from begin() to end() then you will get the elements
as if you were traversing the normally-sorted container with a binary
search. This could be useful for cache-oblivious algorithms.
A bit like std::priority_queue, except this happens at sort time, not
at insertion time.
--
---
You received this message because you are subscribed to the Google Groups "ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to std-proposals+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/?hl=en.
.