Template Class MapBasedQueue

Class Documentation

template<class item_t>
class MapBasedQueue

Templatized interface for a priority queue.

This is faster than the std::priority_queue implementation in certain cases because iterating does not require resorting after every element is examined. Based on https://github.com/ros-planning/navigation/pull/525 The relative speed of this against the priority queue depends how many items with each priority are inserted into the queue.

One additional speed up depends on the patterns of priorities during each iteration of the queue. If the same priorities are inserted into the queue on every iteration, then it is quicker to set reset_bins = false, such that the priority bins are not reset and will not have to be recreated on each iteration.

Public Functions

inline explicit MapBasedQueue(bool reset_bins = true)

Default Constructor.

virtual ~MapBasedQueue() = default

Default virtual Destructor.

inline virtual void reset()

Clear the queue.

inline void enqueue(const double priority, item_t item)

Add a new item to the queue with a set priority.

Parameters:
  • priority – Priority of the item

  • item – Payload item

inline bool isEmpty()

Check to see if there is anything in the queue.

Must be called prior to front/pop.

Returns:

True if there is nothing in the queue

inline item_t &front()

Return the item at the front of the queue.

Returns:

The item at the front of the queue

inline void pop()

Remove (and destroy) the item at the front of the queue.

Protected Types

using ItemMap = std::map<double, std::vector<item_t>>
using ItemMapIterator = typename ItemMap::iterator

Protected Attributes

bool reset_bins_
ItemMap item_bins_
unsigned int item_count_
ItemMapIterator iter_
ItemMapIterator last_insert_iter_