Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 <iostream>
#include <stdexcept>

using std::cout;

template <typename T>
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 <typename T>
queue<T>::~queue() {
    node *curr = new node();
    while(head) {
        curr = head;
        head = head->next;
        delete curr;
    }
    delete tail;
}

template <typename T>
bool queue<T>::empty() const {
    return elements == 0;
//    return head == nullptr;
}

template <typename T>
size_t queue<T>::size() const {
    return elements;
}

template <typename T>
T queue<T>::front() const {
    if(elements == 0)
        throw std::runtime_error("Invalid Action");
    return head->data;
}

template <typename T>
void  queue<T>::push(T const& data) {
    node *newNode = new node(data, nullptr);
    if(!elements) head = newNode;
    else tail->next = newNode;
    tail = newNode;
    ++elements;
}
template <typename T>
void  queue<T>::push(T&& data) {
    node *newNode = new node(std::move(data), nullptr);
    if(!elements) head = newNode;
    else tail->next = newNode;
    tail = newNode;
    ++elements;
}
template <typename T>
void  queue<T>::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 appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.

Also can you give me some insight on how I can implement the C++11 features like emplace(T&& data) and swap(queue& x) efficiently?


Edit (After applying most of the suggestions)

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <stdexcept>

template <typename T>
class queue {
public:
    ~queue();
    bool empty() const;
    size_t size() const;
    T const& front() const;
    T& front();
    void push(T const& data);
    void push(T&& data);
    //void emplace (T&&... args);
    // void swap (queue& x);
    void pop();

private:
    size_t elements = 0;
    struct node {
        T data;
        node *next;

        node(T const& data, node* next)
            : data(data)
            , next(next) {
        }

        node(T&& data, node* next)
            : data(std::move(data))
            , next(next) {
        }
    };
    node *head = nullptr;
    node *tail = nullptr;
};

template <typename T>
queue<T>::~queue() {
    node *curr;
    while(head) {
        curr = head;
        head = head->next;
        delete curr;
    }
}

template <typename T>
bool queue<T>::empty() const {
    return elements == 0;
//    return head == nullptr;
}

template <typename T>
size_t queue<T>::size() const {
    return elements;
}

template <typename T>
T const& queue<T>::front() const {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");
    return head->data;
}

template <typename T>
T& queue<T>::front() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");
    return head->data;
}

template <typename T>
void  queue<T>::push(T const& data) {
    node *newNode = new node(data, nullptr);
    if(head == nullptr) head = newNode;
    else tail->next = newNode;
    tail = newNode;
    ++elements;
}
template <typename T>
void  queue<T>::push(T&& data) {
    node *newNode = new node(std::move(data), nullptr);
    if(head == nullptr) head = newNode;
    else tail->next = newNode;
    tail = newNode;
    ++elements;
}

template <typename T>
void  queue<T>::pop() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");

    node* remove = head;
    head = head->next;
    delete remove;

    --elements;
}

#endif // QUEUE_H
share|improve this question

3 Answers 3

up vote 13 down vote accepted

Don't do this in a header file.

using std::cout;

You are now messing with everybody else code that uses your header file. That will not please them and can lead to issues down the road for them for wich your name will be cursed for a thousand years.

No need to make the node public. The poeple using your class do not need to know the internal workings of the class.

