folly::IntrusiveHeap

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.

Synopsis

Declared in <folly/container/IntrusiveHeap.h>

template<
    class T,
    class Compare = std::less<>,
    class Tag = void,
    class NodeTraitsType = DerivedNodeTraits<T, Tag>>
class IntrusiveHeap;

Description

  • 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.

Type Aliases

NameDescription
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.

Member Functions

NameDescription
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.

Friends

NameDescription
folly::IntrusiveHeapTestTest fixture granted access to node internals.