chromium/base/containers/intrusive_heap.h

// Copyright 2019 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef BASE_CONTAINERS_INTRUSIVE_HEAP_H_
#define BASE_CONTAINERS_INTRUSIVE_HEAP_H_

// Implements a standard max-heap, but with arbitrary element removal. To
// facilitate this, each element has associated with it a HeapHandle (an opaque
// wrapper around the index at which the element is stored), which is maintained
// by the heap as elements move within it.
//
// An IntrusiveHeap is implemented as a standard max-heap over a std::vector<T>,
// like std::make_heap. Insertion, removal and updating are amortized O(lg size)
// (occasional O(size) cost if a new vector allocation is required). Retrieving
// an element by handle is O(1). Looking up the top element is O(1). Insertions,
// removals and updates invalidate all iterators, but handles remain valid.
// Similar to a std::set, all iterators are read-only so as to disallow changing
// elements and violating the heap property. That being said, if the type you
// are storing is able to have its sort key be changed externally you can
// repair the heap by resorting the modified element via a call to "Update".
//
// Example usage:
//
//   // Create a heap, wrapping integer elements with WithHeapHandle in order to
//   // endow them with heap handles.
//   IntrusiveHeap<WithHeapHandle<int>> heap;
//
//   // WithHeapHandle<T> is for simple or opaque types. In cases where you
//   // control the type declaration you can also provide HeapHandle storage by
//   // deriving from InternalHeapHandleStorage.
//   class Foo : public InternalHeapHandleStorage {
//    public:
//     explicit Foo(int);
//     ...
//   };
//   IntrusiveHeap<Foo> heap2;
//
//   // Insert some elements. Like most containers, "insert" returns an iterator
//   // to the element in the container.
//   heap.insert(3);
//   heap.insert(1);
//   auto it = heap.insert(4);
//
//   // By default this is a max heap, so the top element should be 4 at this
//   // point.
//   EXPECT_EQ(4, heap.top().value());
//
//   // Iterators are invalidated by further heap operations, but handles are
//   // not. Grab a handle to the current top element so we can track it across
//   // changes.
//   HeapHandle* handle = it->handle();
//
//   // Insert a new max element. 4 should no longer be the top.
//   heap.insert(5);
//   EXPECT_EQ(5, heap.top().value());
//
//   // We can lookup and erase element 4 by its handle, even though it has
//   // moved. Note that erasing the element invalidates the handle to it.
//   EXPECT_EQ(4, heap.at(*handle).value());
//   heap.erase(*handle);
//   handle = nullptr;
//
//   // Popping the current max (5), makes 3 the new max, as we already erased
//   // element 4.
//   heap.pop();
//   EXPECT_EQ(3, heap.top().value());
//
// Under the hood the HeapHandle is managed by an object implementing the
// HeapHandleAccess interface, which is passed as a parameter to the
// IntrusiveHeap template:
//
//   // Gets the heap handle associated with the element. This should return the
//   // most recently set handle value, or HeapHandle::Invalid(). This is only
//   // called in DCHECK builds.
//   HeapHandle GetHeapHandle(const T*);
//
//   // Changes the result of GetHeapHandle. GetHeapHandle() must return the
//   // most recent value provided to SetHeapHandle() or HeapHandle::Invalid().
//   // In some implementations, where GetHeapHandle() can independently
//   // reproduce the correct value, it is possible that SetHeapHandle() does
//   // nothing.
//   void SetHeapHandle(T*, HeapHandle);
//
//   // Clears the heap handle associated with the given element. After calling
//   // this GetHeapHandle() must return HeapHandle::Invalid().
//   void ClearHeapHandle(T*);
//
// The default implementation of HeapHandleAccess assumes that your type
// provides HeapHandle storage and will simply forward these calls to equivalent
// member functions on the type T:
//
//   void T::SetHeapHandle(HeapHandle)
//   void T::ClearHeapHandle()
//   HeapHandle T::GetHeapHandle() const
//
// The WithHeapHandle and InternalHeapHandleStorage classes in turn provide
// implementations of that contract.
//
// In summary, to provide heap handle support for your type, you can do one of
// the following (from most manual / least magical, to least manual / most
// magical):
//
// 0. use a custom HeapHandleAccessor, and implement storage however you want;
// 1. use the default HeapHandleAccessor, and manually provide storage on your
//    your element type and implement the IntrusiveHeap contract;
// 2. use the default HeapHandleAccessor, and endow your type with handle
//    storage by deriving from a helper class (see InternalHeapHandleStorage);
//    or,
// 3. use the default HeapHandleAccessor, and wrap your type in a container that
//    provides handle storage (see WithHeapHandle<T>).
//
// Approach 0 is suitable for custom types that already implement something akin
// to heap handles, via back pointers or any other mechanism, but where the
// storage is external to the objects in the heap. If you already have the
// ability to determine where in a container an object lives despite it
// being moved, then you don't need the overhead of storing an actual HeapHandle
// whose value can be inferred.
//
// Approach 1 is is suitable in cases like the above, but where the data
// allowing you to determine the index of an element in a container is stored
// directly in the object itself.
//
// Approach 2 is suitable for types whose declarations you control, where you
// are able to use inheritance.
//
// Finally, approach 3 is suitable when you are storing PODs, or a type whose
// declaration you can not change.
//
// Most users should be using approach 2 or 3.

