title: Why does the 32769th insert fail in std::unordered_set?
body: <p>I generate a large number of class instances and store them in a <code>std::unordered_set</code>. I have defined a hash function and an equality relation, and so far everything works as it should - I insert 10000 instances with <code>unordered_set::insert</code>, and I can find them with <code>unordered_set::find</code>. All the objects are undamaged, and there is no hint on memory corruption or any other issue.</p>
  
  <p>However, when I keep inserting, <strong>the 32769th insert fails</strong> - it doesn't throw, but it returns a pair where the iterator is <code>== nullptr</code> (0x00000000). <code>insert</code> is defined as:</p>
  
  <pre><code>pair&lt;iterator, bool&gt; insert(const value_type&amp; Val);
  </code></pre>
  
  <p>and normally, the <code>*iterator</code> is the key I inserted, and the bool is <code>true</code>.<br>
  If I (after the error) try to find the object, it <em>is</em> in the set; if I try to insert it again, it tells me its already there; so the insert seems to have worked fine. Just the returned value is <code>pair&lt;nullptr,true&gt;</code> instead <code>pair&lt;iterator,bool&gt;</code>.<br>
  Note that if I hand-fill the iterator and continue in the debugger, the same issue happens again at the first insert after 65536, and then at 131072, etc. (so for 2^15+1, 2^16+1, 2^17+1, ...) - but not at 3 * 32768+1, etc.</p>
  
  <p>To me, this looks like some <code>short</code> overflow. Maybe my hashes are really bad and lead to uneven filling of buckets, and at 32768 it runs out of buckets? I could not find anything more detailed about such a limit when googling, and I don't know enough about balanced trees or whatever this is internally.<br>
  Still, the std library code should be able to handle bad hashing, I understand if it gets slow and inefficient, but it shouldn't <em>fail</em>.</p>
  
  <p><strong>Question: Why do the 2^15th+1, 2^16th+1, etc. inserts fail, and how can I avoid it?</strong></p>
  
  <p>This is in Microsoft Visual Studio 2017  V15.7.1 (latest version as of 2018-05-15). Compiler is set to use C++2017 rules, but I doubt it makes any impact.<br>
  I cannot paste the complete code for a minimum viable solution, as the object generation is complex across multiple classes and methods, and has several hundreds lines of code, the generated hashes obviously depend on the details of the objects, and are not easily reproducible in dummy code.</p>
  
  <p><strong>### Update after one day ###</strong>: (I cannot put this in an answer, because the q was put on hold)
  After extensive debugging of the standard library (including a lot of head-scratching), @JamesPoag's answer turns out to point to the right thing.<br>
  After <code>n</code> inserts, I get:</p>
  
  <pre><code>  n     load_factor  max_load_factor  bucket_count  max_bucket_count
  32766   0.999938965  1.00000000       32768         536870911 (=2^29-1)
  32767   0.999969482  1.00000000       32768         536870911
  32768   1.000000000  1.00000000       32768         536870911
  32769   0.500000000  1.00000000       65536         536870911
  </code></pre>
  
  <p>not surprising, after 32768 inserts, the load factor has reached its maximum. The 32769th insert triggers a rehash to bigger table, inside the internal method  _Check_Size:</p>
  
  <pre><code>void _Check_size()
          {    // grow table as needed
          if (max_load_factor() &lt; load_factor())
  
              {    // rehash to bigger table
              size_type _Newsize = bucket_count();
  
              if (_Newsize &lt; 512)
                  _Newsize *= 8;    // multiply by 8
              else if (_Newsize &lt; _Vec.max_size() / 2)
                  _Newsize *= 2;    // multiply safely by 2
              _Init(_Newsize);
              _Reinsert();
              }
          }
  </code></pre>
  
  <p>at the end, <code>_Reinsert()</code> is called and fills all 32769 keys into the new buckets, and _sets all the <code>_next</code> and <code>_prev</code> pointers accordingly. That works fine.<br>
  However, the code that is calling those two looks like this (<code>Plist</code> is <em>my</em> set's name, this code gets generated from a template):</p>
  
  <pre><code>_Insert_bucket(_Plist, _Where, _Bucket);
  
  _TRY_BEGIN
  _Check_size();
  _CATCH_ALL
  erase(_Make_iter(_Plist));
  _RERAISE;
  _CATCH_END
  
  return (_Pairib(_Make_iter(_Plist), true));
  }
  </code></pre>
  
  <p>The critical point is in the last line - _Plist is used to build the pair, but it holds a now dead pointer to <code>_next</code>, because all bucket's addresses were rebuild in <code>_Check_size()</code>, some lines earlier.
  I think this is an error in the std library - here it needs to find <code>_Plist</code> in the new set, where it looks the same, but has a valid <code>_next</code> pointer.</p>
  
  <p>An easy 'fix' is (verified to work) to expand the set right before the critical <code>insert</code>:<br>
  <code>if (mySet.size() == mySet.bucket_count()) mySet.rehash(mySet.bucket_count() * 2);</code>.</p>
  
  <p><strong>### Further Update: ###</strong>
  I have been trying extensively (16+ hours) to produce a <em>minimum code</em> that reproduces the issue, but I was not yet able to. I'll try to log the actual calculated hashes for the existing large code.<br>
  One thing I found is that one hash value of one of the keys <em>changed</em> (unintentionally) between being inserted and being rehashed. This <em>might</em> be the root cause; if I move the rehashing outside of the insert, the issue is gone.<br>
  I am not sure if there is a rule that hashes have to be constant, but it probably makes sense, how else could you find the key again.</p>