IntrusiveHeap implements a skew heap with intrusive pointers to provide O(log(n)) operations on any node in the heap with no separately allocated node type.
Declared in <folly/container/IntrusiveHeap.h>
template<
class T,
class Compare = std::less<>,
class Tag = void,
class NodeTraitsType = DerivedNodeTraits<T, Tag>>
class IntrusiveHeap;
To be inserted into an IntrusiveHeap<T, Compare, Tag>, T must inherit from IntrusiveHeapNode<Tag>, or have a member of type IntrusiveHeapNode<Tag> and use MemberNodeTraits.
An instance of T may only be included in one IntrusiveHeap for each Tag type. It may be included in more than one IntrusiveHeap by inheriting from IntrusiveHeapNode again with a different tag type, or by using composition with different members.
| Name | Description |
|---|---|
Node | The intrusive node type stored by elements of this heap. |
NodeTraits | The traits used to convert between values and nodes. |
Value | The element type stored in the heap. |
| Name | Description |
|---|---|
IntrusiveHeap [constructor] | Constructors |
operator= | Assignment operators |
contains | Check whether this node is included in this heap. Primarily meant for assertions, as containment should be externally tracked. |
empty | Returns true if the heap contains no values. |
erase | Removes a value from the heap. |
merge | Moves the contents of other into *this. |
pop | Removes the maximum value from the heap and returns it, or nullptr if the heap is empty. |
push | Inserts a value into the heap. |
top | Returns a pointer to the maximum value in the heap, or nullptr if the heap is empty. |
update | Updates the heap to reflect a change in a given value. |
visit | Visits all items in the heap. |
| Name | Description |
|---|---|
folly::IntrusiveHeapTest | Test fixture granted access to node internals. |