Priority Queue with Custom Container

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

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 {
 private:
  std::deque<T> data;

 public:
  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() {
  std::priority_queue<int,
    CustomContainer<int>> pq;

  pq.push(10);
  pq.push(30);
  pq.push(20);

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

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 pq.top() 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.

Priority Queues using std::priority_queue

Learn how to access objects based on their importance, and how to customise how that priority is determined

Questions & Answers

Answers are generated by AI models and may not have been reviewed. Be mindful when running any code on your device.

Custom Comparison Function for Priority Queue
How can I define a custom comparison function for a priority queue of custom objects?
Removing a Specific Element from Priority Queue
Is it possible to remove a specific element from a priority queue without popping the top element?
Priority Queue with Unique Elements
How can I ensure that a priority queue contains only unique elements?
Priority Queue with Dynamic Priorities
Can I update the priority of an element already in the priority queue?
Priority Queue with Stable Ordering
How can I ensure stable ordering in a priority queue when elements have the same priority?
Or Ask your Own Question
Get an immediate answer to your specific question using our AI assistant