gum::Heap< Val, Cmp, Alloc > Class Template Reference

Heap data structureThis structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering. More...

#include <agrum/core/heap.h>

Public Member Functions
Constructors / Destructors
	Heap (Cmp compare=Cmp(), Size capacity=GUM_HEAP_DEFAULT_CAPACITY)
	Basic constructor: creates an empty heap. More...
	Heap (std::initializer_list< Val > list)
	Initializer list constructor. More...
	Heap (const Heap< Val, Cmp, Alloc > &from)
	Copy constructor. More...
template<typename OtherAlloc >
	Heap (const Heap< Val, Cmp, OtherAlloc > &from)
	Generalized copy constructor. More...
	Heap (Heap< Val, Cmp, Alloc > &&from) noexcept
	Move constructor. More...
	~Heap ()
	Class destructor. More...
Operators
Heap< Val, Cmp, Alloc > &	operator= (const Heap< Val, Cmp, Alloc > &from)
	Copy operator. More...
template<typename OtherAlloc >
Heap< Val, Cmp, Alloc > &	operator= (const Heap< Val, Cmp, OtherAlloc > &from)
	Generalized copy operator. More...
Heap< Val, Cmp, Alloc > &	operator= (Heap< Val, Cmp, Alloc > &&from) noexcept
	Move operator. More...
const Val &	operator[] (Size index_elt) const
	Returns the element at index index_elt from the heap. More...
Accessors / Modifiers
const Val &	top () const
	Returns the element at the top of the heap. More...
Val	pop ()
	Removes the top element from the heap and return it. More...
void	eraseTop ()
	Removes the top of the heap (but does not return it). More...
void	eraseByPos (Size index)
	Removes the element positioned at "index" from the heap. More...
void	erase (const Val &val)
	Removes a given element from the heap (but does not return it). More...
Size	insert (const Val &val)
	inserts a new element (actually a copy) in the heap and returns its index More...
Size	insert (Val &&val)
	Inserts a new element (by moving it) in the heap and returns its index. More...
template<typename... Args>
Size	emplace (Args &&... args)
	Emplace a new element in the heap and returns its index. More...
Size	size () const noexcept
	Returns the number of elements in the heap. More...
bool	empty () const noexcept
	Indicates whether the heap is empty. More...
bool	contains (const Val &) const
	Indicates whether the heap contains a given value. More...
std::string	toString () const
Fine tuning
Size	capacity () const noexcept
	Returns the size of the internal structure storing the heap. More...
void	resize (Size new_size)
	Changes the size of the the internal structure storing the heap. More...

Public Types
using	value_type = Val
	Types for STL compliance. More...
using	reference = Val &
	Types for STL compliance. More...
using	const_reference = const Val &
	Types for STL compliance. More...
using	pointer = Val *
	Types for STL compliance. More...
using	const_pointer = const Val *
	Types for STL compliance. More...
using	size_type = std::size_t
	Types for STL compliance. More...
using	difference_type = std::ptrdiff_t
	Types for STL compliance. More...
using	allocator_type = Alloc
	Types for STL compliance. More...

Detailed Description

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>
class gum::Heap< Val, Cmp, Alloc >

Heap data structure

This structure is a basic heap data structure, i.e., it is a container in which elements are sorted according to a weak ordering.

Given this ordering, we do have access in O(1) to the "smallest" element contained by the structure. Insertions and deletions of elements are processed in O(ln n), where n is the number of elements in the heap. In addition to the classical pop, top and push functions, Heap provide direct accessors to the elements in the heap (see operator[]). However, these can only be accessed in read-only mode.

Usage example:

// create a heap of integers, the top element is the smallest element
Heap<int> heap1;

// create a heap of floats, the top element is the greatest
Heap<float> heap2 (std::greater<float>());

// insert elements into the heap
heap1.insert (8);
heap1.insert (10);
heap1.insert (2);
heap1.insert (23);
heap1.insert (24);
heap1.insert (10);
heap1.insert (10);

