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