Implementing a Custom Comparator for C++ Priority Queues

Priority queues are a versatile data structure in C++ that organize elements based on a priority order. By default, priority queues use operator< to establish the priority ordering between elements. However, in some cases you may want to define a custom priority ordering that does not correspond to the default operator< implementation for a data type.

Fortunately, C++ allows specifying custom comparator functions to control the priority ordering of elements in a priority queue. In this comprehensive guide, we will cover various use cases, implementations, performance considerations, and best practices for working with custom comparators.

Common Use Cases for Custom Comparators

There are several reasons you may want to customize the sorting behavior of a priority queue:

Prioritizing by attributes: The default operator< does not match what you want to prioritize on. For example, sorting Person objects by age rather than name.

Reversing default order: You want to reverse the default sort order – like descending rather than ascending.

Tie-breaking: Multiple elements may have the same priority, so you provide a secondary prioritization scheme.

External state: Priority logic that needs access to variables outside just the element values themselves.

Domain-specific sorting: Specialized domains like graphics, simulations, or scheduling have unique ordering requirements not served by the native comparison operators.

Custom comparators allow tailoring priority queues to these kinds of specialized sorting logic in ways built-in operators do not.

Graph Algorithms

For example, in graph traversal algorithms, vertices often need prioritization based on attributes like distance, path cost, or connectivity. Custom comparators provide flexibility to implement specialized queueing logic to optimally traverse graphs.

Popular pathfinding algorithms like A* search use a priority queue optimized for fast vertex selection based on a calculated cost function:

F(n) = G(n) + H(n)

Where G(n) is the cost to reach node n, and H(n) estimates cost to goal.

A custom comparator would prioritize vertices with the lowest F cost:

auto graphCmp = [](const Vertex& a, const Vertex& b) {
  return a.costF() < b.costF();  
};

priority_queue<Vertex, Vector<Vertex>, decltype(graphCmp)> frontier(graphCmp) 

This domain-specific queue prioritization vastly improves performance in graph search and pathfinding.

Function Approximation

Another common use case is numerically approximating functions through simulations. Sorting particles or data points often does not map neatly to default value-based comparisons between objects.

For example, efficiently finding minima/maxima in multidimensional function plots requires sorting points by the Z-axis. This could be done through a simple custom comparator on the Z coordinate regardless of X and Y positions:

auto functionCmp = [](const Point& a, const Point& b) {
  return a.z < b.z;
} 

This allows quickly queueing points by function output value (z) rather than position.

Resource Allocation

In computing, priority queues often schedule jobs, processes, or resource allocation. Custom sorting criteria based on vectors or maps allow flexible policy-based scheduling.

For example, a priority function could combine job priority, waiting time, and resource utilization to make scheduling decisions:

auto jobCmp = [](const Job &a, const Job &b) {
  int aPriority = jobPriorities[a.type]; 
  int bPriority = jobPriorities[b.type];

  int aWait = a.timeWaited;
  int bWait = b.timeWaited;  

  return aPriority + aWait > bPriority + bWait;
}

priority_queue<Job, Vector<Job>, decltype(jobCmp)> scheduler(jobCmp);

This allows configuring sophisticated priority functions unique to the environment and constraints.

Case Study: Task Scheduler

As a more extensive illustration, we will demonstrate using a custom comparator to build a task scheduling service that prioritizes and queues work items by expected effort.

Task Model

First, we define a Task class that stores a name, estimated effort level, complexity, and priority multiplier:

class Task {
public:
  Task(string name, int effortLevel) {
    this->name = name;
    this->baseEffort = effortLevel;
  }

  int getScaledEffort() {
    return baseEffort * priorityFactor;
  }

private:
  string name;

  int baseEffort;

  double complexity = 1.0; 

  int priorityFactor = 1;
}; 

Effort encapsulates the overall expected work to complete the task. This will drive the scheduler priority queue ordering.

Priority Queue Setup

Next we need a custom comparator that can prioritize Tasks by their scaled effort fields:

