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

debugcn 发表于 Dev

斯特林

我有一个成员函数，可打印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。但是，此程序导致段错误，而以下情况则不会：

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

现在，如果我们在sprintSnapshot的定义中添加一个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;
}

段故障消失。怎么解释呢？

看

fibonacci_heap带有lvalue reference（非const）的构造函数显然没有做正确的事情。

它没有记录应执行的操作：http : //www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/fibonacci_heap.html#idp21129704-bb

我认为这可能是一个可报告的错误。我会对此进行调查。

更新令人惊讶的是，此构造方法的行为显然等同于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;
    }

后者有一个奇怪的副作用，就是简单地从原始（侵入式）列表中删除所有根。这看起来像一个明确的错误。

只需删除此构造函数即可使代码正常工作。

基本的解决方法是避免使用lvalue-ref构造函数：

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);
    }
}