C++ Difference between std::lower_bound and std::set::lower_bound?

std::set is typically implemented as a self-balancing tree with some list like structure tied into it. Knowing this structure, std::set::lower_bound will traverse the tree knowing the properties of the tree structure. Each step in this just means following a left or right child branch.

std::lower_bound needs to run something akin to a binary search over the data. However since std::set::iterator is bidirectional, this is much slower, a lot of increments need to be done between the checked elements. The work done between elements is thus much more intense. In this case the algorithm will check the element half way between A and B, then adjust one of A or B, find the element half way between them, and repeat.

After reading the API of std::lower_bound

On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

And I think STL set is using non-random-access iterators, so it is not doing a O(log N) binary search if using on STL set