Re: Interest in a Unicode library for Boost?

From: Gavin Lambert (boost_at_[hidden])
Date: 2019-11-04 22:28:58

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.