// copy a heap into another
Heap<int> heap2 = heap1;

// get the number of elements of the heap
std::cerr << heap2.size() << std::endl;

// get the top element but do not remove it
std::cerr << heap2.top() << std::endl;

// get and remove the top element of the heap
std::cerr << heap2.pop() << std::endl;

// remove the top element but do not return it (faster than above)
heap2.eraseTop();

// erase in heap1 value 8
heap1.eraseByVal (8);

// erase element at position 3 (see function erase for the
// meaning of position 3)
heap1.erase (3);

// get the element at position 3
heap1[3];

// check whether element 24 belongs to the heap
heap1.contains (24);

Template Parameters

Val	The gum::Heap values type.
Cmp	The comperator used to sort elements in the gum::Heap.
Alloc	The allocator of elements stored in the gum::Heap.

Definition at line 48 of file heap.h.

Member Typedef Documentation

allocator_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::allocator_type = Alloc

Types for STL compliance.

Definition at line 135 of file heap.h.

const_pointer

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::const_pointer = const Val*

Types for STL compliance.

Definition at line 132 of file heap.h.

const_reference

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::const_reference = const Val&

Types for STL compliance.

Definition at line 130 of file heap.h.

difference_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::difference_type = std::ptrdiff_t

Types for STL compliance.

Definition at line 134 of file heap.h.

pointer

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::pointer = Val*

Types for STL compliance.

Definition at line 131 of file heap.h.

reference

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::reference = Val&

Types for STL compliance.

Definition at line 129 of file heap.h.

size_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::size_type = std::size_t

Types for STL compliance.

Definition at line 133 of file heap.h.

value_type

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

using gum::Heap< Val, Cmp, Alloc >::value_type = Val

Types for STL compliance.

Definition at line 128 of file heap.h.

Constructor & Destructor Documentation

Heap() [1/5]

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::Heap ( Cmp  compare = Cmp(), Size  capacity = GUM_HEAP_DEFAULT_CAPACITY  )

explicit

Basic constructor: creates an empty heap.

Parameters

compare	a function taking two elements in argument, say e1 and e2, and returning a Boolean indicating wether e1 < e2, i.e., whether e1 should be nearer than e2 to the top of the heap.
capacity	the size of the internal data structures containing the elements (could be for instance vectors or hashtables).

Definition at line 39 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap.

                                                          : __cmp(compare) {
    __heap.reserve(capacity);

    // for debugging purposes
    GUM_CONSTRUCTOR(Heap);
  }

Heap() [2/5]

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::Heap ( std::initializer_list< Val >  list )

explicit

Initializer list constructor.

Parameters

list	The initializer list.

Definition at line 48 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::insert().

                                                               {
    __heap.reserve(list.size());
    for (const auto& elt : list) {
      insert(elt);
    }

    // for debugging purposes
    GUM_CONSTRUCTOR(Heap);
  }

Here is the call graph for this function:

Heap() [3/5]

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::Heap

(

const Heap< Val, Cmp, Alloc > &

from

)

Copy constructor.

Parameters

from	The gum::Heap to copy.

Definition at line 60 of file heap_tpl.h.

                                                                   :
      __heap(from.__heap), __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
    // for debugging purposes
    GUM_CONS_CPY(Heap);
  }

Heap() [4/5]

template<typename Val , typename Cmp , typename Alloc >

template<typename OtherAlloc >

gum::Heap< Val, Cmp, Alloc >::Heap

(

const Heap< Val, Cmp, OtherAlloc > &

from

)

Generalized copy constructor.

Template Parameters

OtherAlloc

The other gum::Heap allocator.

Parameters

from	The gum::Heap to copy.

Definition at line 69 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                                        :
      __nb_elements(from.__nb_elements), __cmp(from.__cmp) {
    __heap.reserve(__nb_elements);

    // copy the elements of from.__heap
    for (unsigned i = 0; i < __nb_elements; ++i)
      __heap.push_back(from.__heap[i]);

    // for debugging purposes
    GUM_CONS_CPY(Heap);
  }

