Problem with Boost Fibonacci Heap at the moment of erasing an element

Question

I'm getting an unrelated error with Boost's Fibonacci Heap when I use the erase()method:

astar: /usr/include/boost/intrusive/list.hpp:1266: static boost::intrusive::list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder>::iterator boost::intrusive::list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder>::s_iterator_to(boost::intrusive::list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder>::reference) [with ValueTraits = boost::intrusive::bhtraits<boost::heap::detail::heap_node_base<false>, boost::intrusive::list_node_traits<void*>, (boost::intrusive::link_mode_type)1, boost::intrusive::dft_tag, 1>; SizeType = long unsigned int; bool ConstantTimeSize = true; HeaderHolder = void; boost::intrusive::list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder>::iterator = boost::intrusive::list_iterator<boost::intrusive::bhtraits<boost::heap::detail::heap_node_base<false>, boost::intrusive::list_node_traits<void*>, (boost::intrusive::link_mode_type)1, boost::intrusive::dft_tag, 1>, false>; boost::intrusive::list_impl<ValueTraits, SizeType, ConstantTimeSize, HeaderHolder>::reference = boost::heap::detail::heap_node_base<false>&]: Assertion `!node_algorithms::inited(value_traits::to_node_ptr(value))' failed.

This is the part of the code that triggers the error:

void prune(Node_h* last_sol){
    Node_h* elem;
    int count = 0;
    for(auto it=open.begin(),end=open.end(); it != end; ++it){
        elem = *it;
        
        if (handlers.find(elem) == handlers.end()){
            printf("KEEEEY NOT FOUND");
        } else {
            printf("elem->f: %f >= last_sol->f: %f \n",elem->g.second+elem->h.second, last_sol->g.second+last_sol->h.second);
            if(elem->g.second+elem->h.second >= last_sol->g.second+last_sol->h.second){ 
                
                open.erase(handlers[elem]);
                count++;
            }
        }
    }
    printf("New Open size: %ld ", open.size());
    printf("Nodes prune: %d\n", count);
}

I'm saving the handlers in a hash map at the moment of pushing the nodes:

open_handle handler = open.push(succ);
handlers[succ] = handler;

Everything worked fine with the heap until this point (pop and push methods) so I'm puzzled on what could trigger this error, implementation looks accord to the documentation.

Other information:

struct compare_states {
    bool operator()(const Node_h* s1, const Node_h* s2) const {
        //return n1.id > n2.id;
        return s1->f > s2->f ;
    }
};
typedef fibonacci_heap<Node_h*,compare<compare_states> >::handle_type open_handle;

gcc version 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)

Answer 1

This loop looks suspect:

for(auto it=open.begin(),end=open.end(); it != end; ++it){
    open.erase(/*...*/);
}

Quoting the docs:

Unless otherwise noted, all non-const heap member functions invalidate iterators, while all const member functions preserve the iterator validity.

That means the erase invalidates the loop iterator(s).

From context I'm assuming that handler/handlers in your code actually refers to node handles. If so, you might want to collect handles to be erased in a temporary container before doing the deletion:

Live On Compiler Explorer

#include <boost/heap/fibonacci_heap.hpp>
#include <fmt/ranges.h>
#include <map>

int main() {
    namespace bh = boost::heap;
    using Heap   = bh::fibonacci_heap<int>;
    using Handle = Heap::handle_type;

    Heap open;
    std::map<int, Heap::handle_type> handles;

    for (int j : {1, 2, 3, 4, 5})
        handles.emplace(j, open.push({j}));

    std::vector<Handle> to_erase;
    for (int el : open) {
        if (el % 2) {
            //if (handles.contains(el)) {
                to_erase.push_back(handles.at(el));
            //}
        }
    }

    fmt::print("Deleting {} odd elements from {}\n", to_erase.size(), open);
    for (auto h : to_erase)
        open.erase(h);

    fmt::print("Remaining {}\n", open);
}

Prints

Deleting 3 odd elements from [5, 4, 3, 2, 1]
Remaining [4, 2]

---

For classic node-based containers, the following loop style would be applicable:

for (auto it = open.begin(), end = open.end(); it != end;) {
    if (condition) 
        it = open.erase(it);
    else
        ++it;
}

However, fibonacci_heap::erase returns void.

In fact this algorithm is standardized as the free function std::erase_if in c++20 for standard containers.