#include <algorithm>
#include <compare>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <type_traits>
#include <utility>
#include <vector>

#include "base/base_export.h"
#include "base/check.h"
#include "base/check_op.h"
#include "base/compiler_specific.h"
#include "base/memory/ptr_util.h"
#include "base/ranges/algorithm.h"
#include "base/ranges/from_range.h"
#include "third_party/abseil-cpp/absl/container/inlined_vector.h"

namespace base {

// Intended as a wrapper around an |index_| in the vector storage backing an
// IntrusiveHeap. A HeapHandle is associated with each element in an
// IntrusiveHeap, and is maintained by the heap as the object moves around
// within it. It can be used to subsequently remove the element, or update it
// in place.
class BASE_EXPORT HeapHandle { … };

// The default HeapHandleAccessor, which simply forwards calls to the underlying
// type.
template <typename T>
struct DefaultHeapHandleAccessor { … };

// Intrusive heap class. This is something like a std::vector (insertion and
// removal are similar, objects don't have a fixed address in memory) crossed
// with a std::set (elements are considered immutable once they're in the
// container).
template <typename T,
          typename Compare = std::less<T>,
          typename HeapHandleAccessor = DefaultHeapHandleAccessor<T>>
class IntrusiveHeap {
 private:
  using UnderlyingType = std::vector<T>;

 public:
  //////////////////////////////////////////////////////////////////////////////
  // Types.

  using value_type = typename UnderlyingType::value_type;
  using size_type = typename UnderlyingType::size_type;
  using difference_type = typename UnderlyingType::difference_type;
  using value_compare = Compare;
  using heap_handle_accessor = HeapHandleAccessor;

  using reference = typename UnderlyingType::reference;
  using const_reference = typename UnderlyingType::const_reference;
  using pointer = typename UnderlyingType::pointer;
  using const_pointer = typename UnderlyingType::const_pointer;

  // Iterators are read-only.
  using iterator = typename UnderlyingType::const_iterator;
  using const_iterator = typename UnderlyingType::const_iterator;
  using reverse_iterator = typename UnderlyingType::const_reverse_iterator;
  using const_reverse_iterator =
      typename UnderlyingType::const_reverse_iterator;

  //////////////////////////////////////////////////////////////////////////////
  // Lifetime.

  // Constructs an empty heap, with the default comparator and handle accessor.
  IntrusiveHeap() = default;
  // Constructs an empty heap.
  IntrusiveHeap(const value_compare& comp, const heap_handle_accessor& access)
      : … { … }