Heap() [5/5]

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::Heap ( Heap< Val, Cmp, Alloc > &&  from )

noexcept

Move constructor.

Parameters

from	The gum::Heap to move.

Definition at line 83 of file heap_tpl.h.

                                                                       :
      __heap(std::move(from.__heap)), __nb_elements(std::move(from.__nb_elements)),
      __cmp(std::move(from.__cmp)) {
    // for debugging purposes
    GUM_CONS_MOV(Heap);
  }

~Heap()

template<typename Val , typename Cmp , typename Alloc >

gum::Heap< Val, Cmp, Alloc >::~Heap

(

)

Class destructor.

Definition at line 92 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::operator=().

                                 {
    // for debugging purposes
    GUM_DESTRUCTOR(Heap);
  }

Here is the call graph for this function:

Member Function Documentation

__restoreHeap()

template<typename Val , typename Cmp , typename Alloc >

Size gum::Heap< Val, Cmp, Alloc >::__restoreHeap ( )

private

After inserting an element at the end of the heap, restore heap property.

Definition at line 254 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::emplace(), and gum::Heap< Val, Cmp, Alloc >::insert().

                                              {
    // get the element at the end of the heap
    Size i = __nb_elements - 1;
    Val  v = std::move(__heap[i]);

    // restore the heap property
    for (Size j = (i - 1) >> 1; i && __cmp(v, __heap[j]); i = j, j = (j - 1) >> 1)
      __heap[i] = std::move(__heap[j]);

    __heap[i] = std::move(v);

    return i;
  }

Here is the caller graph for this function:

capacity()

template<typename Val , typename Cmp , typename Alloc >

INLINE Size gum::Heap< Val, Cmp, Alloc >::capacity ( ) const

noexcept

Returns the size of the internal structure storing the heap.

Returns

Returns the size of the internal structure storing the heap.

Definition at line 185 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap.

                                                               {
    return Size(__heap.size());
  }

contains()

template<typename Val , typename Cmp , typename Alloc >

INLINE bool gum::Heap< Val, Cmp, Alloc >::contains

(

const Val &

val

)

const

Indicates whether the heap contains a given value.

Returns

Indicates whether the heap contains a given value.

Definition at line 304 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                                    {
    for (Size i = 0; i < __nb_elements; ++i)
      if (__heap[i] == val) return true;

    return false;
  }

emplace()

template<typename Val , typename Cmp , typename Alloc >

template<typename... Args>

Size gum::Heap< Val, Cmp, Alloc >::emplace

(

Args &&...

args

)

Emplace a new element in the heap and returns its index.

Template Parameters

Args	the type of the new element to emplace.

Parameters

args	The new element to emplace.

Returns

The emplaced element position in the gum::Heap.

Definition at line 289 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

                                                      {
    // create a new element at the end of the heap
    __heap.emplace_back(std::forward< Args >(args)...);
    ++__nb_elements;
    return __restoreHeap();
  }

Here is the call graph for this function:

empty()

template<typename Val , typename Cmp , typename Alloc >

INLINE bool gum::Heap< Val, Cmp, Alloc >::empty ( ) const

noexcept

Indicates whether the heap is empty.

Returns

Indicates whether the heap is empty.

Definition at line 298 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                            {
    return (__nb_elements == 0);
  }

erase()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::erase

(

const Val &

val

)

Removes a given element from the heap (but does not return it).

If the element cannot be found, the function returns without throwing any exception.

Parameters

val	The element we wish to remove. If the heap contains several times this element, then the one with the smallest index is removed.

Definition at line 225 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::eraseByPos().

                                                           {
    // find val in the heap
    for (Size i = 0; i < __nb_elements; ++i)
      if (__heap[i] == val) {
        eraseByPos(i);
        break;
      }
  }

Here is the call graph for this function:

eraseByPos()

template<typename Val , typename Cmp , typename Alloc >

void gum::Heap< Val, Cmp, Alloc >::eraseByPos

(

Size

index

)

