https://svn.boost.org/trac10/ticket/3693 <p> Recently raised on the Developers mailing list is the issue that <code>unordered_set::erase(iterator)</code> has complexity O(bucket_count): <a class="ext-link" href="http://lists.boost.org/Archives/boost/2009/11/159116.php"><span class="icon">​</span>http://lists.boost.org/Archives/boost/2009/11/159116.php</a> </p> <p> The same issue came up just three weeks ago on the GCC bug tracker: <a class="ext-link" href="http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975"><span class="icon">​</span>http://gcc.gnu.org/bugzilla/show_bug.cgi?id=41975</a> </p> <p> It was also warned about in 2006: <a class="ext-link" href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf"><span class="icon">​</span>http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2023.pdf</a> </p> <p> Slightly related, a change to Boost.MultiIndex (made by the author of n2023): <a class="changeset" href="https://svn.boost.org/trac10/changeset/33914" title="rewritten erase(key) to avoid implicit iterator increments leading to ...">33914</a> </p> <p> Daniel James suggested in the Developers thread that I should file this ticket. My desired outcome is the ability to erase by iterator from an <code>unordered_set</code> or <code>unordered_map</code> in constant time. The name of the method is not important to me; I suggested <code>erase_fast</code> or <code>erase_void</code> just to get the ball rolling. </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/3693 Trac 1.4.3 anonymous Sun, 29 Nov 2009 02:32:54 GMT https://svn.boost.org/trac10/ticket/3693#comment:2 https://svn.boost.org/trac10/ticket/3693#comment:2 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> Fixed in <a class="changeset" href="https://svn.boost.org/trac10/changeset/58403" title="Implement an alternative erase function that doesn't return an ...">[58403]</a> on trunk, <a class="changeset" href="https://svn.boost.org/trac10/changeset/58605" title="Merge unordered.">[58605]</a> on release. I called it <code>erase_return_void</code>. </p> Ticket anonymous Sun, 28 Feb 2010 17:03:26 GMT https://svn.boost.org/trac10/ticket/3693#comment:3 https://svn.boost.org/trac10/ticket/3693#comment:3 <ul> <li><strong>status</strong> <span class="trac-field-old">closed</span> → <span class="trac-field-new">reopened</span> </li> <li><strong>resolution</strong> <span class="trac-field-deleted">fixed</span> </li> </ul> <p> reopening this because there appears now to be a consensus to change the result of erase() to "void": <a class="ext-link" href="http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579"><span class="icon">​</span>http://home.roadrunner.com/~hinnant/issue_review/lwg-active.html#579</a> </p> Ticket anonymous Sun, 28 Feb 2010 17:05:53 GMT https://svn.boost.org/trac10/ticket/3693#comment:5 https://svn.boost.org/trac10/ticket/3693#comment:5 <ul> <li><strong>status</strong> <span class="trac-field-old">reopened</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">fixed</span> </li> </ul> <p> I've created a new ticket (<a class="closed ticket" href="https://svn.boost.org/trac10/ticket/3966" title="#3966: Bugs: Rename `erase_return_void` to `quick_erase`. (closed: fixed)">#3966</a>) for this. </p> Ticket Daniel James Sun, 28 Feb 2010 17:23:30 GMT