5 ms·
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
by w0mbat 3y ago
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.
- badtension 3y agoYou 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.
- klysm 3y agoI guess it’s good to have the option of not caring if you want even more speed
- deleted 3y ago[deleted]
- shultays 3y agoMy 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
- commandlinefan 3y agoOr, 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.
- jfk13 3y agoOn 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.
- plagiarist 3y agoAnecdotally 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.
- sltkr 3y agoAs far as I can tell it does return the earliest match. Why do you think it doesn't?
- w0mbat 3y agoI 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.