Lower/upper_bound functions

IR & Optimizations
,
1

Hello! If you read standard, it says that complexity is linear for non-random-access iterators. And, yes, it is written quite clear, but even in strong companies people make this mistakes
(Google: [bugfix] Use std::set::lower_bound instead of std::lower_bound for improved performance by KaurkerDevourer · Pull Request #54320 · tensorflow/tensorflow · GitHub, Intel: Fix DpSeamFinder::hasOnlyOneNeighbor by KaurkerDevourer · Pull Request #21598 · opencv/opencv · GitHub)
But, in modern C++, we got strong instrument - concepts.
We can write something like
concept HasMethod = requires(S a, T b) { a.lower_bound(b);}
and just call method, if it exists.
Everyone understand, that calling lower_bound function for map/set is just a mistake and this is a way we can fix it. But, something tells me, that it wouldn’t be implemented. I am just interested - why?
Or, there is nothing blocking and I can make a pull request?

2

I don’t think there’s any reason we wouldn’t want a warning for that; we have warnings for other misuses of the standard library.

3

Should I use Diagnostic flags in Clang — Clang 17.0.0git documentation -Wmisexpect?
Or is there a better warning? And, I am so sorry, can I see anyone committed any warning like this?
Because it sounds like static_warning, but there is no such a thing

4

I think it might be a good clang-tidy diagnostic with the automatic fix

1 Like
5

Can you give me an example of any similar one? I am a bit lost in code and llvm’s commit system =)

6

Actually, there is already a check that does exactly this:
https://clang.llvm.org/extra/clang-tidy/checks/performance/inefficient-algorithm.html

Yet, I’m not sure that it is able to catch the *_bound algorithms problem

1 Like