擦除元素时 Boost Fibonacci Heap 的问题

Question

当我使用 erase() 方法时，我遇到了与 Boost 的 Fibonacci 堆无关的错误：

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.

这是触发错误的代码部分：

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);
}

我在推送节点时将处理程序保存在哈希映射中：

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

直到此时（pop 和 push 方法）在堆上一切正常，所以我对什么会触发这个错误感到困惑，实现看起来与文档一致。

其他信息：

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 版本 7.5.0 (Ubuntu 7.5.0-3ubuntu1~18.04)

Answer 1

这个循环看起来很可疑：

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

引用 the docs:

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

这意味着 erase 使循环迭代器无效。

根据上下文，我假设您的代码中的 handler/handlers 实际上是指节点 handles。如果是这样，您可能希望在执行删除之前收集要在临时容器中删除的句柄：

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);
}

版画

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

对于经典 node-based 容器，以下循环样式适用：

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

但是，fibonacci_heap::erase returns无效。

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

擦除元素时 Boost Fibonacci Heap 的问题

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

c++

boost

fibonacci-heap