Boost logo

Boost Users :

From: Zach Laine (whatwasthataddress_at_[hidden])
Date: 2019-11-04 09:19:16


On Sun, Nov 3, 2019 at 10:24 PM Gavin Lambert via Boost-users <
boost-users_at_[hidden]> wrote:

> On 2/11/2019 04:34, Zach Laine wrote:
> > This is a red herring; if you only care about existence, why are you
> > using find()? Use any_of() or C++20's includes() (for detecting
> > subranges) instead. They each return a bool. Moreover, just knowing
> > whether a value is found at all within a subrange via linear search is a
> > corner case -- usually you will use something with O(log(N)) or faster
> > access if you need to do that operation a lot.
>
> I'm using find because you said to use find. :)
>

Right, that's true. However, I did ask you to use it like that. :)

The thing I was going for, in part, was that you show the definition,
which would have included a branch, necessary for initializing/not
initializing the optional, which is not necessary in the general case.

> But yes, the argument applies to map.find and friends as well -- and
> would probably be more useful there than for std::find itself. "Is key
> present in map" is a very common query.
>
> (Granted, map.contains has been added in C++20, but most people don't
> have access to that yet.)
>

True enough, but that is a special case, since any_of() does not work
optimally with trees. If you have a flat tree, you can use
std::binary_search() too. My point is that the algorithms already support
the use cases you care about that are related to find(). If you have
another algorithm that you find to be a better example for what you're
trying to show, we can discuss that one.

> > If I had to write that code using your approach, it would suffer. All
> > I'm pointing out here is that the change you propose is not universally
> > better. In fact, it is universally worse if what you want to do is
> > search for a subrange:
> >
> > auto lower = std::lower_bound(c.begin(), c.end(), 42);
> > out = std::copy(lower, std::upper_bound(lower, c.end(), 42), out);
> >
> > Or:
> >
> > out = std::ranges::copy(std::ranges::equal_range(c, 42), out);
> >
> > That turns in to a real mess when the iterators returned are optionals.
>
> I don't really like the former example anyway because you're not
> checking for failure of lower_bound.

Well, that was the point of that example -- I don't have to.

> Granted, it will end up with an
> empty range in the end so the result will still be correct, but you're
> potentially wasting some time in upper_bound.
>

No. upper_bound() will go into the first iteration of its loop with a
false condition (first != last will not be true). If I had checked for
failure of lower_bound() I would just be pessimizing the non-failure case
with an extra branch.

> In the second example it would return an empty range either way, so
> there's not really any difference.
>

The first and second examples have the same semantics and will probably
generate nearly identical object code.

As importantly, they are simple to read and understand. There is no
checking-for-failure noise, nor is there the opportunity for bugs if I
forget to check for failure.

Zach



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net