Boost C++ Libraries: Ticket #12229: intrusive::unordered_set<T>::rehash() broken https://svn.boost.org/trac10/ticket/12229 <p> I do use the intrusive::unordered_set&lt;T&gt; to store language-dependent objects, and when the language changes, I used to use </p> <p> mymap::rehash() </p> <p> to update the buckets. Notice the bucket count does not change! </p> <p> As it is now (1.61), "fast_shrink" becomes true: </p> <blockquote> <p> const bool fast_shrink = (!incremental) &amp;&amp; (old_bucket_count &gt;= new_bucket_count) &amp;&amp; </p> <blockquote> <table class="wiki"> <tr>(power_2_buckets <td> (old_bucket_count % new_bucket_count) == 0); </td></tr></table> </blockquote> </blockquote> <p> while in the previouis version used, it was </p> <blockquote> <p> const bool fast_shrink = (!incremental) &amp;&amp; (old_bucket_count &gt; new_bucket_count) &amp;&amp; </p> <blockquote> <table class="wiki"> <tr>(power_2_buckets <td style="text-align: left">(old_bucket_count % new_bucket_count) == 0); </td></tr></table> </blockquote> </blockquote> <p> and "fast_shrink" was false. </p> <p> Due to </p> <blockquote> <p> if(same_buffer &amp;&amp; fast_shrink &amp;&amp; (n &lt; new_bucket_count)){ </p> <blockquote> <p> new_first_bucket_num = n; n = new_bucket_count; </p> </blockquote> <p> } </p> </blockquote> <p> the "n" is set to the bucket count, and the loop that is rehashing is <strong>NOT</strong> entered any more, thus rehash() does nothing any more. </p> <p> This is according to the documentation, but a change in behaviour. So I add this as as a warning that the change might cause trouble for some people. A "rehash(bucket_size+1)" still does its job, though not as optimal as the size is then not a prime any more. An optional "force_rehash" parameter or such to the rehash() function might be handy. </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/12229 Trac 1.4.3 Ion Gaztañaga Sun, 31 Jul 2016 12:17:36 GMT <link>https://svn.boost.org/trac10/ticket/12229#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12229#comment:1</guid> <description> <p> Previous behaviour was an unintended side effect. That behaviour was also broken if the hash was stored in the hook (as it would not be recalculated and stored). A new "full_rehash" function has been added in </p> <p> <a class="ext-link" href="https://github.com/boostorg/intrusive/commit/4546ffba1d8af0c97072456779a5f0d44067a43c"><span class="icon">​</span>https://github.com/boostorg/intrusive/commit/4546ffba1d8af0c97072456779a5f0d44067a43c</a> </p> <p> in order to achieve the desired "force rehash" behaviour. This function requires some invariants to be preserved (previous equal keys should produce equal hashes and previous uniqueness should be respected as otherwise rehashing will produce a broken container) so that only hashes are calculated. </p> <p> Please check the proposed solution to see if it's useful when the language is changed and a new erasure+insertion would be more expensive than just rehashing. </p> </description> <category>Ticket</category> </item> <item> <author>boost@…</author> <pubDate>Thu, 10 Nov 2016 09:04:45 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/12229#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/12229#comment:2</guid> <description> <p> Thank you very much for implementing/correcting. Sorry it took some time, but I can confirm that it works as intended. Great service! </p> </description> <category>Ticket</category> </item> </channel> </rss>