配置为可变时，boost::heap::d_ary_heap除了使用保存堆节点值的向量外，还使用std:：list。我意识到，为使mutable_heap_interface工作而提供的句柄实际上是该列表的迭代器，但我想知道为什么选择如此昂贵的解决方案，以及是否有更精简的方法来实现boost::heap::d_ary_heap的可变性。
可变性需要一种方法，在给定节点本身的情况下，在堆向量中找到节点的索引。需要维护某种向后指针。这难道不能通过将这个向后指针存储在节点中，并通过值类型的移动/复制构造函数/赋值运算符来维护它来实现吗？
为什么它需要像双重链接列表一样昂贵，有充分的理由吗？
这是对我自己的问题的一种回答，这个问题只是推测为什么boost设计是这样的，并为我想要的boost数据结构提供了部分解决方案。我仍然有兴趣进一步了解boost实现背后的基本原理，当然还有对我下面介绍的解决方案的反馈。
让我先解释一下下面的代码，然后讨论它的优点和问题，然后评论boost.heap的实现，为什么它可能是这样，以及为什么我不喜欢它。
下面的代码是基于古老的std::priority_queue。它将优先级队列管理的节点拆分为一个句柄和一个主体。句柄进入priority_queue核心的堆中，因此在添加或删除条目时在底层vector中移动。句柄只包含优先级值和一个指向主体的指针，以便使其四处移动变得便宜。身体是一个潜在的大物体，在记忆中保持静止。它持有一个指向句柄的后向指针，因为当主体的优先级更改或主体消失时，句柄必须无效。
由于句柄在堆中移动，因此每次句柄更改位置时，都必须更新主体中的backpointer。这是在句柄的move构造函数和move赋值运算符中完成的。如果句柄无效，则其中的指针和指向它的反向指针都为null。
#include<队列>//！使用托管对象句柄的优先级队列。模板<typename优先级，typename对象>结构优先级队列{struct Entry；//！每个堆条目都是一个句柄，由指向托管对象的指针和优先级值组成。结构条目{对象*obj_；优先级_；Entry(Entry const&)=删除；条目&operator=(条目常量&)=删除；~入口(){if(obj_)obj_->setLink(nullptr)；}条目(对象&obj，优先级)：obj_｛&obj｝，val_｛val｝{if(obj_)obj_->setLink(this)；}条目(条目&&v)：obj_｛v.obj_｝，val_｛v.val_｝{if(obj_)obj_->setLink(this)；v.obj=nullptr；}条目&运算符=(条目&&v){if(&v！=this){val_=v.val_；if(obj_)obj_->setLink(nullptr)；obj_=v.obj_；if(obj_)obj_->setLink(this)；v.obj=nullptr；}return*this；}友元布尔运算符<(条目常量&a，条目常量&aamp；b){return a.val_<b.val_；}}；优先级添加(对象&obj，优先级值){而(！heap_empty()&！heap_.top().obj)heap_pop()；heap_template(obj，val)；return heap_top().val；}删除优先级(对象&obj){//我们无法立即删除该条目，因此我们将指针设为空//并将条目留在堆中，最终会在堆中冒泡//直到根部位置，从那里可以将其移除。if(obj.getLink()){obj.getLink()->obj_=nullptr；obj.setLink(nullptr)；}而(！heap_empty()&！heap_.top().obj)heap_pop()；是否返回heap_empty()？INT64_MAX：堆.top().val_；}优先级更新(对象和对象，优先级值){remove(obj)；return add(obj，val)；}std:：priority_queue<条目>堆_；}；//！托管对象的示例。结构MyObject{MyObject(MyObject const&)=删除；MyObject；operator=(MyObject常量&)=删除；优先级队列<int，MyObject>：条目*getLink()常量{return link_；}void setLink(PriorityQueue<int，MyObject>：Entry*link){link_=链接；}优先级队列<int，MyObject>：条目*link_；}
不幸的是，std:：priority_queue不支持可变性，即您不能删除除根条目之外的条目，因此回退是将句柄留在堆中，但通过破坏与主体的关系使其无效。它们最终会向根部冒出气泡，在那里它们可以被去除。显然，这意味着它们不必要地扩大了堆的大小，消耗了一些额外的内存和CPU时间，这可能很重要，也可能不重要。如果std::priority_queue将公开内部堆维护函数，则可以直接删除或更新条目。
通过将优先级保留在主体中而不是句柄中，可以进一步减小句柄大小，但每次优先级比较都需要咨询主体，这会破坏引用的位置。所选择的方法通过在句柄中保留与堆维护相关的所有内容来避免这种情况。move构造函数和move赋值运算符更新主体中的backpointer是一种只写操作，这不必妨碍性能，因为现代处理器中通常有写缓冲区可以吞噬相关的延迟。
为了优化缓存性能，人们希望使用d元堆而不是二进制堆，这样在向量中相邻的节点的所有子节点(即它们的句柄)都会占用一条缓存线。遗憾的是，std::priority_queue也不支持这一点。
后者将由boost.heap支持，但为了也支持可变性，他们引入了一个额外的std::list来管理后向指针，我怀疑这源于库的时代。它可以追溯到C++11之前，当时该语言还没有提供移动支持。据推测，从那以后，只对其进行了最低限度的维护。我欢迎他们更新库，并利用这个机会提供更精简的实现。
因此，最重要的是，我至少有一个怀疑，可以回答我最初的问题，并且有一个设计可以解决我的一些目标，给我留下一个基于标准库的可行但尚未优化的解决方案。
感谢评论，请记住，如果你有其他见解需要补充，我们非常欢迎你。