The Interface#

The central piece of the library is the class template dsa::IQueue<Elem, Impl> that specifies the interface of the Queue ADT. It is an abstract class template in the sense that client code cannot instantiate any queue classes from it. All generic implementations of the Queue ADT must statically inherit from it using the Curiously Recurring Template Pattern (CRTP) and fully implement the specified interface via private member functions, so as to become an instantiable class template.

At the topmost level of the library, a free function is defined to destroy a queue on the free store via a base pointer. Although memory (de)allocation of the queue elements is handled automatically by all baked-in implementations, things get complicated when client code take advantage of static polymorphism using pointers of the base type dsa::IQueue<Elem, Impl>, which at run time actually points to some derived type (a concrete implementation of the queue ADT). Having divorced from virtual, a delete expression with a base pointer does not invoke the derived class destructor as desired. Here comes the support function to avoid such pitfall.

In addition, there is also a custom exception class that indicates invalid operations on an empty queue.


Abstract Data Type (ADT)#

template<typename Elem, template<typename> typename Impl>
class IQueue#

The queue abstract data type (ADT)

A sequential ADT that emulates the first-in-first-out behavior of a queue in real world. This class template specifies the API for all implementations of the queue ADT in the cppdsa-queue library.

Note

All implementations of the queue ADT must statically inherit this class template using the Curiously Recurring Template Pattern (CRTP). The inherited class template must implement the private member functions size_(), empty_(), iter_(), front_(), enqueue_(), dequeue_(), and emplace_<...Args>() to realize the functionalty provided by the respective parent class member functions, including all overloads, unless the client code of the inherited class template will not require certain operations. A default implementation for to_string_() is provided but you may override it to customize the string representation for your implementation.

Template Parameters:

  • Elem – The element type.

  • Impl – The derived implementation class.

Public Types

using elem_type = std::remove_const_t<Elem>#

Queue element type.

Public Functions

std::size_t size() const noexcept#

Number of elements in the queue.

bool empty() const noexcept#

Determines if this queue has no elements.

void iter(std::function<void(Elem const&)> action) const#

Iterates over all elements of this queue from the front.

The given operation will be performed on each element iterated.

Parameters:

action – The operation to be performed on each element.

template<Insertable T = Elem>
std::string to_string(std::string_view prefix = "", std::string_view sep = " ") const#

Creates a string representation of this queue.

Elements are presented in the queue order from left to right.

Template Parameters:

T(dummy) – This operation is available only if the element type Elem of the queue satisfies the dsa::Insertable concept.

Parameters:

  • prefix – Text to prepend to the output string. Defaults to none.

  • sep – Sequence of characters to separate successive elements in the output string. Defaults to a single space character.

Returns:

The string representation created.

Elem &front()#

Accesses the element at the front of this queue.

Throws:

dsa::EmptyQueueError – if the queue is empty.

Returns:

The front element.

Elem const &front() const#

Accesses (read-only) the element at the front of this queue.

Throws:

dsa::EmptyQueueError – if the queue is empty.

Returns:

The front element (immutable).

void enqueue(Elem const &elem)#

Adds an element to the end of this queue.

A deep copy of the element will be copy-constructed and then put into the queue.

Parameters:

elem – The element to be added.

void enqueue(Elem &&elem)#

Adds an element to the end of this queue.

The element will be put into the queue using move semantics.

Parameters:

elem – The element to be added.

void dequeue()#

Removes the element at end of this queue.

Throws:

dsa::EmptyQueueError – if this queue is empty.

template<typename ...Args>
void emplace(Args&&... args)#

Creates a new element in-place after the last element of this queue.

The new element is constructed in-place using all of the arguments passed to this member function.

Note

Strictly speaking, this is a convenient member function, and hence implementations without emplace_<...Args>() is still considered complete with respect to the Queue ADT in theory.

Template Parameters:

Args – Types of the arguments to be passed to the constructor of the element type Elem.

Parameters:

args – Variable number of arguments to be passed to the constructor of the element type Elem.


Supporting Function#

template<typename Elem, template<typename> typename Impl>
void dsa::destroy(IQueue<Elem, Impl> *queue)#

Destroys a queue on the free store via a pointer.

Note

IMPORTANT This is the only proper way to destroy a queue via a base pointer. DO NOT use delete queue; in such context, which will lead to memory leak.

Template Parameters:

  • Elem – The element type.

  • Impl – The derived implementation class.

Parameters:

queue – Pointer to a queue on the free store.

NOTE: Client code that does not adopt static polymorphism will never need to call the dsa::destroy() function.


template<Insertable Elem, template<typename> typename Impl>
std::ostream &dsa::operator<<(std::ostream &os, IQueue<Elem, Impl> const *queue)#

Writes the string representation of this queue to an output stream.

Template Parameters:

  • Elem – Type of each element of the queue.

  • Impl – The derived implementation class of the Queue ADT.

Parameters:

  • os – The output stream to write to.

  • queue – The queue of which the string representation is to output.

Returns:

The outstream to write to.


Concepts#

To make the member function dsa::IQueue::to_string() available, the element type Elem must satisfy the dsa::Insertable constraint, so that the insertion operator << can be operated on the queue elements.

template<typename T>
concept Insertable#
#include <adt.hpp>

Specifies that the type T can be operated with the insertion operator << as the right operand to write to an output stream that serves as the left operand.

tparam T:

The type to test.


Exception#

class EmptyQueueError : public std::exception#

Empty queue error.

An exception that indicates an operation on the queue is invalid when the queue is empty.

Public Functions

inline EmptyQueueError(std::string custom_message = "")#

Constructs a new Empty Queue Error object.

Note

If no custom message is provided, the default error message will be used.

Parameters:

custom_message – A custom message. Defaults to none.

inline const char *what() const noexcept override#

Gets the error message.

Public Static Attributes

static constexpr const char *default_msg = "invalid operation on an empty queue"#

Default error message