配置为可变性时，boost :: heap :: d_ary_heap保留的额外std :: list的目的是什么? [英] What's the purpose of the extra std::list that boost::heap::d_ary_heap holds when configured for mutability?

问题描述

配置为可变性后， <代码> boost :: heap :: d_ary_heap 除了用于保存堆节点值的向量外，还使用std :: list.我意识到为使 mutable_heap_interface 工作而提供的句柄实际上是该列表的迭代器，但是我想知道为什么选择了这种昂贵的解决方案，以及是否有更精简的方法来实现 boost :: heap :: d_ary_heap 的可变性.

When configured for mutability, boost::heap::d_ary_heap uses a std::list in addition to the vector that holds the values of the heap nodes. I realize that the handles which are being provided for making the mutable_heap_interface work are in fact iterators of this list, but I'm wondering why such an expensive solution was chosen, and if there's a leaner way to achieve mutability with boost::heap::d_ary_heap.

可变性需要一种在给定节点本身的情况下在堆向量中查找节点索引的方法.需要维护某种后向指针.不能通过在节点中存储此向后指针并通过值类型的move/copy构造函数/assignment-operators对其进行维护来实现?

Mutability requires a way to find the index of a node in the heap vector, given the node itself. Some kind of backward pointer needs to be maintained. Can't this be achieved by storing this backwards pointer in the node, and maintain it by the move/copy constructors/assignment-operators of the value type?

有充分的理由说明它需要和双向链表一样贵吗?

Is there a good reason why it needs to be as expensive as a doubly-linked list?

推荐答案

这是对我自己的问题的一种答案，该问题仅推测了为什么升压设计保持原样，并提供了我所希望的部分解决方案获得增强数据结构.我仍然有兴趣进一步了解Boost实施背后的原理，当然还有我在下面提出的解决方案的反馈.

This is kind of an answer to my own question that only speculates why the boost design is as it is, and presents a partial solution to what I would have liked to get with the boost data structure. I'm still interested in receiving further insight into the rationale behind the boost implementation, and of course also feedback on the solution I present below.

让我先解释下面的代码，然后再讨论其优缺点，然后再对boost.heap实现进行评论，为什么它大概是这样，为什么我不喜欢它.

Let me first explain the piece of code below, before going on to discuss its merits and problems, and then comment on the boost.heap implementation, why it presumably is like it is, and why I don't like it.

下面的代码基于古老的 std :: priority_queue .它将由优先级队列管理的节点分为句柄和主体.该句柄进入 priority_queue 核心的堆中，并因此在添加或删除条目时在基础 vector 中移动.句柄仅包含优先级值和指向主体的指针，以使其廉价地移动.身体是一个潜在的大物体，会在内存中保持静止.它持有该句柄的反向指针，因为当主体的优先级更改或主体消失时，必须使该句柄无效.

The code below is based on the venerable std::priority_queue. It splits the node managed by the priority queue into a handle and a body. The handle goes into the heap at the core of the priority_queue, and therefore moves around in the underlying vector as entries are added or removed. The handle only contains the priority value and a pointer to the body, in order to make it cheap to move it around. The body is a potentially large object that remains stationary in memory. It holds a backpointer to the handle, because the handle must be invalidated when the body's priority changes, or the body disappears.

由于句柄在堆中四处移动，因此每次句柄更改位置时，都必须更新主体中的反向指针.这是在handle的move构造函数和move赋值运算符中完成的.如果句柄失效，则其中的指针和指向该句柄的反向指针都将为空.

Since the handle moves around in the heap, the backpointer in the body must be updated each time the handle changes location. This is done in the move constructor and the move assignment operator of the handle. If a handle gets invalidated, both the pointer in it and the backpointer pointing at it are nulled.

#include <queue>

//! Priority queue that works with handles to managed objects.
template<typename Prio, typename Object> struct PriorityQueue {
    struct Entry;

    //! Each heap entry is a handle, consisting of a pointer to the managed object and a priority value.
    struct Entry {
        Object *obj_;
        Prio val_;

        Entry(Entry const &) =delete;
        Entry &operator=(Entry const &) =delete;

        ~Entry() {
            if(obj_)
                obj_->setLink(nullptr);
        }

        Entry(Object &obj, Prio val)
            : obj_{&obj}
            , val_{val}
        {
            if(obj_)
                obj_->setLink(this);
        }

        Entry(Entry &&v)
            : obj_{v.obj_}
            , val_{v.val_}
        {
            if(obj_)
                obj_->setLink(this);
            v.obj_ = nullptr;
        }

        Entry &operator=(Entry &&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;
        }

        friend bool operator<(Entry const &a, Entry const &b) {
            return a.val_ < b.val_;
        }

    };

    Prio add(Object &obj, Prio val) {
        while(!heap_.empty() && !heap_.top().obj_)
            heap_.pop();
        heap_.emplace(obj, val);
        return heap_.top().val_;
    }

    Prio remove(Object &obj) {
        // We can't remove the entry straight away, so we null the pointer
        // and leave the entry in the heap, where it will eventually bubble
        // up to the root position, from where it can be removed.
        if(obj.getLink()) {
            obj.getLink()->obj_ = nullptr;
            obj.setLink(nullptr);
        }
        while(!heap_.empty() && !heap_.top().obj_)
            heap_.pop();
        return heap_.empty() ? INT64_MAX : heap_.top().val_;
    }

    Prio update(Object &obj, Prio val) {
        remove(obj);
        return add(obj, val);
    }

    std::priority_queue<Entry> heap_;
};

