Почему я могу обновить выдвинутый элемент в boost :: fibonacci_heap?

Я реализую алгоритм Fast Marching с использованием библиотеки 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

2

Решение

Действительно, вы вызываете Неопределенное поведение.

Запустите вашу программу под 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] ----

Видите, вы читаете память, которая была ранее удалена. К сожалению.

Все может случиться. Что происходит, зависит от вашей удачи, вашего компьютера и т. Д.

Used Я использовал очищенную версию кода: Жить на Колиру, так что вы можете перекрестные ссылки на номера строк

1

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]