3
\$\begingroup\$

I'm reading through Algorithms Fourth Edition by Sedgewick and doing some of the practice exercises in C++11 instead of Java. Exercise 1.3.29 is to write a Queue that uses a circular linked list, keeping only one Node instance variable (last).

All comments are welcome, but especially ones focusing on advanced C++ techniques as well as the algorithm itself.

#ifndef QUEUE_HH
#define QUEUE_HH

#include <cstddef>
#include <stdexcept>

template<class T>
class Queue {
public:

    Queue()
    : _last(nullptr)
    {}

    void enqueue(T value)
    {
        // Create a new node, not yet linked to anything
        Node* node = new Node{value, nullptr};

        if(is_empty()) {
            // Only node in the list, link it to itself
            node->next = node;
        } else {
            // Link the new node to the start of the list
            node->next = _last->next;

            // Add the new node to the end of the list
            _last->next = node;
        }

        _last = node;
    }

    T dequeue()
    {
        if(is_empty()) {
            throw std::out_of_range("Empty queue");
        }

        // Get the first node in the list
        Node* node = _last->next;

        // Unlink the node by pointing last to the next node
        _last->next = node->next;

        // If we're removing the only node in the list, set last node to nullptr
        if(node == _last) {
            _last = nullptr;
        }

        // Retrieve the value before deleting the node
        int value = node->value;

        delete node;
        return value;
    }

    size_t size() const
    {
        if(is_empty()) {
            return 0;
        }

        // Start at last node, count iterations until last node is reached again
        size_t count = 0;
        Node* current = _last;
        do {
            count++;
            current = current->next;
        } while(current != _last);

        return count;
    }

    bool is_empty() const
    {
        return _last == nullptr;
    }

private:

    struct Node
    {
        T value;
        Node* next;
    };

    Node* _last;
};

#endif // QUEUE_HH
\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

There is a bug in the dequeue function:

// Retrieve the value before deleting the node
int value = node->value;

The Queue class is a template, therefore the value of the node is of type T. And instead of assigning it, moving the value (see std::move) is a better choice:

T value{std::move(node->value)};

Why move?

Imagine T is a string or an vector with millions of entries. A copy is expensive, move will only transfer the associated resources (e.g. simple pointer exchange). Don't forget, node will be destroyed, therefore the value in node too. That's why the assignment to the return value. Again, why create and destroy if we just simply could transfer (move) it.

As long as T is a primitive type (small type), there is no difference between copy and move assignment, but the more there is to copy ...

\$\endgroup\$
3
  • 1
    \$\begingroup\$ "therefore the value of the node is of type T" Ah yep, you're right. I wrote the class for ints initially, and broke my rule of writing a new unit test before changing it to a template. "instead of assigning it, moving the value" Would you mind talking a bit more about why this is better in this case? \$\endgroup\$ Sep 1, 2022 at 20:21
  • \$\begingroup\$ @MarlonSmith I've added a litle explanation according to why move would be better.. \$\endgroup\$ Sep 2, 2022 at 6:52
  • \$\begingroup\$ Makes perfect sense, thank you for a great explanation \$\endgroup\$ Sep 6, 2022 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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