title: C++ set is slower?
body: <p>I had to use a data structure which keeps the elements in some sort of order such that
  I can query for least element and also insert new elements efficiently.So I chose
  <code>set ( C++ stl)</code> . It takes <code>log(n)</code> time for <em>insertion</em> and <code>log(n)</code> for <em>deleting</em> least element.</p>
  
  <p>So i wrote the following program:</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;set&gt;
  #include&lt;stdio.h&gt;
  using namespace std;
  int main()
  {
     set&lt;int&gt;s1,s2;
     set&lt;int&gt;::iterator it;
     int tmp,i;
     for(i=1;i&lt;=1000000;i++)s1.insert(i);
     for(i=1;i&lt;=1000000;i++)
     {
        it=s1.begin();
        s2.insert(*it);
        s1.erase(s1.begin());
     }
  return 0;
  }
  </code></pre>
  
  <p>but this takes <code>1.67</code> secs on my machine( <em>i core 3</em>) i expected much less <code>O(log(1000000)*1000000)</code> i.e. <code>2*10^7</code> i tried <em>priority queue</em> also it gave me the same performance. So should I implement my own <em>heap</em> to make it faster or there is some other way?</p>