Dominique Pelle - 2022-05-28

Calling the std::equal_range() algorithm on a std::set or std::list container is silly. It's worse than O(n) complexity since std::equal_range() will internally call std::distance() and std::advance() which are both O(n) on a std::set or std::list, and they will be called O(log(n)) times, so the complexity ought to be n*log(n) which is worse than linear complexity.

Yet it compiles fine and cppcheck does not detect any issue as in this silly example:

$ cat $ cat foo.cpp
#include <algorithm>
#include <iostream>
#include <set>

void foo(std::set<int> s) {
  const auto r = std::equal_range(s.begin(), s.end(), 42); // Slow!

  for (auto it = r.first; it != r.second; ++it) {
    std::cout << *it << "\n";
  }
}

$ clang++-14 -Wall -Wpedantic -std=c++11 -c -O0 foo.cpp
$ cppcheck --inconclusive --enable=all foo.cpp
(bug not found)

This was with the latest cppcheck in git (SHA1 16a4449901d5401cbc2db9be93d4208ef2542844 from May 28, 2022).

At least clang-tidy-14 detects it as it says:

foo.cpp:6:18: error: this STL algorithm call should be replaced with a container method [performance-inefficient-algorithm,-warnings-as-errors]
  const auto r = std::equal_range(s.begin(), s.end(), 42);
                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                 s.equal_range(42)