提高:: fibonacci_heap拷贝构造破坏源堆 [英] boost::fibonacci_heap copy constructor corrupts the source heap

问题描述

我有打印的boost :: fibonacci_heap快照的成员函数

I have a member function that prints a snapshot of a 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;
}

我呼吁在另一个成员函数这个成员函数，该函数

I call this member function in another member function, which does

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

由于堆在通过printSnapshot的开始拷贝构造函数创建的，则printSnapshot应该改变这个 - >堆。不过，这一方案将导致段故障，而以下不：

Since the heap is created through a copy constructor at the beginning of "printSnapshot", then "printSnapshot" should change this->heap. However, this program leads to segment fault, while the following does not:

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

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

Now, if we add a const keyword to the definition of printSnapshot, i.e.

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

段故障消失。怎么会这样来解释？

The segment fault disappears. How could this be explained?

推荐答案

fibonacci_heap 的构造函数，一个左值参考（非const）显然没有做正确的事。

The constructor of fibonacci_heap that takes a lvalue reference (non-const) apparently doesn't do the right things.

这不是证明它应该做的：的http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/fibonacci_heap.html#idp21129704-bb

It's not documented what it should do: http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/fibonacci_heap.html#idp21129704-bb

我想这可能是一个错误报告。我会考虑这一点。

I assume this might be a reportable bug. I'll look into this a bit.

更新令人惊讶的是该构造的行为显然是相当于布展施工：

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.

只要删除这个构造使得code的工作。

Simply removing this constructor makes the code work.

的根本解决方法是避免左值裁判的构造函数：

The essential workaround is to avoid the lvalue-ref constructor:

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

同时这里是一个自包含的再生器：

Meanwhile here's a self-contained reproducer:

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

这篇关于提高:: fibonacci_heap拷贝构造破坏源堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！