  // Constructs a heap containing all elements in the `range`.
  template <class Range>
    requires(std::ranges::input_range<Range>)
  IntrusiveHeap(base::from_range_t,
                Range&& range,
                const value_compare& comp = value_compare(),
                const heap_handle_accessor& access = heap_handle_accessor())
      : impl_(comp, access) { … }

  // Construct a heap with elements from `[first, last)`. Prefer the
  // `from_range_t` constructor as it avoid iterator pairs.
  //
  // # Safety
  // The `first` and `last` must be a valid iterator pair for a container with
  // `first <= last` or Undefined Behaviour results.
  template <class InputIterator>
    requires(std::input_iterator<InputIterator>)
  UNSAFE_BUFFER_USAGE IntrusiveHeap(
      InputIterator first,
      InputIterator last,
      const value_compare& comp = value_compare(),
      const heap_handle_accessor& access = heap_handle_accessor())
      : impl_(comp, access) { … }

  // Moves an intrusive heap. The outstanding handles remain valid and end up
  // pointing to the new heap.
  IntrusiveHeap(IntrusiveHeap&& other) = default;

  // Copy constructor for an intrusive heap.
  IntrusiveHeap(const IntrusiveHeap&);

  // Initializer list constructor.
  template <typename U>
  IntrusiveHeap(std::initializer_list<U> ilist,
                const value_compare& comp = value_compare(),
                const heap_handle_accessor& access = heap_handle_accessor())
      : impl_(comp, access) { … }

  ~IntrusiveHeap();

  //////////////////////////////////////////////////////////////////////////////
  // Assignment.

  IntrusiveHeap& operator=(IntrusiveHeap&&) noexcept;
  IntrusiveHeap& operator=(const IntrusiveHeap&);
  IntrusiveHeap& operator=(std::initializer_list<value_type> ilist);

  //////////////////////////////////////////////////////////////////////////////
  // Element access.
  //
  // These provide O(1) const access to the elements in the heap. If you wish to
  // modify an element in the heap you should first remove it from the heap, and
  // then reinsert it into the heap, or use the "Replace*" helper functions. In
  // the rare case where you directly modify an element in the heap you can
  // subsequently repair the heap with "Update".

  const_reference at(size_type pos) const { … }
  const_reference at(HeapHandle pos) const { … }
  const_reference operator[](size_type pos) const { … }
  const_reference operator[](HeapHandle pos) const { … }
  const_reference front() const { … }
  const_reference back() const { … }
  const_reference top() const { … }

  // May or may not return a null pointer if size() is zero.
  const_pointer data() const { … }

  //////////////////////////////////////////////////////////////////////////////
  // Memory management.

  void reserve(size_type new_capacity) { … }
  size_type capacity() const { … }
  void shrink_to_fit() { … }

  //////////////////////////////////////////////////////////////////////////////
  // Size management.

  void clear();
  size_type size() const { … }
  size_type max_size() const { … }
  bool empty() const { … }

  //////////////////////////////////////////////////////////////////////////////
  // Iterators.
  //
  // Only constant iterators are allowed.

  const_iterator begin() const { … }
  const_iterator cbegin() const { … }

  const_iterator end() const { … }
  const_iterator cend() const { … }

  const_reverse_iterator rbegin() const { … }
  const_reverse_iterator crbegin() const { … }

  const_reverse_iterator rend() const { … }
  const_reverse_iterator crend() const { … }

  //////////////////////////////////////////////////////////////////////////////
  // Insertion (these are std::multiset like, with no position hints).
  //
  // All insertion operations invalidate iterators, pointers and references.
  // Handles remain valid. Insertion of one element is amortized O(lg size)
  // (occasional O(size) cost if a new vector allocation is required).

  const_iterator insert(const value_type& value) { … }
  const_iterator insert(value_type&& value) { … }

  // Inserts all elements in `range` into the heap.
  template <class Range>
    requires(std::ranges::input_range<Range>)
  void insert_range(Range&& range) { … }

