Hacker News Reader

Comment by w0mbat | Hacker News Reader

Is that still lower_bound? Maybe I am misreading the code but it looks like this returns any match, not the earliest match (when there are dupes).

It’s common to have multiple matches even in a unique list if the comparison function is say looking for a certain string prefix to do autocomplete, but we want the earliest in the list.

View on HN

You halve the remaining length each time there is a match and only exit the loop when length is 0 so it should be the first one.

I guess it’s good to have the option of not caring if you want even more speed

My lower_bound is a bit better then

  template <class ForwardIt, class T, class Compare>
  constexpr ForwardIt super_optimized_lower_bound(
        ForwardIt first, ForwardIt last, const T& value, Compare comp) {
    return first;
  }

It doesn't really work like for some cases std::lower_bound but it is super fast

Or, less contentiously - if you know you don't care/don't need to disambiguate dups, look how much efficiency you're losing on a case that isn't important.

The most common argument against optimization is "just use the existing code", but the "existing code" _always_ attempts to handle special edge cases that probably don't apply in your case. We programmers waste a lot of end-user time saving a bit of programmer time.

On the other hand, assuming it's OK to ignore the special edge cases (or not even thinking of them) can come back to bite you (or your users) when eventually one of them does show up in a situation you didn't anticipate.

Anecdotally this happens to me every time I omit an edge case. Now I try to always write a unit test for the special edge case being deliberately omitted. I just wish I could catch everything that way.

As far as I can tell it does return the earliest match. Why do you think it doesn't?

I am possibly confused, getting moreso the more I read the code. As it is ignoring the sign of the result of compare I don't even see how it would work at all. The sign is what tells you which half to throw away as you search.

Reply on news.ycombinator.com