[Boost-bugs] [Boost C++ Libraries] #13087: Boost::binomial_heap Merge error

Subject: [Boost-bugs] [Boost C++ Libraries] #13087: Boost::binomial_heap Merge error
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-06-20 17:27:54

#13087: Boost::binomial_heap Merge error
 Reporter: jun.kudo@… | Owner: timblechmann
     Type: Bugs | Status: new
Milestone: To Be Determined | Component: heap
  Version: Boost 1.64.0 | Severity: Problem
 Keywords: |
 Configured with BOOST_HEAP_SANITYCHECKS turned on.
 Binomial heap hits an assertion failure during the second merge routine in
 the attached example.

 #include "boost/heap/binomial_heap.hpp"
 typedef boost::heap::binomial_heap<int> Heap;

 int main(int argc, char* argv[]) {
   Heap heap0;
   size_t heap0_size = 13;
   size_t max_range = 100;
   for (size_t ix = 0; ix < heap0_size; ++ix) {
     heap0.push(rand() % max_range);

   Heap heap1;
   size_t heap1_size = 5;
   for (size_t ix = 0; ix < heap1_size; ++ix) {
     heap1.push(rand() % max_range);

   Heap heap2;
   size_t heap2_size = 1;
   for (size_t ix = 0; ix < heap2_size; ++ix) {
     heap2.push(rand() % max_range);


 When heap1 is merged into heap0, the underlying forest incorrectly
 contains two 2-degree trees. This error is later caught in a sanity
 assertion check when heap0 is merged into heap2.

 I believe the error stems the case identified by line 668 in
 binomial_heap.hpp. When the two root degrees are equal and a carry tree
 with degree less than both exist, the carry tree is inserted into trees.
 However, after this insertion, the this_iterator is incorrectly iterated
 forward which causes the algorithm to behave incorrectly. In the case
 provided above, this causes the merge algorithm to skip the degree-2 /
 degree-2 merge between this and rhs, and instead causes rhs's degree-2
 tree to be simple inserted into trees.

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

This archive was generated by hypermail 2.1.7 : 2017-06-20 17:32:18 UTC