Anatomy of std::priority_queue in Container Adapter

std::priority_queue is a container adapter in C++ that provides a queue where elements are processed in order of priority. The element with the highest priority is always at the front, allowing for efficient access to and manipulation of the highest-priority elements.

Characteristics:

• Priority-Based Ordering: Elements are ordered based on priority, determined by a comparison function.
• Container Independence: Works with any underlying container that provides random access iterators.

Creation of std::priority_queue:

Creating a std::priority_queue involves declaring an instance and specifying the element type and an optional container type. By default, it used std::vector as the underlying container:

#include <queue>

std::priority_queue<int> myPriorityQueue;  // Default underlying container is std::vector<int>

Basic Operations

Enqueueing Elements:

Adding elements to the priority queue is done using the push member function:

myPriorityQueue.push(7);

Dequeueing Elements:

Removing the highest-priority element from the front of the queue is accomplished with the pop member function:

int highestPriorityElement = myPriorityQueue.top();

Comparison Comparators:

The order of elements is determined by a comparison function. By default, it used operator<, but you can provide a custom comparator:

#include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int>> myMinPriorityQueue;

In this example, std::greater<int> is used to create a min-priority queue.

Functions

1. Element Access:

top():

• Returns a reference to the highest-priority element in the priority queue.

Example:

std::priority_queue<int> myPriorityQueue;
int highestPriorityElement = myPriorityQueue.top();

2. Capacity:

empty():

• Checks if the priority queue is empty.

Example:

std::priority_queue<int> myPriorityQueue;
bool isEmpty = myPriorityQueue.empty();

size():

• Returns the number of elements in the priority queue.

Example:

std::priority_queue<int> myPriorityQueue;
size_t sizeOfPriorityQueue = myPriorityQueue.size();

3. Modifiers:

push(const T& value):

• Adds an element to the priority queue.

Example:

std::priority_queue<int> myPriorityQueue;
myPriorityQueue.push(42);

pop():

• Removes the highest-priority element from the priority queue.

Example:

std::priority_queue<int> myPriorityQueue;
myPriorityQueue.pop();

4. Customization:

Custom Comparators:

• Allows the use of custom comparison functions to determine element priority.

Example:

#include <functional>
std::priority_queue<int, std::vector<int>, std::greater<int>> myMinPriorityQueue;