Priority Queues - Array based implementation

Question

I am learning about stacks, queues, lists & hash tables from the book Data Structures using C and C++ by Tanenbaum. I am also spending time to take in OOPs essentials, to ensure they sink in well, so that I don't learn by osmosis/need-be basis in the future, and there are no knowledge gaps.

The author of the book suggests, that an array based implementation of the ascending & descending priority queues can be realized using circular, ordered arrays. The author leaves the implementation of the routines insert() and remove(), as an exercise to the reader.

I built a PriorityQueue class. My implementation of insert() and remove() routines is very cryptic. I produce the code verbatim for completeness(and not spamming).

Questions

• Could my implementation from an abstraction/encapsulation standpoint, be optimized?
• Would you in general call it good object oriented design?

Code

---

#ifndef PQueue_H
#define PQueue_H

#include <cmath>
#include <iostream>

const int maxsize = 5;

template <class T>
class PQueue
{
    T items[maxsize];
    int front, rear,n;

public:
    PQueue(T val);
    PQueue(const PQueue<T>& q);
    ~PQueue();
    void insert(T x, int& overflow);
    int search_position(T x);
    T remove(int& underflow);
    T first(int& underflow) const;
    T last(int& underflow) const;
    int size() const;
    bool empty() const;
    void print () const;
    void increment(int& i);
    void decrement(int& i);
};

template <class T>
PQueue<T>::PQueue(T val)
{
    for (int i = 0; i < maxsize; i++)
        items[i] = val;

    front = rear = maxsize - 1;
    n = 0;
}

template <class T>
PQueue<T>::PQueue(const PQueue<T>& q)
{
    for (int i = 0; i < q.n; i++)
    {
        items[i] = q.items[i];
    }
    front = rear = maxsize - 1;
    n = 0;
}

template <class T>
PQueue<T>::~PQueue() {};

template <class T>
int PQueue<T>::search_position(T x)
{
    int low = front, high = rear;
    int i;

    if (empty()) {
        return (rear+1)%maxsize;
    }

    
    for (i = (front+1)%maxsize; i != (rear+1)%maxsize; increment(i))
    {    
        if (items[i] > x)
            break;
    }
    return i;
}

template <class T>
void PQueue<T>::insert(T x, int& overflow)
{
    overflow = 0;
    if ((rear + 1) % maxsize == front)
    {
        overflow = 1;
        return;
    }
    else
    {
        int index = search_position(x);
        std::cout << "\nInserting item " << x << " at position " << index;

        increment(rear);

        //If index matches the updated value of rear,
        //there must be nothing to shift.
        if(index!=rear)
        {
            int i = rear - 1, j = rear;
            i += maxsize; i %= maxsize;
            j += maxsize; j %= maxsize;

            do
            {
                //Shift all elements 1 position to 
                //the right in item[index...rear]
                items[j] = items[i];
                std::cout << "\nShifting item " << items[i] << " from index "
                    << i << " to " << j;
                decrement(i); 
                decrement(j);

            } while (j != index);
        }
        n++;
        items[index] = x;
    }
}

template <class T>
T PQueue<T>::remove(int& underflow)
{
    underflow = 0;
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        increment(front);

        std::cout << "\nRemoving item " << items[front] << " from the front";
        n--;
        return items[front];
    }
}

template <class T>
T PQueue<T>::first(int& underflow) const
{
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        return items[(front + 1) % maxsize];
    }
}

template <class T>
T PQueue<T>::last(int& underflow) const
{
    if (empty())
    {
        underflow = 1;
        return -1;
    }
    else
    {
        return items[rear];
    }
}

template <class T>
int PQueue<T>::size() const
{
    return n;
}

template <class T>
bool PQueue<T>::empty() const
{
    if (front == rear)
        return true;
    else
        return false;
}

template <class T>
void PQueue<T>::print() const
{
    std::cout << "\nQueue items : ";
    for (int i = (front + 1) % maxsize; i != (rear+1)%maxsize; i=(++i)%maxsize)
    {
        std::cout << "items[" << i << "] = " << items[i] << "\t";
    }
}

template <class T>
void PQueue<T>::increment(int& i)
{
    ++i;
    i %= maxsize;
}

template <class T>
void PQueue<T>::decrement(int& i)
{
    --i;
    i += maxsize; i %= maxsize;
}


#endif // !PriorityQueue_H

Answer 1

This code looks a lot like C with classes, rather than modern C++. You make no use of the standard library except for std::cout. You #include <cmath>, but I don't see where you used its functionality.

I'll try to point out a few places where the standard library would simplify the code.

But first:

Bug:

Your copy constructor copies items over from the source queue, but then sets front = rear = maxsize - 1; n = 0;, meaning that the queue will be empty. These values should be copied over from the source queue also.

Rule of 0/3/5:

If you define a custom destructor, copy constructor or copy assignment, you probably should define all three. But you should also be interested in move semantics, meaning that you should also define a move constructor and move assignment (the 5 special functions).

However, in your case you don't really need a custom destructor, since it does nothing. You should not define it at all, and let the compiler generate it. Defining the destructor (even if it is trivial) will prevent the compiler from automatically generating copy and move constructor/assignment.