//! Example of a managed object.
struct MyObject {
    MyObject(MyObject const &) =delete;
    MyObject &operator=(MyObject const &) =delete;

    PriorityQueue<int, MyObject>::Entry *getLink() const {
        return link_;
    }
    
    void setLink(PriorityQueue<int, MyObject>::Entry *link) {
        link_ = link;
    }
    
    PriorityQueue<int, MyObject>::Entry *link_;
};

不幸的是，std :: priority_queue不支持可变性，即您不能删除除根条目之外的条目，因此后备方法是将句柄留在堆中，但通过破坏与主体的关系使它们无效.它们最终会朝根部冒出，可以从中取出.显然，这意味着它们不必要地增加了堆的大小，从而消耗了一些额外的内存和CPU时间，这可能是重要的，也可能不是重要的.如果 std :: priority_queue 将公开内部堆维护功能，则可以直接删除或更新条目.

Unfortunately, std::priority_queue doesn't support mutability, i.e. you can't remove entries except the root entry, so the fallback is to leave handles in the heap, but invalidate them by breaking the relationship with the body. They will eventually bubble up towards the root, where they can be removed. Obviously, that means that they inflate the size of the heap needlessly, consuming some additional memory and CPU time, which may or may not be significant. If std::priority_queue would expose the internal heap maintenance functions, it would be possible to delete or update entries directly.

通过将优先级保留在主体而不是句柄中，可以进一步减小句柄的大小，但是随后每次优先级比较都需要向主体进行咨询，这会破坏参考位置.选择的方法通过将所有与堆维护相关的句柄保存在句柄中来避免这种情况.move构造函数和move赋值运算符对主体中的backpointer进行更新是只写操作，而不会影响性能，因为现代处理器中通常存在写缓冲区，这些缓冲区可以吞噬相关的延迟.

It would be possible to reduce the handle size even more by holding the priority in the body rather than the handle, but then the body would need to be consulted for each priority comparison, which would destroy locality of reference. The chosen approach avoids this by holding everything in the handle that is relevant for heap maintenance. The updating of the backpointer in the body by the move constructor and move assignment operator is a write-only operation, which needn't hinder performance, since there typically are write buffers in modern processors that can swallow the associated latency.

为了优化缓存性能，可能希望使用d堆而不是二进制堆，以便向量中相邻的节点的所有子代(即它们的句柄)都占用一条缓存行.las， std :: priority_queue 也不支持.

For optimizing cache performance, one would wish to use a d-ary heap instead of a binary heap, so that all children of a node (i.e. their handles), which are adjacent in the vector, occupy one cache line. Alas, that's not supported by std::priority_queue, either.

boost.heap 将支持后者，但是为了也支持可变性，他们引入了附加的 std :: list 来管理反向指针，我怀疑这源于图书馆的时代.它的历史可以追溯到C ++ 11之前，当时该语言还没有移动支持.从那时起，大概只对它进行了最少的维护.我欢迎他们使库保持最新状态，并借此机会提供更精简的实现.

The latter would be supported by boost.heap, but in order to also support mutability, they introduce an additional std::list for the management of the backpointers, which I suspect is rooted in the age of the library. It dates back to before C++11, when move support wasn't yet available in the language. Presumably, only minimal maintenance has been done to it since. I'd welcome them bringing the library up to date and use the opportunity to provide leaner implementations.

因此，最重要的是，我至少有一个猜疑可以回答我的原始问题，并且设计可以解决我的一些目标，这给我留下了基于标准库的可行但尚不理想的解决方案.

So, the bottom line is that I have at least a suspicion that answers my original question, and a design that addresses some of my goals, leaving me with a workable but not yet optimal solution based on the standard library.

感谢评论者，并记住如果您有其他需要补充的见解，将非常欢迎您.

Thanks go to the commenters, and remember if you have additional insight to add, you're most welcome.

这篇关于配置为可变性时，boost :: heap :: d_ary_heap保留的额外std :: list的目的是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！