1
\$\begingroup\$

I wrote a Priority Queue that is stored using a doubly linked list. The queue can return the head and tail of the list, and contains a print function that is only used for testing purposes.

I'd like a critique of the general style, correctness, efficiency, exception handling, algorithm and any other areas I may have missed.I've also added the tests I used for the code as well.

#pragma once
#include <memory>
#include <iostream>

template <typename T>
class PriorityQueue
{
    public:
        PriorityQueue();
        PriorityQueue(const PriorityQueue& other);
        PriorityQueue(PriorityQueue&& other)                            noexcept;
        ~PriorityQueue();

        PriorityQueue<T>& operator= (const PriorityQueue<T>& other);
        PriorityQueue<T>& operator= (PriorityQueue<T>&& other)          noexcept;

        void swap(PriorityQueue<T>& other)                              noexcept;

        friend void swapPriorityQueue(PriorityQueue<T>& A, PriorityQueue<T>& B)
        {
            A.swap(B);
        }

        //Highest priority item is dequeued first. If the same priority is used, the earlier queued item is dequeued first
        void dequeue();
        void enqueue(int priority, T item);

        T& first()                                                      const;
        T& last()                                                       const;

        void print()                                                    const;

    private:

        struct Node
        {
            std::shared_ptr<Node> next;
            std::shared_ptr<Node> prev;
            T data;
            int priority;

            Node(T&& data, int priority, std::shared_ptr<Node>&& next, std::shared_ptr<Node>&& prev)
                :data(std::move(data))
                ,priority(priority)
                ,next(std::move(next))
                ,prev(std::move(prev))
            {}
        };

        std::shared_ptr<Node> head;
        std::shared_ptr<Node> tail;
};

template <typename T>
PriorityQueue<T>::PriorityQueue()
    :head(nullptr)
    ,tail(nullptr)
{}

template <typename T>
PriorityQueue<T>::PriorityQueue(const PriorityQueue& other)
{
    for (std::shared_ptr<Node> curr = other.tail; curr != nullptr; curr = curr->next )
        enqueue(curr->priority, curr->data);    

}

template <typename T>
PriorityQueue<T>::PriorityQueue(PriorityQueue&& other)                                  noexcept
    :PriorityQueue()
{
    swapPriorityQueue(*this, other);
}

template <typename T>
PriorityQueue<T>& PriorityQueue<T>::operator= (const PriorityQueue<T>& other)
{
    PriorityQueue tmp(other);
    swapPriorityQueue(*this, tmp);
    return *this;
}

template <typename T>
PriorityQueue<T>::~PriorityQueue()
{
    while (tail != nullptr)
        dequeue();
}

template <typename T>
PriorityQueue<T>& PriorityQueue<T>::operator= (PriorityQueue<T>&& other)                    noexcept
{
    swapPriorityQueue(*this, other);
    return *this;
}

template <typename T>
void PriorityQueue<T>::swap(PriorityQueue& other)                                           noexcept        
{
    using std::swap;
    swap(head, other.head);
    swap(tail, other.tail);
}

template <typename T>
void PriorityQueue<T>::dequeue()
{
    if (tail == nullptr)
        throw std::runtime_error("Nothing in queue");

    tail = std::move(tail->next);

    if(tail != nullptr)
        tail->prev = nullptr;
}

template <typename T>
void PriorityQueue<T>::enqueue(int priority, T item)
{
    std::shared_ptr<Node> newNode = std::make_shared<Node>(std::move(item), priority, nullptr, nullptr);

    if (head == nullptr)
    {
        head = tail = newNode;
        return;
    }
    std::shared_ptr<Node> curr = nullptr;
    for (curr = head; curr != nullptr && priority < curr->priority; curr = curr->prev);

    if (curr == nullptr)        //We are at the end of queue, the priority I want to insert must be the highest priority in the queue, we didn't find any lower priority
    {
        newNode->next = tail;
        tail->prev = newNode;
        newNode->prev = nullptr;
        tail = newNode;
    }
    else                        //curr now points to the Node that is just barely in front of newNode. curr is either higher priority than newNode, or same priority but inserted earlier
    {
        newNode->prev = curr;
        newNode->next = curr->next;

        if(newNode->next != nullptr)
            newNode->next->prev = newNode;

        newNode->prev->next = newNode;

        if (head == tail || priority >= head->priority)
            head = newNode;
    }
}

template <typename T>
T& PriorityQueue<T>::first() const
{
    if (tail == nullptr)
        throw std::runtime_error("Nothing in queue");

    return tail->data;
}

template <typename T>
T& PriorityQueue<T>::last() const
{
    if (head == nullptr)
        throw std::runtime_error("Nothing in queue");

    return head->data;
}

template <typename T>
void PriorityQueue<T>::print() const
{
    if (head == nullptr)
        throw std::runtime_error("Nothing in queue");

    std::cout << "\n\nFrom lowest priority to highest \n\n";

    for (std::shared_ptr<Node> curr = head; curr != nullptr; curr = curr->prev)
        std::cout << curr->data << "[" << curr->priority << "] --> ";               //print is just for testing purposes. This line will not compile if T is not a primitive data-type


}

Here is my test code:

#pragma once