Removes the element positioned at "index" from the heap.

If the element cannot be found, the function returns without throwing any exception.

Parameters

index

represents the position of the element to be removed. This is computed as follows: suppose that the heap is a complete binary tree, that is, a binary tree where all levels are completely filled except, maybe, the last one and, in this case, the elements of this level are all to the left of the tree. Then parsing the tree from top to bottom and, for each level, from left to right, and assigning index 0 to the root of the tree and, incrementing the index by 1 each time we jump to another node, we get a unique index for each element. This is precisely what the index passed in argument of the function represents.

index

The index of the element to remove

Definition at line 197 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::erase(), gum::Heap< Val, Cmp, Alloc >::eraseTop(), and gum::Heap< Val, Cmp, Alloc >::pop().

                                                     {
    if (index >= __nb_elements) return;

    // remove the element and put the last element in its place
    Val last = std::move(__heap[__nb_elements - 1]);
    __heap.pop_back();
    --__nb_elements;

    if (!__nb_elements || (index == __nb_elements)) return;

    // restore the heap property
    Size i = index;

    for (Size j = (index << 1) + 1; j < __nb_elements; i = j, j = (j << 1) + 1) {
      // let j be the max child
      if ((j + 1 < __nb_elements) && __cmp(__heap[j + 1], __heap[j])) ++j;

      // if "last" is smaller than __heap[j], "last" must be stored at index i
      if (__cmp(last, __heap[j])) break;

      __heap[i] = std::move(__heap[j]);
    }

    __heap[i] = std::move(last);
  }

Here is the caller graph for this function:

eraseTop()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::eraseTop

(

)

Removes the top of the heap (but does not return it).

If the heap is empty, it does nothing (in particular, it does not throw any exception).

Definition at line 236 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::eraseByPos().

                                                {
    // if the heap is empty, do nothing
    if (!__nb_elements) return;
    eraseByPos(0);
  }

Here is the call graph for this function:

insert() [1/2]

template<typename Val , typename Cmp , typename Alloc >

INLINE Size gum::Heap< Val, Cmp, Alloc >::insert

(

const Val &

val

)

inserts a new element (actually a copy) in the heap and returns its index

Parameters

val	The element to insert.

Returns

The inserted element position in the gum::Heap.

Definition at line 270 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