  // Inserts all elements in `[first, last)` into the heap. Prefer to use
  // `insert_range()` as it avoids iterator pairs.
  //
  // # Safety
  // The `first` and `last` must be a valid iterator pair for a container with
  // `first <= last` or Undefined Behaviour results.
  template <class InputIterator>
    requires(std::input_iterator<InputIterator>)
  UNSAFE_BUFFER_USAGE void insert(InputIterator first, InputIterator last) { … }

  template <typename... Args>
  const_iterator emplace(Args&&... args) { … }

  //////////////////////////////////////////////////////////////////////////////
  // Removing elements.
  //
  // Erasing invalidates all outstanding iterators, pointers and references.
  // Handles remain valid. Removing one element is amortized O(lg size)
  // (occasional O(size) cost if a new vector allocation is required).
  //
  // Note that it is safe for the element being removed to be in an invalid
  // state (modified such that it may currently violate the heap property)
  // when this called.

  // Takes the element from the heap at the given position, erasing that entry
  // from the heap. This can only be called if |value_type| is movable.
  value_type take(size_type pos);

  // Version of take that will accept iterators and handles. This can only be
  // called if |value_type| is movable.
  template <typename P>
  value_type take(P pos) { … }

  // Takes the top element from the heap.
  value_type take_top() { … }

  // Erases the element at the given position |pos|.
  void erase(size_type pos);

  // Version of erase that will accept iterators and handles.
  template <typename P>
  void erase(P pos) { … }

  // Removes the element at the top of the heap (accessible via "top", or
  // "front" or "take").
  void pop() { … }

  // Erases every element that matches the predicate. This is done in-place for
  // maximum efficiency. Also, to avoid re-entrancy issues, elements are deleted
  // at the very end.
  // Note: This function is currently tuned for a use-case where there are
  // usually 8 or less elements removed at a time. Consider adding a template
  // parameter if a different tuning is needed.
  template <typename Functor>
  void EraseIf(Functor predicate) { … }

  //////////////////////////////////////////////////////////////////////////////
  // Updating.
  //
  // Amortized cost of O(lg size).

  // Replaces the element corresponding to |handle| with a new |element|.
  const_iterator Replace(size_type pos, const T& element) { … }
  const_iterator Replace(size_type pos, T&& element) { … }

  // Versions of Replace that will accept handles and iterators.
  template <typename P>
  const_iterator Replace(P pos, const T& element) { … }
  template <typename P>
  const_iterator Replace(P pos, T&& element) { … }

  // Replaces the top element in the heap with the provided element.
  const_iterator ReplaceTop(const T& element) { … }
  const_iterator ReplaceTop(T&& element) { … }

  // Causes the object at the given location to be resorted into an appropriate
  // position in the heap. To be used if the object in the heap was externally
  // modified, and the heap needs to be repaired. This only works if a single
  // heap element has been modified, otherwise the behaviour is undefined.
  const_iterator Update(size_type pos);
  template <typename P>
  const_iterator Update(P pos) { … }

  // Applies a modification function to the object at the given location, then
  // repairs the heap. To be used to modify an element in the heap in-place
  // while keeping the heap intact.
  template <typename P, typename UnaryOperation>
  const_iterator Modify(P pos, UnaryOperation unary_op) { … }

  //////////////////////////////////////////////////////////////////////////////
  // Access to helper functors.

  const value_compare& value_comp() const { … }

  const heap_handle_accessor& heap_handle_access() const { … }

  //////////////////////////////////////////////////////////////////////////////
  // General operations.

  void swap(IntrusiveHeap& other) noexcept;
  friend void swap(IntrusiveHeap& lhs, IntrusiveHeap& rhs) { lhs.swap(rhs); }

  // Comparison operators. These check for exact equality. Two heaps that are
  // semantically equivalent (contain the same elements, but in different
  // orders) won't compare as equal using these operators.
  friend bool operator==(const IntrusiveHeap& lhs, const IntrusiveHeap& rhs) {
    return lhs.impl_.heap_ == rhs.impl_.heap_;
  }

  //////////////////////////////////////////////////////////////////////////////
  // Utility functions.

