HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

STL queue implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationqueuestl

Problem

I've implemented a simple C++ STL like queue. (I've tried to follow @LokiAstari stack implementation code fashion)

#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_H


I 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:

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.