c++ - 配置为可变性时，boost::heap::d_ary_heap保存的额外std::list的目的是什么？

Question

当配置为可变性时， boost::heap::d_ary_heap 除了用于保存堆节点值的 vector 外，还使用std::list。我意识到为使mutable_heap_interface工作而提供的句柄实际上是该列表的迭代器，但是我想知道为什么选择了这种昂贵的解决方案，以及是否有更精简的方法来实现boost::heap::d_ary_heap的可变性。
给定节点本身，可变性需要一种在堆 vector 中查找节点索引的方法。需要维护某种后向指针。不能通过在节点中存储此向后指针并通过值类型的move / copy构造函数/ assignment-operators对其进行维护来实现？
有充分的理由为什么它需要和双向链表一样贵？

Answer 1

这是对我自己的问题的一种解答，该问题仅推测了为什么boost设计保持原样，并为我希望通过boost数据结构获得的结果提供了部分解决方案。我仍然有兴趣进一步了解Boost实现背后的原理，当然还有我在下面提出的解决方案的反馈。
让我先解释下面的代码，然后再讨论其优缺点，然后再对boost.heap实现进行评论，为什么它大概是这样，为什么我不喜欢它。
下面的代码基于古老的std::priority_queue。它将由优先级队列管理的节点分为句柄和主体。该句柄进入priority_queue核心的堆中，并因此在添加或删除条目时在底层vector中移动。句柄仅包含优先级值和指向主体的指针，以使其廉价地移动。 body 是一个潜在的大物体，在内存中保持静止。它持有该句柄的反向指针，因为当主体的优先级更改或主体消失时，必须使该句柄无效。
由于句柄在堆中移动，因此每次句柄更改位置时，都必须更新主体中的反向指针。这是在句柄的移动构造函数和移动分配运算符中完成的。如果句柄失效，则其中的指针和指向它的反向指针都将为空。
#include <队列>

//!与被管理对象的句柄一起使用的优先级队列。
template struct PriorityQueue {
struct Entry;

//!每个堆条目都是一个句柄，由指向托管对象的指针和优先级值组成。
struct Entry {
对象* obj_;
Prio val_;

Entry(Entry const＆)=删除;
条目＆operator =(条目const＆)=删除;

〜Entry(){
如果(obj_)
obj _-> setLink(nullptr);
}

条目(对象和对象，优先级)
:obj _ {＆obj}
，val_ {val}
{
如果(obj_)
obj _-> setLink(this);
}

条目(条目&& v)
:obj_ {v.obj_}
，val_ {v.val_}
{
如果(obj_)
obj _-> setLink(this);
v.obj_ = nullptr;
}

条目＆operator =(条目&& v){
if(＆v!= this){
val_ = v.val_;
如果(obj_)
obj _-> setLink(nullptr);
obj_ = v.obj_;
如果(obj_)
obj _-> setLink(this);
v.obj_ = nullptr;
}
返回* this;
}

friend bool(boolean) 运算符<(Entry const＆a，Entry const＆b){
返回a.val_ }

};

Prio add(Object＆obj，Prio val){
while(!heap_.empty()&&!heap_.top()。obj_)
heap_.pop();
heap_.emplace(obj，val);
返回heap_.top()。val_;
}

Prio remove(Object＆obj){
//我们无法立即删除该条目，因此我们将指针归零
//将条目保留在堆中，最终它将在此处冒泡
//直到可以从中移除的根位置为止。
if(obj.getLink()){
obj.getLink()-> obj_ = nullptr;
obj.setLink(nullptr);
}
while(!heap_.empty()&&!heap_.top()。obj_)
heap_.pop();
返回heap_.empty()？ INT64_MAX:heap_.top()。val_;
}

Prio更新(Object＆obj，Prio val){
remove(obj);
返回add(obj，val);
}

std::priority_queue 堆_;
};

//!受管理对象的示例。
struct MyObject {
MyObject(MyObject const＆)=删除;
MyObject＆operator =(MyObject const＆)=删除;

PriorityQueue ::Entry * getLink()const {
返回link_;
}

无效setLink(PriorityQueue ::Entry * link){
link_ =链接；
}

PriorityQueue ::Entry * link_;
};

不幸的是，std::priority_queue不支持可变性，即您不能删除除根条目以外的条目，因此后备方法是将句柄留在堆中，但通过破坏与主体的关系来使它们无效。它们最终会朝根部冒出，可以从中取出。显然，这意味着它们不必要地增加了堆的大小，从而消耗了一些额外的内存和CPU时间，这可能或可能不重要。如果 std::priority_queue将公开内部堆维护功能，则可以直接删除或更新条目。
通过将优先级保留在主体而不是句柄中，甚至可以进一步减小句柄的大小，但是随后每次优先级比较都需要向主体进行咨询，这会破坏参考位置。选择的方法通过将与堆维护相关的所有内容保留在句柄中来避免这种情况。移动构造函数和移动赋值运算符在主体中对Backpointer进行更新是只写操作，而不会影响性能，因为现代处理器中通常会存在写入缓冲区，这些缓冲区会吞噬相关的延迟。
为了优化高速缓存性能，人们希望使用一元堆而不是二进制堆，以便 vector 中相邻的节点的所有子代(即它们的句柄)都占据一个高速缓存行。 ， std::priority_queue也不支持。
后者将由 boost.heap支持，但是为了也支持可变性，他们引入了一个额外的 std::list来管理回指针，我怀疑这是从库时代开始的。它的历史可以追溯到C++ 11之前，当时该语言还没有移动支持。从那时起，大概只对它进行了最少的维护。我欢迎他们使库保持最新状态，并借此机会提供更精简的实现。
因此，最重要的是，我至少有一个猜疑可以回答我的原始问题，而设计可以解决我的一些目标，这给我留下了一个基于标准库的可行但尚不理想的解决方案。
多谢评论者，并记住如果您有其他需要补充的信息，我们将非常欢迎。