setのlower_boundがO(NlogN)になるミス

TL;DR

set<int> st;
lower_bound( st.begin(), st.end(), 0); // これは O(NlogN)
lower_bound( 0 ); // これはO(logN)

解説

この前のABCでハマってしまった.
上のコード
下のコード

異様に遅いしlower_boundあたりがもしかして O(N) になってないか?と思って書き直したらACした. (本当はO(NlogN))
なぜかというと, 上のコードをやるとsetのメンバ関数が呼ばれないため

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

lower_bound - C++ Reference

この lower_bound が呼ばれ, O(logN) 回だけ advance(it,step); が呼ばれる.
setのiteratorはRandomAccessIteratorでないのでこれは大体 O(N), 全体では O(NlogN) かかってしまう.
気をつけような