Boost C++ Libraries: Ticket #5787: [multi_index] Suboptimal non-unique hash table https://svn.boost.org/trac10/ticket/5787 <p> Computational complexity on non-unique hash table index operations are O(&lt;number of non-unique elements for the given hash value&gt;). </p> <p> I've prepared a patch: an optional dual-linked list could be used instead of a single-linked one. </p> <p> Please, find a diff in the attachment. </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/5787 Trac 1.4.3 voznesensky@… Tue, 16 Aug 2011 11:51:31 GMT attachment set https://svn.boost.org/trac10/ticket/5787 https://svn.boost.org/trac10/ticket/5787 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">optimize_multi_index.patch</span> </li> </ul> <p> Patch to optimize hashed_non_unique index of multi_index </p> Ticket Joaquín M López Muñoz Thu, 17 Oct 2013 09:17:59 GMT <link>https://svn.boost.org/trac10/ticket/5787#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/5787#comment:1</guid> <description> <p> Starting with Boost.1.56, hashed indices will use a new internal data structure allowing for O(1) erase(iterator). </p> <p> <a class="ext-link" href="https://svn.boost.org/trac/boost/changeset/86264"><span class="icon">​</span>https://svn.boost.org/trac/boost/changeset/86264</a> </p> <p> A preview can be obtained by just downloading from the current Boost trunk branch. Any feedback on the performance within real-life scenarios is greatly appreciated. Waiting to such feedback before closing the bug. </p> </description> <category>Ticket</category> </item> <item> <author>vvoznesensky@…</author> <pubDate>Thu, 17 Oct 2013 10:13:10 GMT</pubDate> <title/> <link>https://svn.boost.org/trac10/ticket/5787#comment:2 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/5787#comment:2</guid> <description> <p> Sorry, Joaquin, have no time for stress-testing your great refactoring at the current period. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Joaquín M López Muñoz</dc:creator> <pubDate>Fri, 29 Nov 2013 19:59:14 GMT</pubDate> <title>status changed; resolution set https://svn.boost.org/trac10/ticket/5787#comment:3 https://svn.boost.org/trac10/ticket/5787#comment:3 <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> Ticket