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

Name

Description

The intrusive node type stored by elements of this heap.

The traits used to convert between values and nodes.

The element type stored in the heap.

Member Functions

Name

Description

IntrusiveHeap [constructor]

Constructors

Assignment operators

Check whether this node is included in this heap. Primarily meant for assertions, as containment should be externally tracked.

Returns true if the heap contains no values.

Removes a value from the heap.

Moves the contents of other into *this.

Removes the maximum value from the heap and returns it, or nullptr if the heap is empty.

Inserts a value into the heap.

Returns a pointer to the maximum value in the heap, or nullptr if the heap is empty.

Updates the heap to reflect a change in a given value.

Visits all items in the heap.

Friends

Name

Description

folly::IntrusiveHeapTest

Test fixture granted access to node internals.

Created with MrDocs