Referenced by gum::Heap< Val, Cmp, Alloc >::Heap().

                                                            {
    // create a new element at the end of the heap
    __heap.push_back(val);
    ++__nb_elements;
    return __restoreHeap();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

insert() [2/2]

template<typename Val , typename Cmp , typename Alloc >

Size gum::Heap< Val, Cmp, Alloc >::insert

(

Val &&

val

)

Inserts a new element (by moving it) in the heap and returns its index.

Parameters

val	The element to insert.

Returns

The inserted element position in the gum::Heap.

Definition at line 279 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::__restoreHeap().

                                                {
    // create a new element at the end of the heap
    __heap.push_back(std::move(val));
    ++__nb_elements;
    return __restoreHeap();
  }

Here is the call graph for this function:

operator=() [1/3]

template<typename Val , typename Cmp , typename Alloc >

Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator=

(

const Heap< Val, Cmp, Alloc > &

from

)

Copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters

from	The gum::Heap to copy.

Definition at line 100 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::Heap< Val, Cmp, Alloc >::operator=(), and gum::Heap< Val, Cmp, Alloc >::~Heap().

                                                                          {
    // avoid self assignment
    if (this != &from) {
      try {
        __heap = from.__heap;
      } catch (...) {
        __heap.clear();
        __nb_elements = 0;

        throw;
      }

      // set the comparison function
      __cmp = from.__cmp;
      __nb_elements = from.__nb_elements;

      // for debugging purposes
      GUM_OP_CPY(Heap);
    }

    return *this;
  }

Here is the caller graph for this function:

operator=() [2/3]

template<typename Val , typename Cmp , typename Alloc >

template<typename OtherAlloc >

Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator=

(

const Heap< Val, Cmp, OtherAlloc > &

from

)

Generalized copy operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Template Parameters

OtherAlloc

The other gum::Heap allocator.

Parameters

from	The gum::Heap to copy.

Definition at line 127 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and gum::Heap< Val, Cmp, Alloc >::operator=().

                                                                               {
    // avoid self assignment
    if (this != &from) {
      try {
        __heap.clear();

        if (__heap.capacity() < from.__nb_elements)
          __heap.reserve(from.__nb_elements);

        for (unsigned int i = 0; i < from.__nb_elements; ++i) {
          __heap.push_back(from.__heap[i]);
        }
      } catch (...) {
        __heap.clear();
        __nb_elements = 0;
        throw;
      }

      __cmp = from.__cmp;
      __nb_elements = from.__nb_elements;

      // for debugging purposes
      GUM_OP_CPY(Heap);
    }

    return *this;
  }

Here is the call graph for this function:

operator=() [3/3]

template<typename Val , typename Cmp , typename Alloc >

Heap< Val, Cmp, Alloc > & gum::Heap< Val, Cmp, Alloc >::operator= ( Heap< Val, Cmp, Alloc > &&  from )

noexcept

Move operator.

When a problem occurs during the copy (for instance when not enough memory is available), the operator guarantees that the heap stays in a coherent state. Actually, the heap becomes empty. An exception is then thrown.

Parameters

from	The gum::Heap to move.

Definition at line 158 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__cmp, gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                                              {
    // avoid self assignment
    if (this != &from) {
      __heap = std::move(from.__heap);
      __nb_elements = std::move(from.__nb_elements);
      __cmp = std::move(from.__cmp);
    }

    return *this;
  }

operator[]()

template<typename Val , typename Cmp , typename Alloc >

INLINE const Val & gum::Heap< Val, Cmp, Alloc >::operator[]

(

Size

index_elt

)

const

Returns the element at index index_elt from the heap.

Parameters

index_elt

The index of the element to return.

Returns

Returns the element at index index_elt from the heap.

Exceptions

NotFound

exception is thrown if there is no element at position "index_elt".

Definition at line 313 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and GUM_ERROR.

                                                                        {
    // check if the element exists
    if (index >= __nb_elements) {
      GUM_ERROR(NotFound, "not enough elements in the heap");
    }

    return __heap[index];
  }

pop()

template<typename Val , typename Cmp , typename Alloc >

INLINE Val gum::Heap< Val, Cmp, Alloc >::pop

(

)

Removes the top element from the heap and return it.

Returns

Returns the top element from the heap.

Exceptions

NotFound

exception is thrown if the heap is empty.

Definition at line 244 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, gum::Heap< Val, Cmp, Alloc >::eraseByPos(), and GUM_ERROR.

                                          {
    if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }

    Val v = __heap[0];
    eraseByPos(0);
    return v;
  }

Here is the call graph for this function:

resize()

template<typename Val , typename Cmp , typename Alloc >

INLINE void gum::Heap< Val, Cmp, Alloc >::resize

(

Size

new_size

)

Changes the size of the the internal structure storing the heap.

If the new size does not enable the heap to contain the elements it currently contains, then the resizing does not occur.

Parameters

new_size

The gum::Heap new size.

Definition at line 191 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                           {
    if (new_size > __nb_elements) __heap.reserve(new_size);
  }

size()

template<typename Val , typename Cmp , typename Alloc >

INLINE Size gum::Heap< Val, Cmp, Alloc >::size ( ) const

noexcept

Returns the number of elements in the heap.

Returns

Returns the number of elements in the heap.

Definition at line 179 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__nb_elements.

                                                           {
    return __nb_elements;
  }

top()

template<typename Val , typename Cmp , typename Alloc >

INLINE const Val & gum::Heap< Val, Cmp, Alloc >::top

(

)

const

Returns the element at the top of the heap.

Returns

Returns the element at the top of the heap.

Exceptions

NotFound

exception is thrown if the heap is empty.