  // Converts iterators and handles to indices. Helpers for templated versions
  // of insert/erase/Replace.
  size_type ToIndex(HeapHandle handle) { … }
  size_type ToIndex(const_iterator pos);
  size_type ToIndex(const_reverse_iterator pos);

 private:
  // Templated version of ToIndex that lets insert/erase/Replace work with all
  // integral types.
  template <typename I, typename = std::enable_if_t<std::is_integral_v<I>>>
  size_type ToIndex(I pos) { … }

  // Returns the last valid index in |heap_|.
  size_type GetLastIndex() const { … }

  // Helper functions for setting heap handles.
  void SetHeapHandle(size_type i);
  void ClearHeapHandle(size_type i);
  HeapHandle GetHeapHandle(size_type i);

  // Helpers for doing comparisons between elements inside and outside of the
  // heap.
  bool Less(size_type i, size_type j);
  bool Less(const T& element, size_type i);
  bool Less(size_type i, const T& element);

  // The following function are all related to the basic heap algorithm
  // underpinning this data structure. They are templated so that they work with
  // both movable (U = T&&) and non-movable (U = const T&) types.

  // Primitive helpers for adding removing / elements to the heap. To minimize
  // moves, the heap is implemented by making a hole where an element used to
  // be (or where a new element will soon be), and moving the hole around,
  // before finally filling the hole or deleting the entry corresponding to the
  // hole.
  void MakeHole(size_type pos);
  template <typename U>
  void FillHole(size_type hole, U element);
  void MoveHole(size_type new_hole_pos, size_type old_hole_pos);

  // Moves a hold up the tree and fills it with the provided |element|. Returns
  // the final index of the element.
  template <typename U>
  size_type MoveHoleUpAndFill(size_type hole_pos, U element);

  // Moves a hole down the tree and fills it with the provided |element|. If
  // |kFillWithLeaf| is true it will deterministically move the hole all the
  // way down the tree, avoiding a second comparison per level, before
  // potentially moving it back up the tree.
  struct WithLeafElement {
    static constexpr bool kIsLeafElement = true;
  };
  struct WithElement {
    static constexpr bool kIsLeafElement = false;
  };
  template <typename FillElementType, typename U>
  size_type MoveHoleDownAndFill(size_type hole_pos, U element);

  // Implementation of Insert and Replace built on top of the MoveHole
  // primitives.
  template <typename U>
  const_iterator InsertImpl(U element);
  template <typename U>
  const_iterator ReplaceImpl(size_type pos, U element);
  template <typename U>
  const_iterator ReplaceTopImpl(U element);

  // To support comparators that may not be possible to default-construct, we
  // have to store an instance of value_compare. Using this to store all
  // internal state of IntrusiveHeap and using private inheritance to store
  // compare lets us take advantage of an empty base class optimization to avoid
  // extra space in the common case when Compare has no state.
  struct Impl : private value_compare, private heap_handle_accessor {
    Impl(const value_compare& value_comp,
         const heap_handle_accessor& heap_handle_access)
        : value_compare(value_comp), heap_handle_accessor(heap_handle_access) {}

    Impl() = default;
    Impl(Impl&&) = default;
    Impl(const Impl&) = default;
    Impl& operator=(Impl&& other) = default;
    Impl& operator=(const Impl& other) = default;

    const value_compare& get_value_compare() const { return *this; }
    value_compare& get_value_compare() { return *this; }

    const heap_handle_accessor& get_heap_handle_access() const { return *this; }
    heap_handle_accessor& get_heap_handle_access() { return *this; }

