bslstl_priorityqueue

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Memory Allocation
    • VALUE and CONTAINER::value_type
  • Operations
  • Usage
    • Example 1: Task Scheduler

Purpose

Provide container adapter class template priority_queue .

Classes

• bsl::priority_queue: template of highest-priority-first data structure

Canonical header: bsl_queue.h

See also

bslstl_queue, bslstl_stack

Description

This component defines a class template, bsl::priority_queue, holding a container (of a template parameter type, CONTAINER, containing elements of another template parameter type, VALUE), and adapting it to provide highest-priority-first priority queue data structure. The component takes a third template parameter type, COMPARATOR, for customized priorities comparison between two elements.

An instantiation of priority_queue is an allocator-aware, value-semantic type whose salient attributes are its size (number of held elements) and the sorted sequence of values (of held elements). If priority_queue is instantiated with a value type, that is not itself value-semantic, then it will not retain all of its value-semantic qualities. A priority_queue cannot be tested for equality, but its value type must be able to be tested for comparing less by its comparator type.

The priority_queue implemented here adheres to the C++11 standard when compiled with a C++11 compiler, and makes the best approximation when compiled with a C++03 compiler. In particular, for C++03 we emulate move semantics, but limit forwarding (in emplace) to const lvalues, and make no effort to emulate noexcept or initializer-lists.

Memory Allocation

The type supplied as an ALLOCATOR template parameter in some of priority_queue constructors determines how the held container (of the (template parameter) type CONTAINER) will allocate memory. A priority_queue supports allocators meeting the requirements of the C++11 standard [17.6.3.5] as long as the held container does. In addition it supports scoped-allocators derived from the bslma::Allocator memory allocation protocol. Clients intending to use bslma-style allocators should use bsl::allocator as the ALLOCATOR template parameter, providing a C++11 standard-compatible adapter for a bslma::Allocator object.

VALUE and CONTAINER::value_type

When the CONTAINER template parameter is omitted the VALUE template parameter specifies the value_type of bsl::vector, the default container type. The VALUE template has no other role.

For C++17 and later, the behavior is undefined unless:

true == bsl::is_same<VALUE, typename CONTAINER::value_type>::value

Prior to C++17, CONTAINER::value_type determines the contained value type and VALUE is simply ignored. The resulting code may work with instances of VALUE (e.g., VALUE is convertible to CONTAINER::value_type) or not (compiler errors).

Operations

The C++11 standard [23.6.4] declares any container type supporting operations front, push_back, and pop_back can be used to instantiate the (template parameter) type CONTAINER. Below is a list of public methods of priority_queue class that are effectively implemented as calling the corresponding operations in the held container (referenced as c).

+--------------------------------------+--------------------------+
| Public methods in 'priority_queue'   | Operation in 'CONTAINER' |
+======================================+==========================+
| void push(const value_type& value);  | c.push_back(value);      |
| void pop();                          | c.pop_back();            |
| void emplace(Args&&... args)         | c.emplace_back(...)      |
+--------------------------------------+--------------------------+
| bool empty() const;                  | c.empty();               |
| size_type size() const;              | c.size();                |
| const_reference top() const;         | c.front();               |
+--------------------------------------+--------------------------+

Usage

In this section we show intended use of this component.

Example 1: Task Scheduler

In this example, we will use the bsl::priority_queue class to implement a task scheduler that schedules a group of tasks based on their designated priorities.

Suppose we want to write a background process that runs tasks needed by foreground applications. Each task has a task id, a priority, and a function pointer that can be invoked by the background process. This background process has two threads: one thread (receiving thread) receives requests from other applications, passing required tasks to a task scheduler; the other thread (processing thread) runs the task scheduler, executing the tasks one-by-one from higher to lower priorities. To implement this functionality, we can use bsl::priority_queue in the task scheduler to buffer received, but as yet unprocessed, tasks. The task scheduler adds newly received tasks into the priority queue in the receiving thread, and extracts tasks from the priority queue for execution according to their priorities in the processing thread.

First, we define a TaskFunction type:

typedef void (*TaskFunction)(int, int, int);

Then, we define a Task class, which contains a task id, a TaskFunction object and an associated task priority:

class Task
    // This class represents a task that has an integer task id, a task
    // function, and an integer priority.  The smaller the numerical value
    // of a priority, the higher the priority.
{
  private:
    // DATA
    int          d_taskId;          // task id
 
    TaskFunction d_taskFunction_p;  // task function
 
    int          d_priority;        // priority of the task
 
  public:
    // CREATORS
    explicit Task(int taskId, TaskFunction taskFunction, int priority);
        // Create a 'Task' object having the specified 'taskId', the
        // specified 'd_taskFunction_p', and the specified 'priority'.
 
    // ACCESSORS
    int getId() const;
        // Return the contained task id.
 
    int getPriority() const;
        // Return the priority of the task.
 
    TaskFunction getFunction() const;
        // Return the contained task function object.
};
 
