boost :: fibonacci_heap复制构造函数破坏源堆 [英] boost::fibonacci_heap copy constructor corrupts the source heap
问题描述
我有一个成员函数打印一个boost :: fibonacci_heap的快照
virtual void printSnapshot（std :: ostream& ; ss）{
堆堆（this-> heap）;
double previous_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）;
}
由于堆是通过copySnapshot开头的复制构造函数创建的， ，那么printSnapshot应该更改this-> heap。但是，这个程序导致段错误，而以下不会：
while（std :: getline（stream，line） ）{
... // do something on this-> heap。
// this-> printSnapshot（std :: cout）;
}
现在，如果我们在printSnapshot的定义中添加一个const关键字， / p>
virtual void printSnapshot（std :: ostream& ss）const {
堆堆（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引用（非const）显然不能做正确的事情。
应该执行以下操作： http：// www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/fibonacci_heap.html#idp21129704-bb
我假设这可能是一个可报告的错误。
这个构造函数的行为显然相当于移动-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）
{
root.splice .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};
返回值[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（）; }
};
使用Heap = boost :: heap :: fibonacci_heap< Order> ;;
struct Y {
virtual void printSnapshot（std :: ostream& ss）{
// Heap克隆（static_cast< Heap const&>（this-> heap ））;
堆克隆（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（{}）;
}
}
堆堆;
};
int main（）{
Y y;
for（int i = 0; i <10; ++ i）{
y.generateOrders（）;
y.printSnapshot（std :: cout）;
}
}
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);
}
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);
}
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?
The constructor of fibonacci_heap that takes a lvalue reference (non-const) apparently doesn't do the right things.
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.
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);
}
}
这篇关于boost :: fibonacci_heap复制构造函数破坏源堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