Also, in this case, copy and move constructor and assignment are trivial (byte for byte copy of the contents of your class, since you don't allocate memory or have any other resource that you manage). Therefore you should not declare these either, and let the compiler generate them for you. This is the "rule of 0".

Use constexpr

When you define maxsize, you can use constexpr.

Flexibility

...however, maxsize should really be a template parameter.

Using the standard library

You store your data in a C-style array. Use std::array instead:

std::array<T, maxsize> items;

This will allow you to replace

for (int i = 0; i < maxsize; i++)
    items[i] = val;

with

std::fill(items.begin(), items.end(), val);

or even

items.fill(val);

and

for (int i = 0; i < q.n; i++) {
    items[i] = q.items[i];
}

with

std::copy(q.begin(), q.end(), items.begin());

Your search_position function could be replaced by std::binary_search (or at least constructed using it).

Error conditions

You use a int& overflow or int& underflow parameter to indicate an error condition. This is OK in principle, especially if you expect these error conditions to occur frequently and the calling code explicitly wants to deal with these situations. But if you don't really expect your caller to remove if empty, and you don't expect the max number of items to be reached in a normal program, then the better approach is to throw an exception. Exceptions are designed for exceptional circumstances. As such, the calling code might not even bother with them. Thus, you remove the requirement of checking a return value for every call of remove.

template <class T>
T PQueue<T>::last(int& underflow) const
{
    if (empty())
    {
        throw std::runtime_error("The queue is empty");
    }
    return items[rear];
}

Answer 2

General design

Encapsulation

Some of the member functions provided by PQueue<T> are helper functions which should not be publicly available (e.g. why should an external caller use PQueue<T>::increment?). Helper functions should usually be private, or in some exceptional cases protected.

Return types/out parameters

Some methods take an int& to return some success/error condition, and either return void or T as their normal return value. And in the latter case, if there is an error state, there isn't any conceptually valid value to return anyways.

The usual convention for this case is either to return the error code (and if needed, use a T& parameter to return the requested value) or to skip returning an error code entirely and just throw an exception.

Abstraction

Conceptually, a priority queue is just an interface that enforces a specific ordering on objects it contains. This doesn't actually specify which actual container is used to then store the data, so a good implementation could just take any fitting container class as a template parameter and work with that.

This means, one could extract all the circular buffer logic into its own class, and then use that as a template parameter for the priority queue.

Doing so simplifies the logic of the priority queue (and makes it more general, e.g. it could as easily work with a std::deque, std::vector or similar). As a bonus, there is now a completely reusable circular buffer class!

Comparison to standard library containers

Some of the public facing names deviate from the normal names used in the standard library:

• first -> front
• last -> back
• insert -> push (*)
• remove -> pop (*)

(*) While insert and remove are used in the standard library, they usually have the semantics of "insert a value at a specific position"/"remove all elements with a value".

Additionally, standard library containers usually provide iterators so their contents can easily be iterated.

Implementation

Buggy copy constructor

• It copies elements with indices 0 to q.n - 1, which should actually be indices q.front to q.rear.
• It then discards the information about the number of elements copied and sets n to 0.

Random debug messages

While these debug messages might be useful during debugging a specific issue, they really shouldn't be part of the final product.

Variable naming

Many variables have very short and sometimes rather cryptic names. This makes the code much harder to read (for humans, at least).

Container problems

• With modern C++, move-only types (like std::unique_ptr) were introduced. The current implementation can't handle those.

• first and last return independent copies of the objects, so any changes done to them won't propagate to the stored objects.

  On one hand, this is good, as changes to the objects might change their relative order compared to other objects contained in the priority queue.

  On the other hand, this gives the user an illusion that he can change those objects inside the priority queue.

  Solution: return a const T&.

• This highlights the next fault shared by first, last and remove: in case there is no object in the priority queue, they just randomly try to return -1 (as there is no valid value).

  This will work if T is an arithmetic type (e.g. int, float), but it will surprise users. If there is no conversion available from -1 to T, the code will fail to compile.

  Solution: See the section about return types above.

• The implementation currently initializes all array elements with a given value (that doesn't actually have any meaning). This might incur a huge runtime cost, as not all types can be cheaply copied. You might want to look into "placement new" as to avoid those unnecessary constructor calls. Also, currently objects don't get destructed when they get removed from the priority queue, which, depending on T, might have unforeseen consequences.

• The capacity of the priority queue is restricted to 5, which is really low. Consider changing this to a template parameter (for a fixed size priority queue) or allowing the storage to grow if needed.

Answer 3

const int maxsize = 5;

A couple of things here. First you should prefer constexpr. But furthermore I am curious why you have a maxsize of 5. You may have a good reason, but if you do it would probably be good to document the decision because it isn't implicitly obvious. Is it completely arbitrary? You could document that if it is the case.

---

int front, rear,n;

Don't declare multiple variable on the same line. You do this many many times throughout the code both with declarations and operations.

---

Consistent whitespace

The spacing between your operators isn't consistent.

Sometimes your have this:

for (int i = 0; i < q.n; i++)

and sometimes this:

for (i = (front+1)%maxsize; i != (rear+1)%maxsize; increment(i))

The spacing improves readability but it is also far more glaring and irksome when it changes like that.

---

prefer prefix over postfix

---

if (front == rear)
    return true;
else
    return false;

any time you return true and false from a conditional like that you are likely overwriting your code.

return front == rear;

should suffice.

---