auto effortCmp = [](const Task& a, const Task& b) {
  return a.getScaledEffort() > b.getScaledEffort();
};

priority_queue<Task, Vector<Task>, decltype(effortCmp)> 
  scheduler(effortCmp); 

With this comparator defined, we can start adding tasks:

Task easyTask("Take out trash", 3);
Task hardTask("Write research paper", 80);

scheduler.push(easyTask);
scheduler.push(hardTask);

And the task queue will now prioritize by computed effort:

Write research paper
Take out trash

Extending Priority Logic

To make the priority more sophisticated, we could easily incorporate other attributes like waiting time, complexity, external policies, etc. Since the comparator has access to the entire Task instance, integrating new logic is straightforward.

For example, multiplying base effort by complexity and priority:

class Task {
  //...

  int getScaledEffort() {
    return baseEffort * complexity * priorityFactor;
  } 
}

int main() {

  Task complexTask(“Analyze data”, 50);
  complexTask.complexity = 2.5;

  Task highPriTask(“Respond to user”, 20);
  highPriTask.priorityFactor = 3;  

  scheduler.push(complexTask); 
  scheduler.push(highPriTask);

  // Will print highPriTask first since priorityFactor 
  // scales effort higher
}

This demonstrates the flexibility of custom comparators to encapsulate shifting sorting requirements separate from core data models.

Additional Examples with Lambdas

C++ lambdas provide a straightforward path for one-off comparator definition without needing to define and maintain custom classes.

Here are some additional examples demonstrating possible approaches:

Reverse string sort

auto revCmp = [](const string& a, const string& b) {
  return a > b;  
} 

priority_queue<string, Vector<string>, decltype(revCmp)> 
  revQueue(revCmp);

Prioritize by timestamp

auto latestTsCmp = [](const Log& a, const Log& b) {
  return a.timestamp > b.timestamp;  
}

priority_queue<Log, Vector<Log>, decltype(latestTsCmp)> 
  logQueue(latestTsCmp);

Breaking ties deterministically

auto tieBreakCmp = [](const Item& a, const Item& b) {
  if (a.priority == b.priority) {
    return a.id < b.id; 
  }
  return a.priority > b.priority;
};

priority_queue<Item, Vector<Item>, decltype(tieBreakCmp)> 
  tieBreakQueue(tieBreakCmp);

In addition to encapsulating policies, lambdas provide access to external state. This example periodically adjusts queue priority based on an external vector:

vector<int> hourPriority; // changes periodically  

auto timeCmp = [&hourPriority](const Task& a, const Task& b) {

  int aHour = getHour(a.timestamp); 
  int bHour = getHour(b.timestamp);

  int aPrio = hourPriority[aHour]; 
  int bPrio = hourPriority[bHour];

  return aPrio > bPrio;   
};

priority_queue<Task, Vector<Task>, decltype(timeCmp)>
  timeQueue(timeCmp);

Performance Impact

Custom comparators provide added flexibility and customizability. However, they can carry a performance penalty compared to standards operators like <.

Reasons for potential performance differences:

• Extra function call overhead to external comparator
• Inability to leverage native type optimizations
• Computationally intensive comparisons
• Breaking strict value-equivalence assumptions

For simple cases, the differences may be negligible – especially with optimizing compilers. But for very large data structures, the penalties could become substantial.

If raw performance is the only concern, overloading a custom operator< directly in the data type can sometimes be faster. However this has downsides for encapsulation and maintenance already discussed.

Overall there is a flexibility vs performance tradeoff to evaluate when choosing between custom comparators vs overloaded operators. Use profiling to quantify differences in your environment.

Comparators vs Overloaded Operators

In addition to custom comparators, C++ allows overloading the native comparison operators like <, == directly within custom data types.

There are pros and cons to each approach:

Custom Comparator

• Keeps sorting logic separate from data
• No changes needed to underlying data types
• Can leverage external state
• Slightly less efficient

Overloaded Operator

• Tighter coupling between data and priority
• Impacts all usage of affected types
• Often faster performance

