Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop

[Anton Kryukov <akryuk@…>]

I create an intrusive unordered_multiset and insert multiple elements with the same key into it. When I try to erase an element through an iterator, like so:

ms.erase(ms.iterator_to(elem));

, the erase function never returns.

I use Microsoft Visual Studio 2010. Ran into this problem with boost 1.51, and verified that it still exists in 1.56. Same code seems to run fine with optimize_multikey<false>. Here's the complete code:

#include <boost/intrusive/unordered_set.hpp>
#include <iostream>

using namespace boost::intrusive;
//------------------------------------------------------------------------
struct MyClass
{
  typedef unordered_set_member_hook<optimize_multikey<true> > MultisetHook;

  int id_;
  int key_;
  MultisetHook byKeyHook_;

  friend bool operator== (const MyClass &lhs, const MyClass &rhs) 
  {  return lhs.key_ == rhs.key_;  }

  friend std::size_t hash_value(const MyClass &v) 
  {  return std::size_t(v.key_); }
};
//------------------------------------------------------------------------
typedef member_hook<
  MyClass, 
  MyClass::MultisetHook, 
  &MyClass::byKeyHook_> MyHook;

typedef unordered_multiset<MyClass, MyHook> Multiset;
//------------------------------------------------------------------------
size_t const NUM_BUCKETS = 32;
size_t const NUM_RECS = 10;
//------------------------------------------------------------------------
int main(int argc, char* argv[])
{
  Multiset::bucket_type buckets[NUM_BUCKETS];
  Multiset ms(Multiset::bucket_traits(buckets, NUM_BUCKETS)); 
  MyClass recs[NUM_RECS];

  for (size_t i = 0; i != NUM_RECS; ++i)
  {
    MyClass & rec = recs[i];
    rec.id_ = i;
    rec.key_ = i < 6 ? 123 : 456;
    ms.insert(rec);
  }

  std::cerr << "--- before erase ---\n";
  for (auto it = ms.begin(), endIt = ms.end(); it != endIt; ++it)
  {
    std::cerr << "rec " << it->id_ << " key=" << it->key_ << std::endl;
  }

  {
    MyClass & rec = recs[4];
    std::cerr << "--- erasing rec " << rec.id_ << " ---\n";
    // Stuck in the following erase
    ms.erase(ms.iterator_to(rec));
  }

  std::cerr << "--- after erase ---\n";
  for (auto it = ms.begin(), endIt = ms.end(); it != endIt; ++it)
  {
    std::cerr << "rec " << it->id_ << " key=" << it->key_ << std::endl;
  }

	return 0;
}

And here's the output:

--- before erase ---
rec 6 key=456
rec 9 key=456
rec 8 key=456
rec 7 key=456
rec 0 key=123
rec 5 key=123
rec 4 key=123
rec 3 key=123
rec 2 key=123
rec 1 key=123
--- erasing rec 4 ---

[Ion Gaztañaga]

Thanks for the report, there was a bug when inserting elements. Fixed in:

[develop 702ae47] Fixed #10469: Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop