On 4/11/2019 22:19, Zach Laine wrote:
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.
It's not much of an overhead in the implementation. Internally find is a for loop, which returns the iterator once it finds a successful value, or returns the iterator limit if the loop terminates unsuccessfully. All this would change is that on unsuccessful return it would return an empty optional. No extra branches. On successful return it would construct an optional<iterator> around its loop iterator, but that, too, should be trivial. There's no extra branches when consuming the result, either -- either way, there has to be some code that's checking for the failure state. And that code can be simpler when it's checking for an empty optional rather than checking for equality with an end iterator. It probably can be optimised better as well, since an empty optional is a known state, while list.end() is an extra method call that can't be optimised away. (Granted, the user could cache that in a variable to avoid the duplicate call, but I suspect that this is only very rarely done.)
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.
No, find (and siblings like find_if) are probably the most applicable algorithms. Correct me if I'm wrong, but most other algorithms don't have a "return input-last on failure" behaviour.
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.
Depends on the failure mode. lower_bound can return a non-last iterator which points at a non-equal element (indicating where the element could be inserted). This is what could cause unnecessary work for upper_bound, especially if it immediately goes for a binary search rather than first testing its start iterator. (It's actually the worst case for a binary search.) Admittedly an optional return isn't going to help you with that case either. Actually you can convincingly argue that lower_bound/upper_bound don't actually have a failure result -- in the case where they are currently returning last, it still means "this is where you could insert the element". So probably these should still return last, not an optional.