c++ - 可变优先级队列，允许增加 key

在实现图形搜索算法时，我需要一个允许优先级更改的优先级队列。到现在为止，我一直在使用detail命名空间boost(但未记录名称)d_ary_heap_indirect，但只是被告知未定义优先级的增加(在concept documentation中也提到了这一点)。

因此，我需要找到一个既可以增加又可以减少的结构。我已经尝试过简单地使用vector和push_heap / pop_heap / make_heap，但是更新太慢了。有哪些选择？我看到boost在未决的(再次是未记录的)目录中有两个类，mutable_queue和relaxed_heap，但是我只能在已有五年历史的邮件列表线程中找到它们的提及。它们之间有什么区别，它们是否允许增加和减少？是否有任何尚未接受的实现？

最佳答案

Boost.MultiIndex库的功能容器具有对update对象状态进行操作的操作，并将相应地更新索引。

在您的情况下，modify成员函数似乎合适。从文档中:

struct change_name
{
  change_name(const std::string& new_name):new_name(new_name){}

  void operator()(employee& e)
  {
    e.name=new_name;
  }

private:
  std::string new_name;
};

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index = es.get<name>();

employee_set_by_name::iterator it = name_index.find("Anna Jones");
name_index.modify(it,change_name("Anna Smith"));

关于c++ - 可变优先级队列，允许增加 key ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7316003/