Priority Queues using std::priority_queue

Priority Queue with Custom Container

Can I use a custom container as the underlying container for a priority queue?

Illustration representing computer hardware

Yes, you can use a custom container as the underlying container for a std::priority_queue in C++. The std::priority_queue is a container adapter that uses another container internally to store the elements. By default, it uses std::vector as the underlying container, but you can specify a different container type as a template argument.

To use a custom container with std::priority_queue, the container must meet certain requirements. It should provide the following operations:

  • front(): Returns a reference to the first element in the container.
  • push_back(): Appends an element to the end of the container.
  • pop_back(): Removes the last element from the container.
  • size(): Returns the number of elements in the container.
  • empty(): Checks if the container is empty.

Here's an example of using a custom container with std::priority_queue:

#include <deque>
#include <iostream>
#include <queue>

template <typename T>
class CustomContainer {
  std::deque<T> data;

  using value_type = T;
  using size_type = std::deque<T>::size_type;
  using reference = std::deque<T>::reference;
  using const_reference
    = std::deque<T>::const_reference;
  using iterator = std::deque<T>::iterator;
  using const_iterator
    = std::deque<T>::const_iterator;

  void push_back(const T& value) {
    data.push_back(value); }

  void pop_back() { data.pop_back(); }

  reference front() { return data.front(); }

  const_reference front() const {
    return data.front(); }

  size_type size() const { return data.size(); }

  bool empty() const { return data.empty(); }

  iterator begin() { return data.begin(); }

  const_iterator begin() const {
    return data.begin(); }

  iterator end() { return data.end(); }

  const_iterator end() const {
    return data.end(); }

int main() {
    CustomContainer<int>> pq;


  while (!pq.empty()) {
    std::cout << << " ";

In this example, we define a custom container CustomContainer that wraps a std::deque internally. The CustomContainer provides the necessary operations required by std::priority_queue, such as push_back(), pop_back(), front(), size(), and empty().

It also provides the required random access iterators, through begin() and end() methods.

We create a priority queue pq using std::priority_queue and specify CustomContainer<int> as the underlying container type.

We push elements into the priority queue using pq.push(), and then we print the elements in the order they are retrieved from the queue using and pq.pop().

The output of this code will be:

30 20 10

By using a custom container, you have more control over the internal storage and behavior of the priority queue. You can implement custom optimizations, additional functionality, or use a different data structure altogether, as long as it meets the requirements of the priority queue.

However, it's important to ensure that the custom container provides efficient implementations of the required operations to maintain the performance characteristics of the priority queue.

Answers to questions are automatically generated and may not have been reviewed.

A computer programmer
Part of the course:

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

This course includes:

  • 124 Lessons
  • 550+ Code Samples
  • 96% Positive Reviews
  • Regularly Updated
  • Help and FAQ
Free, Unlimited Access

Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Screenshot from Warhammer: Total War
Screenshot from Tomb Raider
Screenshot from Jedi: Fallen Order
Contact|Privacy Policy|Terms of Use
Copyright © 2024 - All Rights Reserved