How to use the priority queue STL for objects?

Mastering Priority Queues in C++ STL for Custom Objects

Learn how to effectively use std::priority_queue with custom objects in C++, including defining custom comparison logic for flexible sorting and real-world applications.

The C++ Standard Template Library (STL) provides a powerful container adapter called std::priority_queue. It's a type of container that provides constant time lookup of the largest (or smallest) element, making it ideal for scenarios like task scheduling, event simulation, or graph algorithms. While it's straightforward to use with fundamental data types, adapting it for custom objects requires understanding how to define comparison operators or provide custom comparators.

Understanding std::priority_queue Basics

A std::priority_queue is implemented as a max-heap by default, meaning the element with the highest 'priority' (largest value) is always at the top. It takes three template parameters: the element type, the underlying container (default std::vector), and the comparison function object (default std::less). When working with custom objects, the key is to inform the priority queue how to compare two instances of your object.

#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    // Expected output: 30 20 10 5
    std::cout << std::endl;
    return 0;
}

A simple example demonstrating std::priority_queue with integers, showing default max-heap behavior.

Using Custom Objects with std::priority_queue

When you want to store custom objects in a priority queue, the std::priority_queue needs a way to determine which object has higher priority. There are two primary ways to achieve this: overloading the operator< for your custom class or providing a custom comparator functor/lambda.

Decision flow for choosing custom comparison methods.

Method 1: Overloading operator<

The simplest approach for custom object comparison is to overload the operator< within your class. This makes your custom objects directly comparable, and std::priority_queue will use this operator by default. The operator< should define what it means for one object to be 'less than' another, which the priority queue will interpret as lower priority.

#include <iostream>
#include <queue>
#include <string>

class Task {
public:
    std::string name;
    int priority;

    Task(std::string n, int p) : name(n), priority(p) {}

    // Overload the less than operator
    // For a max-heap, 'greater' priority means 'less' in comparison
    // So, higher 'priority' value means higher actual priority
    bool operator<(const Task& other) const {
        return priority < other.priority; // For max-heap based on priority value
    }
};

int main() {
    std::priority_queue<Task> taskQueue;

    taskQueue.push(Task("Write Report", 2));
    taskQueue.push(Task("Fix Bug", 5));
    taskQueue.push(Task("Attend Meeting", 3));

    while (!taskQueue.empty()) {
        Task t = taskQueue.top();
        std::cout << "Task: " << t.name << ", Priority: " << t.priority << std::endl;
        taskQueue.pop();
    }
    // Expected output (order might vary for same priority):
    // Task: Fix Bug, Priority: 5
    // Task: Attend Meeting, Priority: 3
    // Task: Write Report, Priority: 2
    return 0;
}

Example of a Task class with an overloaded operator< for priority queue usage. Higher priority value indicates higher actual priority.

Method 2: Custom Comparator Functor or Lambda

If you cannot modify the class (e.g., it's from a library) or need different comparison logic for different priority queues, a custom comparator is the way to go. You can define a functor (a class with an overloaded operator()) or use a C++11 lambda expression. This comparator is passed as the third template argument to std::priority_queue.

#include <iostream>
#include <queue>
#include <string>

struct Product {
    std::string name;
    double price;

    Product(std::string n, double p) : name(n), price(p) {}
};

// Custom comparator for a min-heap based on price
struct CompareProduct {
    bool operator()(const Product& a, const Product& b) {
        return a.price > b.price; // For min-heap: 'a' has lower priority if its price is greater than 'b's
    }
};

int main() {
    std::priority_queue<Product, std::vector<Product>, CompareProduct> minPriceQueue;

    minPriceQueue.push(Product("Laptop", 1200.50));
    minPriceQueue.push(Product("Mouse", 25.00));
    minPriceQueue.push(Product("Keyboard", 75.25));

    while (!minPriceQueue.empty()) {
        Product p = minPriceQueue.top();
        std::cout << "Product: " << p.name << ", Price: " << p.price << std::endl;
        minPriceQueue.pop();
    }
    // Expected output:
    // Product: Mouse, Price: 25
    // Product: Keyboard, Price: 75.25
    // Product: Laptop, Price: 1200.5
    return 0;
}

Using a custom functor CompareProduct to create a min-heap based on product price, where the lowest price has the highest priority.

Using Lambda Expressions as Comparators (C++11 and Later)

Lambda expressions provide a concise way to define inline comparators, often simplifying code, especially when the comparison logic is simple and not reused elsewhere.

#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Item {
    std::string name;
    double value;

    Item(std::string n, double v) : name(n), value(v) {}
};

int main() {
    // Lambda for a max-heap based on 'value'
    auto compareItems = [](const Item& a, const Item& b) {
        return a.value < b.value; // 'a' has lower priority if its value is less than 'b's
    };

    std::priority_queue<Item, std::vector<Item>, decltype(compareItems)> maxValQueue(compareItems);

    maxValQueue.push(Item("Gold Bar", 1800.00));
    maxValQueue.push(Item("Silver Coin", 25.50));
    maxValQueue.push(Item("Diamond", 5000.00));

    while (!maxValQueue.empty()) {
        Item i = maxValQueue.top();
        std::cout << "Item: " << i.name << ", Value: " << i.value << std::endl;
        maxValQueue.pop();
    }
    // Expected output:
    // Item: Diamond, Value: 5000
    // Item: Gold Bar, Value: 1800
    // Item: Silver Coin, Value: 25.5
    return 0;
}

A lambda expression used as a custom comparator to create a max-heap for Item objects based on their value.

1. Step 1

Define your custom class with the data members you need.

2. Step 2

Decide on the priority logic: what makes one object 'greater' or 'lesser' than another?

3. Step 3

If you can modify the class, overload operator< to define the comparison for a max-heap (or operator> for a min-heap with std::priority_queue<T, std::vector<T>, std::less<T>>).

4. Step 4

If you cannot modify the class or need flexible comparison, create a custom comparator (functor or lambda). This comparator should return true if the first argument has lower priority than the second.

5. Step 5

Instantiate std::priority_queue with your custom object type, underlying container (usually std::vector<YourObject>), and your custom comparator (if used).

6. Step 6

Push and pop objects as needed, and the priority queue will maintain the correct order based on your defined logic.