A priority queue is an abstract data type whose elements have a priority attached to them. Instead of working as a first-in-first-out container, a priority queue makes elements available in the order of their priority. This data structure is used in algorithms such as Dijkstra's shortest path, Prim's algorithm, heap sort, the A* search algorithm, in Huffman codes used for data compression, and others.

A very simple approach to implement a priority queue would be to use an std::vector as the underlying container of elements and always maintain it sorted. That means the maximum and minimum elements are always at the two ends. However, this approach does not provide the most efficient operations.

The most suitable data structure that can be used to implement a priority queue is a heap. This is a tree-based data structure that satisfies the following property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C.

The standard library provides several operations for working with heaps:

• std::make_heap(): This creates a max heap for the given range, using either operator< or a user-provided comparison function to order the elements
• std::push_heap(): This inserts a new element at the end of the max heap
• std::pop_heap(): This removes the first element of the heap (by swapping the values in the first and last position and making the sub-range [first, last-1) a max heap)

A priority queue implementation, that uses std::vector to hold data and the standard functions for heaps, can look as follows:

template <class T,
   class Compare = std::less<typename std::vector<T>::value_type>>
class priority_queue
{
   typedef typename std::vector<T>::value_type value_type;
   typedef typename std::vector<T>::size_type size_type;
   typedef typename std::vector<T>::reference reference;
   typedef typename std::vector<T>::const_reference const_reference;
public:
   bool empty() const noexcept { return data.empty(); }
   size_type size() const noexcept { return data.size(); }

   void push(value_type const & value)
   {
      data.push_back(value);
      std::push_heap(std::begin(data), std::end(data), comparer);
   }

   void pop()
   {
      std::pop_heap(std::begin(data), std::end(data), comparer);
      data.pop_back();
   }

   const_reference top() const { return data.front(); }
   
   void swap(priority_queue& other) noexcept
   {
      swap(data, other.data);
      swap(comparer, other.comparer);
   }
private:
   std::vector<T> data;
   Compare comparer;
};

template<class T, class Compare>
void swap(priority_queue<T, Compare>& lhs,
          priority_queue<T, Compare>& rhs) 
noexcept(noexcept(lhs.swap(rhs)))
{
   lhs.swap(rhs);
}

This class can be used as follows:

int main()
{
   priority_queue<int> q;
   for (int i : {1, 5, 3, 1, 13, 21, 8})
   {
      q.push(i);
   }

   assert(!q.empty());
   assert(q.size() == 7);

   while (!q.empty())
   {
      std::cout << q.top() << ' ';
      q.pop();
   }
}