0
我正在使用boost :: fibonacci_heap庫實現快速前進算法，並且我正在開始使用其句柄操作元素。爲什麼我可以更新boost :: fibonacci_heap中的彈出元素？
我已經寫了下面的基本代碼，它編譯好，但我不明白它的行爲：
我第一次推各元素的句柄存儲在數組中。然後我彈出堆中的第一個元素，然後檢查堆大小是否下降。
但是，我嘗試使用其句柄更新彈出的元素的值。這個操作起作用（令人驚訝的是？），更新的元素現在位於堆的頂部。但堆大小保持不變，因爲我沒有正確地推入新的元素。
那麼彈出元素更新並返回堆時會發生什麼？堆仍然有效嗎？
# include <boost/heap/fibonacci_heap.hpp>
# include <iostream>
using namespace std;
using namespace boost::heap;
struct node
{
int index;
double time;
node(const int& i, double t) : index(i), time(t) {}
};
struct compare_node
{
bool operator()(const node& n1, const node& n2) const
{
return (n1.time > n2.time);
}
};
int main()
{
fibonacci_heap< node, compare<compare_node> > heap;
typedef fibonacci_heap< node, compare<compare_node> >::handle_type handle_t;
handle_t tab_handle[10];
int n;
double tt[10];
// assign a set of arbitrary numbers to initialise array tt:
tt[0] = 5.3;
tt[1] = 0.25;
tt[2] = 3.6;
tt[3] = 1.75;
tt[4] = 9.1;
tt[5] = 2.54;
tt[6] = 3.8;
tt[7] = 6.1;
tt[8] = 1.23;
tt[9] = 7.32;
// push the values of tt into the heap, and keep track of the handle of each element in the heap:
for (n=0; n<10; n++)
{
tab_handle[n] = heap.push(node(n, tt[n]));
}
// display first element in heap
cout << "first element in heap is :" << heap.top().index << " " << heap.top().time << "\n";
// check size of the heap
cout << "size of heap is :" << heap.size() << "\n";
// remove top element
heap.pop();
// check size of the heap
cout << "size of heap after pop is :" << heap.size() << "\n";
// display first element in heap
cout << "first element in heap is now :" << heap.top().index << " " << heap.top().time << "\n";
// access value of a given element by index:
cout << "element index 2 has time :" << (*tab_handle[2]).time << "\n";
// attempt to access the element with handle tab_handle[1]: this element was actually popped out of the heap previously. But I can access it:
cout << "element index 1 has time :" << (*tab_handle[1]).time << "\n";
// update the time of an element using its handle. This is quite standard.
heap.update(tab_handle[2],node(2, tt[2]/10));
// but now I can also update the element that was popped out of the heap:
heap.update(tab_handle[1],node(1, tt[1]/10));
// display first element in heap
cout << "first element in heap is now :" << heap.top().index << " " << heap.top().time << "\n";
// check size of the heap
cout << "size of heap after pop is :" << heap.size() << "\n";
return 0;
}
端子輸出：
first element in heap is :1 0.25
size of heap is :10
size of heap after pop is :9
first element in heap is now :8 1.23
element index 2 has time :3.6
element index 1 has time :0.25
first element in heap is now :1 0.025
size of heap after pop is :9
聽起來像是UB給我。 –
是否使用類似於使用指向已刪除對象的指針的「彈出元素」句柄？ **任何**都可能發生？ –
這是「我的代碼有一個錯誤，爲什麼它沒有達到我期望的效果？」的又一個例子？答案總是一樣的「這就是錯誤所做的事情，你不會期待的事情，修復錯誤並且神祕消失。」 –