boost::fibonacci_heap 复制构造函数破坏了源堆

Question

我有一个成员函数可以打印 boost::fibonacci_heap

的快照

virtual void printSnapshot(std::ostream& ss) {
  Heap heap(this->heap);
  double prev_price = DBL_MAX;
  while(heap.size() > 0) {
    const Order& order = heap.top();
    if(order.price != prev_price) {
      if(prev_price != DBL_MAX) ss << std::endl;
      ss << order.price << " | ";
    }
    ss << order.quantity << " ";
    prev_price = order.price;
    heap.pop();
  }
  ss << std::endl;
}

我在另一个成员函数中调用这个成员函数，它

while(std::getline(stream, line)) {
    ... // do something on this->heap.
    this->printSnapshot(std::cout);
}

既然堆是在"printSnapshot"开头通过拷贝构造函数创建的，那么"printSnapshot"应该改this->heap。但是这个程序会导致segment fault，而下面不会：

while(std::getline(stream, line)) {
    ... // do something on this->heap.
    // this->printSnapshot(std::cout);
}

现在，如果我们在 printSnapshot 的定义中添加一个 const 关键字，即

virtual void printSnapshot(std::ostream& ss) const {
  Heap heap(this->heap);
  double prev_price = DBL_MAX;
  while(heap.size() > 0) {
    const Order& order = heap.top();
    if(order.price != prev_price) {
      if(prev_price != DBL_MAX) ss << std::endl;
      ss << order.price << " | ";
    }
    ss << order.quantity << " ";
    prev_price = order.price;
    heap.pop();
  }
  ss << std::endl;
}

段错误消失。这怎么解释？

Answer 1

fibonacci_heap 的构造函数采用 lvalue reference（非常量）显然没有做正确的事情。

没有记录它应该做什么：http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/fibonacci_heap.html#idp21129704-bb

我认为这可能是一个可报告的错误。我会仔细研究一下。

UPDATE Surprisingly the behaviour of this constructor is apparently equivalent to move-construction:
#ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
    /// \copydoc boost::heap::priority_queue::priority_queue(priority_queue &&)
    fibonacci_heap(fibonacci_heap && rhs):
        super_t(std::move(rhs)), top_element(rhs.top_element)
    {
        roots.splice(roots.begin(), rhs.roots);
        rhs.top_element = NULL;
    }

    fibonacci_heap(fibonacci_heap & rhs):
        super_t(rhs), top_element(rhs.top_element)
    {
        roots.splice(roots.begin(), rhs.roots);
        rhs.top_element = NULL;
    }
The latter has the weird side-effect of simply removing all roots from the original (intrusive) list. This looks like a clear-cut bug.

Simply removing this constructor makes the code work.

基本的解决方法是避免左值引用构造函数：

Heap cloned(static_cast<Heap const&>(this->heap));

同时这里有一个独立的复制器：

#include <boost/heap/fibonacci_heap.hpp>
#include <iostream>
#include <random>

namespace {
#undef DBL_MAX
    static double DBL_MAX = std::numeric_limits<double>::max();

    std::mt19937 rng;
    //std::uniform_real_distribution<double> dist(100, 4000);
    std::discrete_distribution<int> dist({1,1,1,1,1,1});
    static auto price_gen = [&] { 
        static double values[] = {52.40, 12.30, 87.10, 388., 0.10, 23.40};
        return values[dist(rng)]; 
    };
}


struct Order {
    double price      = price_gen();
    unsigned quantity = rand() % 4 + 1;

    double subtotal() const { return price * quantity; }

    bool operator<(Order const& other) const { return subtotal() < other.subtotal(); }
};

using Heap = boost::heap::fibonacci_heap<Order>;

struct Y {
    virtual void printSnapshot(std::ostream &ss) {
        //Heap cloned(static_cast<Heap const&>(this->heap));
        Heap cloned(this->heap);
        double prev_price = DBL_MAX;

        while (cloned.size() > 0) {
            const Order &order = cloned.top();

            if (order.price != prev_price) {
                if (prev_price != DBL_MAX)
                    ss << std::endl;
                ss << order.price << " | ";
            }
            ss << order.quantity << " ";
            prev_price = order.price;
            cloned.pop();
        }
        ss << std::endl;
    }

    void generateOrders() {
        for (int i=0; i<3; ++i) {
            heap.push({});
        }
    }

    Heap heap;
};

int main() {
    Y y;
    for(int i=0; i<10; ++i) {
        y.generateOrders();
        y.printSnapshot(std::cout);
    }
}

boost::fibonacci_heap 复制构造函数破坏了源堆

boost::fibonacci_heap copy constructor corrupts the source heap

c++

boost