[multi_index] Suboptimal non-unique hash table

[vvoznesensky@…]

Computational complexity on non-unique hash table index operations are O(<number of non-unique elements for the given hash value>).

I've prepared a patch: an optional dual-linked list could be used instead of a single-linked one.

Please, find a diff in the attachment.

[voznesensky@…]

Patch to optimize hashed_non_unique index of multi_index

[Joaquín M López Muñoz]

Starting with Boost.1.56, hashed indices will use a new internal data structure allowing for O(1) erase(iterator).

​https://svn.boost.org/trac/boost/changeset/86264

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.

[vvoznesensky@…]

Sorry, Joaquin, have no time for stress-testing your great refactoring at the current period.