// CREATORS
Task::Task(int taskId, TaskFunction taskFunction, int priority)
: d_taskId(taskId)
, d_taskFunction_p(taskFunction)
, d_priority(priority)
{
}
 
// ACCESSORS
inline
int Task::getId() const
{
    return d_taskId;
}
 
inline
int Task::getPriority() const
{
    return d_priority;
}
 
inline
TaskFunction Task::getFunction() const
{
    return d_taskFunction_p;
}

Next, we define a functor to compare the priorities of two Task objects:

struct TaskComparator {
    // This 'struct' defines an ordering on 'Task' objects, allowing them
    // to be included in sorted data structures such as
    // 'bsl::priority_queue'.
 
    bool operator()(const Task& lhs, const Task& rhs) const
        // Return 'true' if the priority of the specified 'lhs' is
        // numerically less than that of the specified 'rhs', and 'false'
        // otherwise.  Note that the smaller the value returned by the
        // 'Task::getPriority' method, the higher the priority.
    {
        return lhs.getPriority() > rhs.getPriority();
    }
};

Then, we define a TaskScheduler class that provides methods to hold and schedule unprocessed tasks:

class TaskScheduler {
    // This class holds and schedules tasks to execute.

Here, we define a private data member that is an instantiation of bsl::priority_queue, which uses Task for its VALUE (template parameter) type, bsl::vector<Task> for its CONTAINER (template parameter) type, and TaskComparator for its COMPARATOR (template parameter) type:

    // DATA
    bsl::priority_queue<Task,
                        bsl::vector<Task>,
                        TaskComparator>
          d_taskPriorityQueue;  // priority queue holding unprocessed tasks
 
    // ...
 
  public:
    // CREATORS
    explicit TaskScheduler(bslma::Allocator *basicAllocator = 0);
        // Create a 'TaskScheduler' object.  Optionally specify a
        // 'basicAllocator' used to supply memory.  If 'basicAllocator' is
        // 0, the currently installed default allocator is used.
 
    // MANIPULATORS
    void addTask(int taskId, TaskFunction taskFunction, int priority);
        // Enqueue the specified 'task' having the specified 'priority'
        // onto this scheduler.
 
    void processTasks(int verbose);
        // Dequeue the task having the highest priority in this scheduler,
        // and call its task function by passing in the specified 'verbose'
        // flag.
};

Next, we implement the TaskScheduler constructor:

TaskScheduler::TaskScheduler(bslma::Allocator *basicAllocator)
: d_taskPriorityQueue(basicAllocator)
{
}

Notice that we pass to the contained d_taskPriorityQueue object the bslma::Allocator supplied to the TaskScheduler at construction.

Then, we implement the addTask method, which constructs a Task object and adds it into the priority queue:

void TaskScheduler::addTask(int taskId,
                            TaskFunction taskFunction,
                            int priority)
{
    // ... (some synchronization)
 
    d_taskPriorityQueue.push(Task(taskId, taskFunction, priority));
 
    // ...
}

Next, we implement the processTasks method, which extracts tasks from the priority queue in order of descending priorities, and executes them:

void TaskScheduler::processTasks(int verbose)
{
    // ... (some synchronization)
 
    while (!d_taskPriorityQueue.empty()) {
        const Task& task = d_taskPriorityQueue.top();
        TaskFunction taskFunction = task.getFunction();
        if (taskFunction) {
            taskFunction(task.getId(), task.getPriority(), verbose);
        }
        d_taskPriorityQueue.pop();
    }
 
    // ...
}

Note that the top method always returns the Task object having the highest priority in the priority queue.

Then, we define two task functions:

void taskFunction1(int taskId, int priority, int verbose)
{
    if (verbose) {
        printf("Executing task %d (priority = %d) in 'taskFunction1'.\n",
               taskId,
               priority);
    }
}
 
void taskFunction2(int taskId, int priority, int verbose)
{
    if (verbose) {
        printf("Executing task %d (priority = %d) in 'taskFunction2'.\n",
               taskId,
               priority);
    }
}

Next, we create a global TaskScheduler object:

TaskScheduler taskScheduler;

Now, we call the addTask method of taskScheduler in the receiving thread:

// (in receiving thread)
// ...
 
taskScheduler.addTask(1, taskFunction1, 50);
 
// ...
 
taskScheduler.addTask(2, taskFunction1, 99);
 
// ...
 
taskScheduler.addTask(3, taskFunction2, 4);
 
// ...

Finally, we call the processTasks method of taskScheduler in the processing thread:

// (in processing thread)
// ...
 
taskScheduler.processTasks(veryVerbose);
 
// ...