[Boost-bugs] [Boost C++ Libraries] #10469: Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop

Subject: [Boost-bugs] [Boost C++ Libraries] #10469: Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-09-05 16:43:28

#10469: Erasing from intrusive unordered_multiset with optimize_multikey goes into
an infinite loop
--------------------------------------+------------------------
 Reporter:  Anton Kryukov <akryuk@…>  |      Owner:  igaztanaga
     Type:  Bugs                      |     Status:  new
Milestone:  To Be Determined          |  Component:  intrusive
  Version:  Boost 1.56.0              |   Severity:  Problem
 Keywords:                            |
--------------------------------------+------------------------
 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 ---


 }}}

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/10469>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.