std::binary_find

[Ralf Goertz]

Hi,

is there a reason why there is no function "std::binary_find" which has
an interface like "std::find" but takes advantage of the fact that the
input is sorted? At least I have found no such function. Of course
std::set.find could be an option but I guess its performance is much
worse than that of a binary_find in a sorted vector.

[leigh.v....@googlemail.com]

std::lower_bound

/Leigh

[Ralf Goertz]

Am Wed, 28 Nov 2018 03:04:48 -0800 (PST)
schrieb leigh.v....@googlemail.com:

"Returns an iterator pointing to the first element in the range [first,
last) that is not less than (i.e. greater or equal to) value, or last if
no such element is found."

So I still need to check that the element pointed to is actually the one
I was looking for. Given the redundancy in <algorithm> (e.g.
std::find_if and std::find_if_not) the existence of st::lower_bound is
not a good enough reason not to have std::binary_find.

[leigh.v....@googlemail.com]

On Wednesday, November 28, 2018 at 10:44:58 AM UTC, Ralf Goertz wrote:

std::lower_bound and std::upper_bound are perfectly adequate for doing the job of your "binary_find" which is not needed.

/Leigh

[leigh.v....@googlemail.com]

On Wednesday, November 28, 2018 at 10:44:58 AM UTC, Ralf Goertz wrote:

There is also std::equal_range

/Leigh

[James Kuyper]

On 11/28/18 05:44, Ralf Goertz wrote:
> Hi,
>
> is there a reason why there is no function "std::binary_find" which has
> an interface like "std::find" but takes advantage of the fact that the
> input is sorted? At least I have found no such function.

Just to confirm: you're looking for a standard function with behavior
equivalent to:


template<class ForwardIterator, class T>
ForwardIterator binary_find(
ForwardIterator first,
ForwardIterator last, const T& value)
{
ForwardIterator iter =
lower_bound(first, last, value);
if(iter !=last && *iter == value)
return iter;
return last;
}


> ... Of course

> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.

Both should be logarithmic, but I could imagine that std::set::find()
might be slower - but that only matters if you're free to choose your
data structure based solely upon this one operation. Whether you use
std::set or a sorted vector should also depend on how you'll be
initializing and modifying the contents of your container, and that's
often the determining issue, unless you will be searching the container
far more often than you modify its contents.

[Juha Nieminen]

Ralf Goertz <m...@myprovider.invalid> wrote:
>> std::lower_bound
>
> "Returns an iterator pointing to the first element in the range [first,
> last) that is not less than (i.e. greater or equal to) value, or last if
> no such element is found."
>
> So I still need to check that the element pointed to is actually the one
> I was looking for. Given the redundancy in <algorithm> (e.g.
> std::find_if and std::find_if_not) the existence of st::lower_bound is
> not a good enough reason not to have std::binary_find.

In principle the main idea behind std::lower_bound and std::upper_bound
is that you can insert the searched element at the place pointed by
the iterator they return, and the container will remain sorted.
(Their difference is that with std::lower_bound the new element will
be inserted before any possibly existing element that's equal to the
searched one, while with std::upper_bound it will be inserted after any
such element.) They don't really take a stance on whether an equal element
already exists in the container.

With std::lower_bound you can check the element pointed by the returned
iterator to see if it's equal to the searched one.

[Ralf Goertz]

Am Wed, 28 Nov 2018 07:44:05 -0500
schrieb James Kuyper <james...@alumni.caltech.edu>:

> On 11/28/18 05:44, Ralf Goertz wrote:
> > Hi,
> >
> > is there a reason why there is no function "std::binary_find" which
> > has an interface like "std::find" but takes advantage of the fact
> > that the input is sorted? At least I have found no such function.
>
> Just to confirm: you're looking for a standard function with behavior
> equivalent to:
>
>
> template<class ForwardIterator, class T>
> ForwardIterator binary_find(
> ForwardIterator first,
> ForwardIterator last, const T& value)
> {
> ForwardIterator iter =
> lower_bound(first, last, value);
> if(iter !=last && *iter == value)
> return iter;
> return last;
> }

Yes, and that is exactly how I implemented it (after looking at
std::binary_search). And I am curious as to why I had to do that. The
fact that it is not so difficult to implement can hardly be the reason
not to provide it. std::binary_search is almost as easy as that but it
is provided by the standard. I guess the need for finding the actual
position of the element is not unreasonable, it is one of the reasons I
don't want to use std::set because std::distance(first, iter) is also
not that trivial.

>
> > ... Of course
> > std::set.find could be an option but I guess its performance is much
> > worse than that of a binary_find in a sorted vector.
>
> Both should be logarithmic, but I could imagine that std::set::find()
> might be slower - but that only matters if you're free to choose your
> data structure based solely upon this one operation. Whether you use
> std::set or a sorted vector should also depend on how you'll be
> initializing and modifying the contents of your container, and that's
> often the determining issue, unless you will be searching the
> container far more often than you modify its contents.

Exactly. I love std::set but in my use case it is not appropriate.

[Öö Tiib]

On Wednesday, 28 November 2018 12:44:58 UTC+2, Ralf Goertz wrote:
> Hi,
>
> is there a reason why there is no function "std::binary_find" which has
> an interface like "std::find" but takes advantage of the fact that the
> input is sorted? At least I have found no such function.

It sounds too close to std::lower_bound or std::equal range
to matter.
Positive side of std::lower_bound is that it gives the place
where to insert when an element was not found. That is
actually quite common need.

> Of course
> std::set.find could be an option but I guess its performance is much
> worse than that of a binary_find in a sorted vector.

That can't be sure until measured. Also the std::unordered_set::find
can be even better. Performance of concrete use-case is still
somewhat predictable but typically every container participates
in several use-cases and what is best for one use-case can be
worst for other.

[Alf P. Steinbach]

Don't know, but I regard as a design level defect that
¹`std::binary_search` discards the information about where it found the
specified value, and only returns a `bool`. Nonsensical design IMHO. :(

Cheers!,

- Alf

Notes:
¹ `https://en.cppreference.com/w/cpp/algorithm/binary_search

[Juha Nieminen]

Öö Tiib <oot...@hot.ee> wrote:
> Positive side of std::lower_bound is that it gives the place
> where to insert when an element was not found. That is
> actually quite common need.

Nothing stops you from inserting the element at the returned
position even if an equal element already exists. The container
will still be sorter afterwards.