    // The items in the heap.
    UnderlyingType heap_;
  } impl_;
};

// Helper class to endow an object with internal HeapHandle storage. By deriving
// from this type you endow your class with self-owned storage for a HeapHandle.
// This is a move-only type so that the handle follows the element across moves
// and resizes of the underlying vector.
class BASE_EXPORT InternalHeapHandleStorage { … };

// Spiritually akin to a std::pair<T, std::unique_ptr<HeapHandle>>. Can be used
// to wrap arbitrary types and provide them with a HeapHandle, making them
// appropriate for use in an IntrusiveHeap. This is a move-only type.
template <typename T>
class WithHeapHandle : public InternalHeapHandleStorage { … };

////////////////////////////////////////////////////////////////////////////////
// IMPLEMENTATION DETAILS

namespace intrusive_heap {

BASE_EXPORT inline size_t ParentIndex(size_t i) { … }

BASE_EXPORT inline size_t LeftIndex(size_t i) { … }

template <typename HandleType>
bool IsInvalid(const HandleType& handle) { … }

BASE_EXPORT inline void CheckInvalidOrEqualTo(HeapHandle handle, size_t index) { … }

}  // namespace intrusive_heap

////////////////////////////////////////////////////////////////////////////////
// IntrusiveHeap

template <typename T, typename Compare, typename HeapHandleAccessor>
IntrusiveHeap<T, Compare, HeapHandleAccessor>::IntrusiveHeap(
    const IntrusiveHeap& other)
    : … { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
IntrusiveHeap<T, Compare, HeapHandleAccessor>::~IntrusiveHeap() { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
IntrusiveHeap<T, Compare, HeapHandleAccessor>&
IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
    IntrusiveHeap&& other) noexcept { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
IntrusiveHeap<T, Compare, HeapHandleAccessor>&
IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
    const IntrusiveHeap& other) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
IntrusiveHeap<T, Compare, HeapHandleAccessor>&
IntrusiveHeap<T, Compare, HeapHandleAccessor>::operator=(
    std::initializer_list<value_type> ilist) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::clear() { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::value_type
IntrusiveHeap<T, Compare, HeapHandleAccessor>::take(size_type pos) { … }

// This is effectively identical to "take", but it avoids an unnecessary move.
template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::erase(size_type pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
IntrusiveHeap<T, Compare, HeapHandleAccessor>::Update(size_type pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::swap(
    IntrusiveHeap& other) noexcept { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
IntrusiveHeap<T, Compare, HeapHandleAccessor>::ToIndex(const_iterator pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
IntrusiveHeap<T, Compare, HeapHandleAccessor>::ToIndex(
    const_reverse_iterator pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::SetHeapHandle(size_type i) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::ClearHeapHandle(
    size_type i) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
HeapHandle IntrusiveHeap<T, Compare, HeapHandleAccessor>::GetHeapHandle(
    size_type i) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(size_type i,
                                                         size_type j) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(const T& element,
                                                         size_type i) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
bool IntrusiveHeap<T, Compare, HeapHandleAccessor>::Less(size_type i,
                                                         const T& element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::MakeHole(size_type pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename U>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::FillHole(size_type hole_pos,
                                                             U element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
void IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHole(
    size_type new_hole_pos,
    size_type old_hole_pos) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename U>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHoleUpAndFill(
    size_type hole_pos,
    U element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename FillElementType, typename U>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::size_type
IntrusiveHeap<T, Compare, HeapHandleAccessor>::MoveHoleDownAndFill(
    size_type hole_pos,
    U element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename U>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
IntrusiveHeap<T, Compare, HeapHandleAccessor>::InsertImpl(U element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename U>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
IntrusiveHeap<T, Compare, HeapHandleAccessor>::ReplaceImpl(size_type pos,
                                                           U element) { … }

template <typename T, typename Compare, typename HeapHandleAccessor>
template <typename U>
typename IntrusiveHeap<T, Compare, HeapHandleAccessor>::const_iterator
IntrusiveHeap<T, Compare, HeapHandleAccessor>::ReplaceTopImpl(U element) { … }

////////////////////////////////////////////////////////////////////////////////
// WithHeapHandle

template <typename T>
template <class... Args>
WithHeapHandle<T>::WithHeapHandle(Args&&... args)
    : value_(std::forward<Args>(args)...) { … }

template <typename T>
void WithHeapHandle<T>::swap(WithHeapHandle& other) noexcept { … }

}  // namespace base

#endif  // BASE_CONTAINERS_INTRUSIVE_HEAP_H_