Definition at line 171 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, gum::Heap< Val, Cmp, Alloc >::__nb_elements, and GUM_ERROR.

                                                       {
    if (!__nb_elements) { GUM_ERROR(NotFound, "empty heap"); }

    return __heap[0];
  }

toString()

template<typename Val , typename Cmp , typename Alloc >

std::string gum::Heap< Val, Cmp, Alloc >::toString

(

)

const

Returns

Displays the content of the heap.

Returns a std::string representing the content of the heap.

Definition at line 324 of file heap_tpl.h.

References gum::Heap< Val, Cmp, Alloc >::__heap, and gum::Heap< Val, Cmp, Alloc >::__nb_elements.

Referenced by gum::operator<<().

                                                    {
    bool              deja = false;
    std::stringstream stream;
    stream << "[";

    for (Size i = 0; i != __nb_elements; ++i, deja = true) {
      if (deja) stream << " , ";

      stream << __heap[i];
    }

    stream << "]";

    return stream.str();
  }

Here is the caller graph for this function:

Member Data Documentation

__cmp

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

Cmp gum::Heap< Val, Cmp, Alloc >::__cmp

private

Comparison function.

Definition at line 380 of file heap.h.

Referenced by gum::Heap< Val, Cmp, Alloc >::__restoreHeap(), gum::Heap< Val, Cmp, Alloc >::eraseByPos(), and gum::Heap< Val, Cmp, Alloc >::operator=().

__heap

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

std::vector< Val, Alloc > gum::Heap< Val, Cmp, Alloc >::__heap

private

An array storing all the elements of the heap.

Definition at line 374 of file heap.h.

Referenced by gum::Heap< Val, Cmp, Alloc >::__restoreHeap(), gum::Heap< Val, Cmp, Alloc >::capacity(), gum::Heap< Val, Cmp, Alloc >::contains(), gum::Heap< Val, Cmp, Alloc >::emplace(), gum::Heap< Val, Cmp, Alloc >::erase(), gum::Heap< Val, Cmp, Alloc >::eraseByPos(), gum::Heap< Val, Cmp, Alloc >::Heap(), gum::Heap< Val, Cmp, Alloc >::insert(), gum::Heap< Val, Cmp, Alloc >::operator=(), gum::Heap< Val, Cmp, Alloc >::operator[](), gum::Heap< Val, Cmp, Alloc >::pop(), gum::Heap< Val, Cmp, Alloc >::resize(), gum::Heap< Val, Cmp, Alloc >::top(), and gum::Heap< Val, Cmp, Alloc >::toString().

__nb_elements

template<typename Val, typename Cmp = std::less< Val >, typename Alloc = std::allocator< Val >>

Size gum::Heap< Val, Cmp, Alloc >::__nb_elements {0}

private

The number of elements in the heap.

Definition at line 377 of file heap.h.

Referenced by gum::Heap< Val, Cmp, Alloc >::__restoreHeap(), gum::Heap< Val, Cmp, Alloc >::contains(), gum::Heap< Val, Cmp, Alloc >::emplace(), gum::Heap< Val, Cmp, Alloc >::empty(), gum::Heap< Val, Cmp, Alloc >::erase(), gum::Heap< Val, Cmp, Alloc >::eraseByPos(), gum::Heap< Val, Cmp, Alloc >::eraseTop(), gum::Heap< Val, Cmp, Alloc >::Heap(), gum::Heap< Val, Cmp, Alloc >::insert(), gum::Heap< Val, Cmp, Alloc >::operator=(), gum::Heap< Val, Cmp, Alloc >::operator[](), gum::Heap< Val, Cmp, Alloc >::pop(), gum::Heap< Val, Cmp, Alloc >::resize(), gum::Heap< Val, Cmp, Alloc >::size(), gum::Heap< Val, Cmp, Alloc >::top(), and gum::Heap< Val, Cmp, Alloc >::toString().

---

The documentation for this class was generated from the following files:

• agrum/core/heap.h
• agrum/core/heap_tpl.h