Class templates

This lesson contains approximately 25 minutes of video content.

Motivation

Class templates

Class templates and separate compilation

Activity: Priority queue

Graded Playground Autograder

Activity Prompt:

In this problem, you will implement the class template PriorityQueue. Any type used to instantiate your class template will implement the comparison operators (==, !=, <, >, <=, >=). Our priority queue will maintain a singly linked list of Node<T> typed objects. In your workspace, you can find the definition of Node<T> in includes/node.hpp. The behaviors and data members of PriorityQueue follow:

PriorityQueue Member Functions

public:
PriorityQueue() Default constructor: head_ is initalized to the nullptr.
PriorityQueue(const PriorityQueue<T>& rhs) = delete; Since we have defined a destructor for this type, we must define this function too (per the rule of three). However, we do not need it in this problem. Therefore, you should = delete this function to ensure that the compiler does not generate a definition of it for you.
PriorityQueue<T>& operator=(const PriorityQueue<T>& rhs) = delete; Since we have defined a destructor for this type, we must define this function too (per the rule of three). However, we do not need it in this problem. Therefore, you should = delete this function to ensure that the compiler does not generate a definition of it for you.
~PriorityQueue() Destructor: frees all dynamcially allocated objects comprising the singly linked list.
void Enqueue(const T& data); Inserts a Node<T> storing data into the singly linked list in ascending order.
T Dequeue(); Returns a copy of the data stored in the node pointed to by head_, frees the memory associated with that node object, and updates head_ to point to the next node in the sequence. If the list is empty, an exception should be thrown.

PriorityQueue Data members

private:
Node<T>* head_  

Graded Files

Only the following files are transferred to the autograder.

  • solution.hpp
  • solution.cc
#include "solution.hpp" int main() {}
#ifndef SOLUTION_HPP #define SOLUTION_HPP #endif
#include "solution.hpp"
#ifndef NODE_HPP #define NODE_HPP // DO NOT MODIFY THIS FILE: OUR GRADER USES THE ORIGINAL NODE.HPP PROVIDED TO YOU. // WE DO NOT COPY THIS FILE FROM YOUR WORKSPACE TO OUR AUTO-GRADER. template <typename T> struct Node { T data; // NOLINT Node<T>* next; // NOLINT Node(T data) : data(data), next(nullptr) {} // NOLINT Node(T data, Node<T>* next) : data(data), next(next) {} // NOLINT }; #endif