title: What's the time complexity of std::lower_bound with std::set?
body: <p>I know that there is <code>std::set::lower_bound</code> and the time complexity is <code>O(log)</code>, and i see that <code>std::lower_bound</code> is much slower than <code>std::set::lower_bound</code> when operates on <code>std::set</code>.</p>
  
  <p>I googled and found this:</p>
  
  <p><a href="http://en.cppreference.com/w/cpp/algorithm/lower_bound" rel="noreferrer">http://en.cppreference.com/w/cpp/algorithm/lower_bound</a>
  <a href="http://en.cppreference.com/w/cpp/iterator/advance" rel="noreferrer">http://en.cppreference.com/w/cpp/iterator/advance</a></p>
  
  <p>so it's clear that because of the <code>std::advance</code> is linear for <code>set::iterator</code>, the whole <code>std::lower_bound</code> takes up to <code>O(n)</code>.</p>
  
  <p>However, it runs much faster than <code>O(n)</code> when i use it(and so did some friends say), can anybody explain why or tell me it's just not like that.</p>