title: Why unordered_multiset works bad for many equal keys
body: <p>I have this piece of code:</p>
  
  <pre><code>unordered_multiset&lt;int&gt; t;
  for (int i = 0; i &lt; 1000000; i++) {
      if (i % 10000 == 0)
          cout &lt;&lt; i &lt;&lt; endl;
  
      t.insert(10);
  }
  </code></pre>
  
  <p>So it just puts a lot of equal elements in an <code>unordered_multiset</code>. But I found out that the more elements I have in hash more slower this works? And I cannot realize the reason. In my opinion after applying the hash function and finding equal element's bucket (since all equal elements are grouped together) stl just put them at the end of bucket.</p>
  
  <p>So what's wrong here?</p>
  
  <p>Udp:
  I found the the description of unordered_multiset::insert function</p>
  
  <blockquote>
    <p>Single element insertions:
    Average case: constant.
    Worst case: linear in container size.</p>
  </blockquote>
  
  <p>So the question now can be rephrased as: "Why the worst case is linear"</p>