Overloading operator< effectively is implementing a custom comparator – just bundled directly into the data type itself. This trades flexibility for better potential efficiency.

Using native operators can be a wise performance optimization when you control the data type and universally want to change its comparisons.

But separating sorting policies into custom comparators keeps priority queue usage decoupled. The same data models can then work across different queue instances with alternate sorting rules.

Comparison Philosophy

Broadly, the choice between custom comparators and overloaded operators represents two schools of thought around handling sorted data:

Coupled: The data model itself knows how to establish internal orderings and comparisons. Operator overloading embeds this knowledge within the data structures.

Decoupled: Sorting semantics live externally to data models. This comes through callback comparators and encapsulates policies separately.

The decoupled approach has notable advantages for reusability, encapsulation, and customization. But often gets sacrificed for marginal efficiency gains by directly embedding the logic.

Comparators provide a "cookie cutter" model for achieving custom orderings that can be freely mixed across various domains and data models at a modest cost of performance. This dynamism and flexibility is the heart of the custom comparator approach.

Validation & Testing

Since comparators encapsulate non-standard ordering logic, they warrant rigorous validity testing before production use. Invalid comparisons could corrupt priority queue behavior.

Unit Testing

Each comparator function should undergo unit testing similar to any other component:

TEST(PriorityCmpTest, OrdersHighEffortFirst) {

  Task easy(“A”, 5);
  Task tough(“B”, 20);

  ASSERT_TRUE(priorityCmp(tough, easy));
}

Invariant Checking

The queue ordering itself should also be continually tested against invariants:

void validatePriorities() {
  auto prev = queue.top(); 
  queue.pop();

  if (!priorityCmp(prev, queue.top())) {
     throw "Invalid priority order";
  }
}

This can catch logical errors that arise as implementations change.

Fuzz & Stress Testing

Fuzz testing with random inputs can reveal edge case weaknesses:

Task fuzzA(randomStr(), randomInt());
Task fuzzB(randomStr(), randomInt());

ASSERT_NO_THROW(priorityCmp(fuzzA, fuzzB));

Load testing will characterize performance limits and regressions.

Comprehensive qualification of custom comparators is essential before trusted production use. Both because they are inherently logical components, and to gain assurance around any performance related surprises.

Real-World Examples

Custom comparators are found across many major C++ libraries and frameworks that leverage priority queues, including:

C++ STL – std::priority_queue itself allows custom comparators

Boost – boost::heap::compare powers the Boost Heap library

Qt – QQueue::sort uses custom compares

ROS – The Robot OS uses priority messaging with topic comparators

ArangoDB – Database query cursors support custom sorting

The widespread adoption further demonstrates the utility of external comparator functions across applications.

Historical Perspective

The ability to customize sorting order separately from core data has long historical importance in computer science. Early examples include:

C qsort() – Released in 1973, the C standard library qsort function allowed custom compares. This influenced later languages.

C++ STL – The original 1993 STL paper covered user-specified sorting via compares. This model continues today.

Java Comparable – Java‘s comparable interface from 1996 allows customizing natural ordering.

C# IComparer – Similarly, C# IComparer dates back to 2002.

The ability to parameterize sorting logic has proven an enormously influential software abstraction. It conferred extensibility enabling mass adoption across languages.

Conclusion

Custom comparators unlock the full potential of the priority queue mechanism. They confer extensibility at a modest cost of efficiency.

Comparators allow priority queues to adapt to specialized domains like AI, scheduling, numeric methods, or algorithm optimizations through stateful and attribute-based ordering. Lambda functions make definition seamless without polluting core data models.

There are long-running software philosophies around the virtues of encapsulating logic apart from the data itself. Comparators manifest this separation of concerns for ordering specifically, and extensively enable cusomизable, policy-rich priority queue designs.

Overall, custom comparators constitute an influential software technique that facilitates highly customizable system architectures by externalizing sorting logic from data. C++ continues this long historical legacy powerfully with modern language features.