I am implementing a Fast Marching algorithm using the boost::fibonacci_heap library, and I was getting started with manipulating elements using their handles.
I have written the basic code below, it compiles well but I do not understand its behaviour:
I first store the handles of each pushed element in an array. Then I pop out the first element from the heap, and I check that the heap size has decreased.
But then I attempt to update the value of the element that was popped out, using its handle. This operation works (surprisingly ?), and the updated element is now at the top of the heap. But the heap size remains the same, since I haven't properly pushed a new element in.
So what happens when a popped out element is updated and back in the heap ? Is the heap still valid ?
# 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;
}
the terminal outputs:
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
Indeed, you're invoking Undefined Behaviour.
Run your program under valgrind¹:
sehe@desktop:/tmp$ valgrind --db-attach=yes ./test
==14185== Memcheck, a memory error detector
==14185== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==14185== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==14185== Command: ./test
==14185==
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
==14185== Invalid read of size 8
==14185== at 0x400F21: main (test.cpp:47)
==14185== Address 0x5aa6d78 is 24 bytes inside a block of size 72 free'd
==14185== at 0x4C2C2BC: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==14185== by 0x402789: __gnu_cxx::new_allocator<boost::heap::detail::marked_heap_node<node> >::deallocate(boost::heap::detail::marked_heap_node<node>*, unsigned long) (new_allocator.h:110)
==14185== by 0x401D2C: boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::finish_erase_or_pop(boost::heap::detail::marked_heap_node<node>*) (fibonacci_heap.hpp:745)
==14185== by 0x4015E7: boost::heap::fibonacci_heap<node, boost::heap::compare<compare_node>, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_, boost::parameter::void_>::pop() (fibonacci_heap.hpp:398)
==14185== by 0x400E1C: main (test.cpp:34)
==14185==
==14185==
==14185== ---- Attach to debugger ? --- [Return/N/n/Y/y/C/c] ----
See, you're reading memory that was previously deleted. Oops.
Anything can happen. What happens depends on your luck, your computer etc.
¹ I used a cleaned up version of the code: Live On Coliru, so you can cross reference the line numbers