#include "stdafx.h"
#include "PriorityQueue.h"
#include <iostream>

void testPriorityQueue();

int main()
{
    testPriorityQueue();

    system("pause");
    return 0;
}

void testPriorityQueue()
{

    PriorityQueue<char> test1;
    test1.enqueue(3, 'A');
    test1.enqueue(1, 'B');
    test1.enqueue(1, 'C');
    test1.enqueue(2, 'D');
    test1.enqueue(4, 'E');
    test1.enqueue(4, 'F');
    test1.print();

    test1.dequeue();
    test1.print();
    test1.dequeue();
    test1.dequeue();
    test1.dequeue();
    test1.print();

    PriorityQueue<char> test2;
    test2 = test1;
    test2.print();

    PriorityQueue<int> dummy;
    dummy.enqueue(1, 1);

    PriorityQueue<int> test3(dummy);
    test3.print();

    std::cout << "\n\n";
}

And here is the output, which is correct for the inputs

Output

\$\endgroup\$
  • \$\begingroup\$ #pragma once is used to make sure header files are included only once, you don't need it in a file containing main(), only header files. \$\endgroup\$ – pacmaninbw Aug 1 '16 at 13:01
  • \$\begingroup\$ What's wrong with std::priority_queue? \$\endgroup\$ – Reuben Thomas Aug 1 '16 at 21:14
3
\$\begingroup\$

Use of linked list

I wrote a Priority Queue that is stored using a doubly linked list.

I'm tempted to start and stop with this single point. A priority queue stored as a linked list is just a bad idea. There's virtually nothing you can do from that point onward to even have a hope of repairing that.

If you're set on putting a linked list to use, I'd at least break it up into one linked list per priority level, with (for example) the heads/tails of the linked lists stored in an array/vector. Then you can index to the correct linked list and add to the end (or remove from the beginning) quickly.

With a single linked list, you're stuck traversing through all the items at higher (or lower, depending on which direction you go) to find the location for an insertion/removal. This is bad because:

  1. it's linear on the number of elements (rather than constant time, as it can be), and
  2. linked lists have lousy locality of reference, so they make poor use of the cache, and
  3. a doubly linked list adds a lot of storage overhead in the form of the forward and reverse pointers--and using a single linked lists makes this still worse, because you're also storing the priority along with the actual data.
  4. In your case, you're compounding the problem by creating the links between the items in the list with shared_ptrs instead of raw pointers. Yes, there are some good things about shared_ptrs--nothing wrong with the idea of using them in general. In this particular case, however, they add still more overhead, as you end up with an extra allocation and dereference to deal with the reference count.

Let's consider those last twos point in a little more detail by considering your example code. In your example, the actual data to be stored in a node is one char. Along with that, however, you're storing two shared pointers and one int.

If we simplified things a bit and used raw pointers, on a typical 32-bit implementation we'd end up with 12 bytes of overhead1 per char of actual data being stored (but on a 64-bit implementation, 20 or 24 bytes of overhead2 per char). With shared_ptr we end up with still more overhead, so we're probably going to be up to at least 32 bytes of overhead for every byte of actual data being stored (and, depending on the minimum node size your allocator deals with, that could easily double).

At least to me, that just seems at least a bit excessive.

Anyway, I hope I haven't bored you too much, but I think that basic point really deserved some emphasis.

Naming

It's not clear to me why you chose the name swapPriorityQueue. Normally this would just be named swap. Using that name allows anything else that wants to swap items to make use of it. This is especially important for generic code.

Similarly, what you've named first and last are normally named front and back. Oh, it's also strange (to the point of being actively misleading) that first returns the tail of the list and last returns the head of the list. I think most people would expect rather the opposite of that.

friendship

Since your swapPriorityQueue only uses a public function (swap) it doesn't really need to be a friend. In this case, all the friend is accomplishing is making it a non-member function.

Formatting

You have a number of lines like:

T& first()                                                      const;
T& last()                                                       const;

void print()                                                    const;

The few studies I've seen that looked at this sort of formatting found it to be a net negative in terms of maintenance. Maintaining this spacing throughout the code takes quite a bit of work, and there's little gain in readability to pay for that work (and it shows here--you haven't used that formatting consistently, and in a few places, a noexcept isn't visible at all, at least as I'm seeing the code online).


  1. 2 pointers of 4 bytes apiece + 1 int of 4 bytes = 12 bytes of overhead.
  2. 2 pointers of 8 bytes apiece + 1 int of 4 or 8 bytes = 20 or 24 bytes of overhead. To be more specific, MS VC++ will give 20 bytes, gcc on Linux will normally give 24.
\$\endgroup\$
  • \$\begingroup\$ can you explain a bit more how you got the number 12 bytes of overhead on a 32 bit machine and 20-24 byte of overhead on a 64 bit machine? Also do you think it is even necessary to write the friend function swapPriorityQueue? Can I just use the void swap(PriorityQueue& other directly? \$\endgroup\$ – Mantracker Aug 1 '16 at 18:08
  • \$\begingroup\$ @Mantracker: You could use the member directly, but it's fairly common (and probably a good idea) to provide it as a free (non-member) function as well. \$\endgroup\$ – Jerry Coffin Aug 1 '16 at 18:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.