patterncppModerate
STL queue implementation
Viewed 0 times
implementationqueuestl
Problem
I've implemented a simple C++ STL like queue. (I've tried to follow @LokiAstari stack implementation code fashion)
I would app
#ifndef QUEUE_H
#define QUEUE_H
#include
#include
using std::cout;
template
class queue {
public:
struct node {
T data;
node *next;
node()
: data(0)
, next(nullptr) {
}
node(T const& data, node* next)
: data(data)
, next(next) {
}
node(T&& data, node* next)
: data(std::move(data))
, next(next) {
}
};
~queue();
bool empty() const;
size_t size() const;
T front() const;
void push(T const& data);
void push(T&& data);
//void emplace (T&&... args);
// void swap (queue& x);
void pop();
private:
size_t elements = 0;
node *head = nullptr;
node *tail = nullptr;
};
template
queue::~queue() {
node *curr = new node();
while(head) {
curr = head;
head = head->next;
delete curr;
}
delete tail;
}
template
bool queue::empty() const {
return elements == 0;
// return head == nullptr;
}
template
size_t queue::size() const {
return elements;
}
template
T queue::front() const {
if(elements == 0)
throw std::runtime_error("Invalid Action");
return head->data;
}
template
void queue::push(T const& data) {
node *newNode = new node(data, nullptr);
if(!elements) head = newNode;
else tail->next = newNode;
tail = newNode;
++elements;
}
template
void queue::push(T&& data) {
node *newNode = new node(std::move(data), nullptr);
if(!elements) head = newNode;
else tail->next = newNode;
tail = newNode;
++elements;
}
template
void queue::pop() {
if(elements == 0)
throw std::runtime_error("Invalid Action");
node *tmp = new node();
if(elements != 0) tmp = head;
head = head->next;
--elements;
delete tmp;
}
#endif // QUEUE_HI would app
Solution
A few points that nearly jump out at me:
-
You've implemented it as a linked list of individually allocated nodes. This nearly guarantees poor locality of reference and for small types wastes quite a bit of space.
-
Your destructor leaks memory:
This allocates a node (not clear why you'd want to allocate a node in the dtor, but there it is), then if
-
Your
For a generic type, this assumption is unwarranted. You typically want to use
-
You've implemented it as a linked list of individually allocated nodes. This nearly guarantees poor locality of reference and for small types wastes quite a bit of space.
-
Your destructor leaks memory:
template
queue::~queue() {
node *curr = new node();
while(head) {
curr = head;This allocates a node (not clear why you'd want to allocate a node in the dtor, but there it is), then if
head != nullptr, it overwrites that pointer with head, thus leaking the node it just allocated (and if that condition isn't met, it just flows off the end without doing any more with curr, also leaking the memory).-
Your
node type takes for granted that a T can be initialized from 0:node()
: data(0)For a generic type, this assumption is unwarranted. You typically want to use
T() to create a value-initialized object, which will be 0 for arithmetic types, a null pointer for a pointer type, an empty string for a string type, and so on.Code Snippets
template <typename T>
queue<T>::~queue() {
node *curr = new node();
while(head) {
curr = head;node()
: data(0)Context
StackExchange Code Review Q#60716, answer score: 16
Revisions (0)
No revisions yet.