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


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 ...

• "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? Sep 1, 2022 at 20:21
• @MarlonSmith I've added a litle explanation according to why move would be better.. Sep 2, 2022 at 6:52
• Makes perfect sense, thank you for a great explanation Sep 6, 2022 at 19:37