public:
    struct node {
        T data;

Don't use zero here.

        node()
            : data(0)
            , next(nullptr)

If you use just braces your force POD types to be zero. While user defined types get default constructed.

        // Try this.
        node()
            : data()           // Zero init POD. Or default construct.
            , next(nullptr)

But to be honest you don't need this constructor at all. I would just remove it.

Don't dynamically allocate a node in the destructor.

queue<T>::~queue() {
    node *curr = new node();    // You just leak this.
                                // Just remove everything from the `new` forward.

If the tail is part of the list then you are going to call delete twice on some object.

    delete tail;     

Remove that line. It is not needed.

Note: Here you are returning a copy of the value in the your stack.

template <typename T>
T queue<T>::front() const {

This may be what you want but usually I would expect to see you return a reference to the object in the stack. That way a user can potentially modify the value. If they want to make a copy they can also do that by assigning it to an object (but it is not required).

As a result you also usually want to versions of this function. A normal one and a const one.

template <typename T>
T& queue<T>::front() {


template <typename T>
T const& queue<T>::front() const {

In:

void  queue<T>::pop() {

No need to crate a tmp node (you just leak it).

    node *tmp = new node();

You have already tested for (elements == 0) above and thrown if so. So this if statement is always true.

    if(elements != 0) tmp = head;
share|improve this answer
    
+1 for your nice answer always! :) –  Kaidul Islam Aug 21 at 17:52

A few points that nearly jump out at me:

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

  2. Your destructor leaks memory:

    template <typename T>
    queue<T>::~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).

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

share|improve this answer
    
+1 for pointing some major mistakes :) –  Kaidul Islam Aug 21 at 17:53

First off

Never, ever use a using directive in a header as that can cause problems for your client code. As this is a code review I'm not going to comment on how to implement the C++11 features you mentioned. You can get help with this over at StackOverflow.

Public interface

Why is node a public type in queue? The user should never have to deal with the implementation details of queue. So I would recommend hiding it as a private or protected member class.

Your front() method returns a copy which is correct if called on a const declared queue. But on a non-const queue you're better of returning a reference to T.

Correctness issues

You should be aware of the fact that new can throw a std::bad_alloc. A destructor in C++ is allowed to throw an exception but it is generally discouraged. If an exception is thrown during handling of another exception the program will call std::terminate(), so if your destructor throws it can throw during stack unwinding and your program will terminates. Also if an exception is thrown from the destructor during a delete operation then the memory of the class may never be freed depending on the implementation of the delete operator. In short you are better off not throwing from the destructor. Not only that, your destructor actually leaks the allocated node which is never used.

Your pop() method also leaks memory through tmp if elements!=0 which it always is because you throw an exception if elements==0.

A correct pop() method should be written like this:

template <typename T>
void  queue<T>::pop() {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");

    node* remove = head;
    head = head->next;
    delete remove;

    --elements;
}

You are also unnecessarily allocating new nodes at many places.

Your node() constructs a T(0) in all cases which is not necessarily possible for all types a user may use as template argument. As Jerry also states this is incorrect. However Jerry's suggested solution to use T() instead requires that T be default-constructible without side-effects. This is not always true and you're better off using std::aligned_storage<sizeof(T)> like this:

template<typename T>
struct node {
    std::aligned_storage_t<sizeof(T)> data;
    bool has_data{ false };
    node *next;

    node()
        : next(nullptr) 
    {}

    node(T const& value, node* next)
        : next(next)
    {
        new (&data) T(value);
        has_data = true; // just incase the constructor throws.
    }

    node(T&& value, node* next)
        : next(next)
    {
        new (&data) T(std::move(value));
        has_data = true;
    }

    T& getdata(){
        if (!has_data)
            throw std::runtime_error("error no data");
        return *reinterpret_cast<T*>(&data);
    }

    ~node(){
        if (has_data)
            getdata().~T();
    }
};

This means that you can create nodes without actually running the constructor or initializing the node data.

Style suggestion

Prefer to test on what you need and not an invariant of what you need.

template <typename T>
T queue<T>::front() const {
    if(elements == 0)
        throw std::runtime_error("Invalid Action");
    return head->data;
}

Is better written like this:

template <typename T>
T queue<T>::front() const {
    if(head == nullptr)
        throw std::runtime_error("Invalid Action");
    return head->data;
}

Also you never call the node constructor with a non-null *next why not change the constructor to simplify usage?

Use sentinels

A sentinel node is an easy way to get around special casing the null list. Read more here: Sentinel Node.

Performance

The poor locality of reference due to linked lists can be mostly mitigated with a memory pool / fixed-size allocator. As the queue is popped at the front, any form of naive vector use is out of the question.

If the maximum number of elements is known at compile time, a Circular Buffer will be your best choice. With some work you can construct a dynamically expanding circular buffer and resizing it would be no more costly than resizing a vector which would leave you with amortized \$\mathcal{O}(n)\$ time to fill a queue of size \$n\$. I believe this is the best approach for performance.

share|improve this answer
    
+1 for mentioning good points! :) –  Kaidul Islam Aug 21 at 17:52
2  
Re: "A destructor in C++ is not allowed to throw an exception. If a destructor throws then you have undefined behavior." No. Many coding guidelines that say not to throw exceptions from destructors, but that's individual choice, not gospel. Throwing an exception from a destructor is legal and its behavior is well defined. Normally it's no different from any other throw. However, if the destructor was called during stack unwinding because of another exception the program calls std::terminate(). That's rather drastic, and it's the reason that many people advise not to throw from destructors. –  Pete Becker Aug 21 at 23:57
    
Not sure I like the concept of using std::aligned_storage<sizeof(T)> that just makes everything a little bit more complicated. I would just remove that default constructor and the problem goes away. –  Loki Astari Aug 22 at 7:26
    
@PeteBecker I over spoke you are allowed to throw but it can lead to all manners of problems from leaking memory to downright calls to terminate as you said. I'll reword it. –  Emily L. Aug 22 at 10:22
1  
When you delete an object the destructor is executed before the delete operator is ever ran. Thus it is impossible to catch the exception or handle it in the delete operator, rather it is thrown out to the enclosing scope. Hence you will leak memory unless you place a try-catch around every delete operator. See here: ideone.com/qzyzEq on that particular compiler the code just terminates, but on gcc 4.7.2 it prints: "News: 1 Deletes: 0" thus memory is leaked. –  Emily L. Aug 22 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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