title: C++ Difference between std::lower_bound and std::set::lower_bound?
body: <p>Recently, while working on a programming problem in C++, I came across something interesting. My algorithm used a really large set and would use std::lower_bound on it a great deal of times. However, after submitting my solution, contrary to the math I did on paper to prove that my code was fast enough, it ended up being far too slow. The code looked something like this:</p>
  
  <pre><code>using namespace std;
  
  set&lt;int&gt; s;
  int x;
  
  //code code code
  
  set&lt;int&gt;::iterator it = lower_bound(s.begin(),s.end(),x);
  </code></pre>
  
  <p>However, after getting a hint from a buddy to use set::lower_bound, the algorithm in question worked waaaaaaaay faster than before, and it followed my math. The binary search after changing:</p>
  
  <pre><code>set&lt;int&gt;::iterator it = s.lower_bound(x);
  </code></pre>
  
  <p>My question is what's the difference between these two? Why does one work much, much faster than the other? Isn't lower_bound supposed to be a binary search function that has the complexity O(log2(n))? In my code it ended up being way slower than that.</p>