title: std::unordered_set::erase complexity
body: <p>I don't understand, why has <em>erase</em> method of <em>std::unordered_set</em> O(N) complexity in worst case (where N is number of elements)? Standard (n4296) says what all three versions of <em>erase</em> method have O(a.size()) complexity in worst case (<em>a</em> is container), and invalidated only iterators which point to erased elements, but not all iterators (i.e. rehashing doesn't take place). This is true even for a version which takes one iterator argument and have constant complexity in average case. I think it is because that <em>erase</em> version returns an iterator to the next element, and this requires finding the first non-empty bucket after erased element, and it gives O(a.bucket_count()) complexity, but not O(a.size())!. Number of elements is not in direct ratio to the number of buckets. For example:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;unordered_set&gt;
  using namespace std;
  
  int main()
  {
      std::unordered_set&lt;int&gt; aSet;
      aSet.insert ({125, 126});
      aSet.rehash (1000);
      cout &lt;&lt; aSet.size() &lt;&lt; endl;
      cout &lt;&lt; aSet.bucket_count() &lt;&lt; endl;
  }
  </code></pre>
  
  <p>Output is</p>
  
  <pre><code>Size: 2
  Bucket count: 1031
  </code></pre>
  
  <p>The size of a container is only 2 and bucket_count is 1031. When <em>erase</em> method will be called, it will seek next non-empty bucket, which can be placed about the end, i.e. complexity is O(a.bucket_count()), but not O(a.size()). What is reason for which Standard gives O(a.size()) complexity?</p>