5
\$\begingroup\$

When reviewing my code, please consider these questions too:

  1. Any way to avoid using new/delete? Or are data structures like that normally and can't really use smart pointers? I was thinking of using shared pointers or unique pointers but they seem odd to use in this case.

  2. Recursion in a constructor? Good or bad?

  3. Copy constructor should be deleted for Node? Because you copy the pointer to next otherwise. Copy of the nodes should be done by Queue instead?

queue.h

#ifndef H_UTILS_QUEUE_H
#define H_UTILS_QUEUE_H

#include <stdexcept>


namespace Utils {

template<class T>
class Queue {

private:

    //  Node
    class Node {
    public:
        explicit Node(const T& data, Node* next);
        explicit Node(T&& data, Node* next);
        Node(const Node& other);
        Node(Node&& other) noexcept;

        Node& operator=(Node other) noexcept;

    private:
        void swap(Node& other) noexcept;

    public:
        T mData;
        Node* mNext;

    };  //  Node

public:
    Queue();
    Queue(const Queue<T>& other);
    Queue(Queue<T>&& other) noexcept;

    Queue<T>& operator=(Queue<T> other) noexcept;

    T& front();
    void pop_front() noexcept;
    void push_front(const T& data);
    void push_back(const T& data);
    void push_back(T&& data);

private:
    void swap(Queue<T>& other) noexcept;
    Node* deepCopy(Node* node);

private:
    Node* mHead;

};  //  Queue


//  Node
template<class T>
Queue<T>::Node::Node(const T& data, typename Queue<T>::Node* next)
    : mData(data)
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(T&& data, typename Queue<T>::Node* next)
    : mData(std::move(data))
    , mNext(next)
{

}

template<class T>
Queue<T>::Node::Node(typename const Queue<T>::Node& other)
    : mData()
    , mNext(nullptr)
{
    mData = other.mData;
    mNext = other.mNext;
}

template<class T>
Queue<T>::Node::Node(typename Queue<T>::Node&& other) noexcept
    : mData()
    , mNext(nullptr)
{
    swap(other);
}

template<class T>
typename Queue<T>::Node& Queue<T>::Node::operator=(typename Queue<T>::Node other) noexcept
{
    if (this != &other) {
        swap(node);
    }

    return *this
}

template<class T>
void Queue<T>::Node::swap(typename Queue<T>::Node& other) noexcept
{
    using std::swap;
    swap(mData, other.mData);
    swap(mNext, other.mNext);
}


//  Queue
template<class T>
Queue<T>::Queue()
    : mHead(nullptr)
{

}

template<class T>
Queue<T>::Queue(const Queue<T>& other)
    : mHead(nullptr)
{
    if (other.mHead) {
        mHead = deepCopy(other.mHead);
    }
}

template<class T>
Queue<T>::Queue(Queue<T>&& other) noexcept
    : mHead(nullptr)
{
    swap(other);
}

template<class T>
Queue<T>& Queue<T>::operator=(Queue<T> other) noexcept
{
    if (this != &other) {
        swap(other);
    }

    return *this;
}

template<class T>
void Queue<T>::swap(Queue<T>& other) noexcept
{
    using std::swap;
    swap(mHead, other.mHead);
}

template<class T>
typename Queue<T>::Node* Queue<T>::deepCopy(typename Queue<T>::Node* node)
{
    if (node->mNext == nullptr) {
        //  at tail

        //  if an exception is thrown here allow it to progate out of this function
        //  to be handled by the calling code
        //  no memory will be leaked
        return new Node(node->mData, nullptr);
    }

    Node* next = deepCopy(node->mNext);
    Node* current = nullptr;

    try {
        current = new Node(node->mData, next);
    } catch (...) {
        //  something went wrong
        //  recursively deallocate any nodes that have been allocated up to this point
        Node* i = next;
        while (i) {
            Node* copy = i->mNext;
            delete i;
            i = copy;
        }
    }

    return current;
}

template<class T>
T& Queue<T>::front()
{
    if (mHead) {
        return mHead->mData;
    } else {
        throw std::logic_error("trying to get front of empty queue");
    }
}

template<class T>
void Queue<T>::pop_front() noexcept
{
    if (mHead) {
        Node* newHead = mHead->mNext;
        Node* oldHead = mHead;
        mHead = newHead;
        delete oldHead;
    } 
}

template<class T>
void Queue<T>::push_front(const T& data)
{   
    try {
        Node* prevHead = mHead;
        Node* newHead = new Node(data, prevHead);
        //  only once we successfully get to this stage do we set the head pointer
        mHead = newHead;
    } catch (...) {
        //  something went wrong
        //  queue still in same state it was before call to push_back

        //  let the caller handle the exception
        throw;
    }
}

template<class T>
void Queue<T>::push_back(const T& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    } else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(data, nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}

template<class T>
void Queue<T>::push_back(T&& data)
{
    //  find the tail
    Node* tail = mHead;
    while (tail) {
        if (tail->mNext == nullptr) break;

        tail = tail->mNext;
    }

    if (tail) {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        tail->mNext = newHead;
    }
    else {
        Node* newHead = nullptr;

        try {
            newHead = new Node(std::move(data), nullptr);
        } catch (...) {
            //  no changes made
            //  no leaks
            //  propogate to caller
            throw;
        }

        mHead = newHead;
    }

}



}  //  Utils


#endif  //  UTILS_QUEUE

main.cpp

#include <iostream>
#include "queue.h"

using Utils::Queue;

int main()
{
    {
        Queue<char> charQueue;

        charQueue.push_back('a');
        char b = 'b';
        charQueue.push_back(b);
        charQueue.push_back('c');
        charQueue.push_back('d');
        charQueue.push_back('e');
        charQueue.push_back('f');
        charQueue.push_back('g');
        charQueue.push_back('h');
        charQueue.push_back('i');
        charQueue.push_back('j');
        charQueue.push_back('k');
        charQueue.push_back('l');
        charQueue.push_back('m');

        for (std::size_t i = 0; i < 13; ++i) {
            std::cout << charQueue.front() << "\n";
            charQueue.pop_front();
        }
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b(std::move(a));
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = a;
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        Queue<char> b;

        b = std::move(a);
    }

    {
        Queue<char> a;
        a.push_back('a');
        a.push_back('b');
        a.push_back('c');

        try {
            for (std::size_t i = 0; i < 10; ++i) {
                a.front();
                a.pop_front();
            }       
        } catch (std::exception& e) {
            std::cout << "Caught Exception " << e.what() << "\n";
        }
    }


    std::cin.get();

}
\$\endgroup\$

closed as off-topic by Sᴀᴍ Onᴇᴌᴀ, Stephen Rauch, Mast, t3chb0t, Marc-Andre Mar 25 '18 at 16:38

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Code not implemented or not working as intended: Code Review is a community where programmers peer-review your working code to address issues such as security, maintainability, performance, and scalability. We require that the code be working correctly, to the best of the author's knowledge, before proceeding with a review." – Sᴀᴍ Onᴇᴌᴀ, Stephen Rauch, Mast, t3chb0t, Marc-Andre
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ Please make sure this compiles, there are a few issues. \$\endgroup\$ – Harald Scheirich Mar 23 '18 at 21:21
  • \$\begingroup\$ @HaraldScheirich sorry will do. I used visual studio but i now understand people use gcc and clang here. \$\endgroup\$ – SRG Mar 23 '18 at 22:56
  • 1
    \$\begingroup\$ There was a missing semicolon and an undefined variable, those are not visual studio issues. \$\endgroup\$ – Harald Scheirich Mar 24 '18 at 0:19
  • \$\begingroup\$ @HaraldScheirich can you show me? \$\endgroup\$ – SRG Mar 24 '18 at 0:42
  • \$\begingroup\$ what does your compiler say when you are trying to compile this ? The assignment operator is missing the semicolon in the return statement, and node is not defined that probably should be other \$\endgroup\$ – Harald Scheirich Mar 24 '18 at 14:54
4
\$\begingroup\$

Regarding your explicit questions:

  1. Well, you can avoid explicit raw use of memory-allocation by using smart-pointers, or if you bound the size of the queue you can alloate all nodes as part of the queue itself.
    Your choice, but for the first it is fairly common to eschew such comforts in the implementation of basic abstractions to reduce dependencies and allow and for maximal control.
    For the second, that's basically a different data-structure.

  2. All else being equal, try to keep the stack small. Recursion can potentially overflow the stack in the absence of tail-call-optimization, so that must be taken into account. If that's not a danger, use the most elegant option which is reasonably efficient (generic library-code should take extra care with efficiency).

  3. Generally, I would avoid trying to go all-out OOifying internal helper classes. Remember that doing so restricts using code from doing useful things, makes them unnatural and convoluted, and generally leads to bloat.
    The optimal definition for a node-class is imho:

    struct node { node* next; T data; };
    

    Use aggregate-initialization for creating nodes.

    That way there is no bloated artifical interface between it and the owning parent-class getting in the way of conciseness and efficiency, which provides all the consumer-facing options for manipulation anyway.

    The only thing to consider is whether you want to use a std::unique_ptr<node> for next instead.

And now, reviewing everything not yet mentioned:

  1. Generally, you make reasonably sure that a header is self-contained by including it first in the corresponding implementation-file.
    That's the one weak point of having a header-only library, there's no source-file which naturally does that check, so it must be done manually.

  2. If you stream a single-character-string, consider streaming a character instead. It might be slightly more efficient.

  3. Node should either be an aggregate without any customization, or not support copy-/move- construction, assignment and certainly .swap().
    Anyway you look at it, declaring the operations you did noexcept unconditionally is an error, as not all T's support that guarantee.

  4. If you insist on having member-function .swap(other), at least make it public. Though it would be far more useful to simply define friend void swap(a, b) instead, as that will be picked up by generic code.

  5. You really only need to do a deep-copy in the copy-ctor, which does only that. As such, extracting that into its own function does not buy you anything. Actually, it means you have to duplicate the cleanup-code already in the dtor.

  6. You should define template<class... X> void emplace_back(X&&... x) and define the two push-variants in terms of that, equivalently for emplace_front(). That allows you to remove much code-duplication and gets you a more efficient and versatile interface.

  7. Don't guard against self-assignment. Aside from the fact that it is trivial to prove that this and &other are distinct as other was passed by value, a copy-and-swap already works correctly and pessimizing the common case is a bad idea.

  8. Don't catch exceptions just to rethrow them. Doing so might look like the compiler should be able to optimize it out, but that's not really always the case.

  9. Try to avoid special cases. Double-indirection is not rocket science.
    As an example, inserting a new node at the end:

    auto p = &head;
    while (*p)
        p = &p->next;
    *p = new Node{...};
    
\$\endgroup\$
  • \$\begingroup\$ 4) I think this is todo with visual studio. I will cross compile with gcc and clang. 7) is there a general consensus on this? I have heard and seen conflicting ideas/code. Some reading material please \$\endgroup\$ – SRG Mar 23 '18 at 23:20
  • \$\begingroup\$ Well, you swap by either using std::iter_swap(&a, &b); or using std::swap; swap(a, b);. Both cases use ADL to find specializations. Member-swap is only relevant if you know the involved types, but why should you memorize that [some incomplete and incorrect list of types] support it, if the other way is always right? \$\endgroup\$ – Deduplicator Mar 23 '18 at 23:23
3
\$\begingroup\$

First off all, let's answer your questions:

  1. Well, you could make this work using std::unique_ptr. However, since you are implementing a quite low-level memory structure, I'm not sure I would suggest it here. In general, smart pointer usage is preferable to raw pointers; however, in a case like this where you have to manipulate the pointers themselves a lot (as opposed to the data they are pointing to), smart pointers tend to be somewhat clumsy and ill fitted. However, you should definitely make sure that you are doing memory management correctly (using static analysis as well as runtime analyzers such as valgrind, asan, msan etc.).
  2. There's nothing inherently bad about using recursion in a constructor.
  3. There are two different approaches to the copy problem. One is to treat Node as a dumb, struct-like class that does not much more than combining a piece of data with a pointer to the next node. In that case, it is fine to make copying nodes correctly the responsibility of Queue.

    The other approach is treating Nodes more like "smart" objects which have some ingrained behavior, in which case copying should be defined through the Node class.

    I personally prefer the latter, because it plays well with the C++ approach to OOP, and lifts some responsibility from Queue. However, I would not say that the other approach is wrong, I just don't like it as much because it makes the overall burden on Queue heavier.

You queue is nearly useless

Harsh words. Why do I say something like this?

The answer is: You only offer two methods to access elements. While this is conforming to the most basic definition of a queue, it's not very useful in everyday programming.

At the very least, you should add an iterator interface, which would also allow your queue to interact with most standard algorithms and increase usability by a huge margin.

Also, you should add some type definitions to conform to the standard's container library requirements.

Some other things

  1. Fix your includes. Now. You need #include <utility> for both std::move and std::swap, otherwise your code might not compile.
  2. Adhere to the rule of five. Queue defines a copy and a move constructor as well as a copy assignment operator, so it should define a move assignment operator and a destructor as well. The same is true for Node, if you want to follow my suggestion for question 3. If not, you should remove the special member functions altogether.
  3. Related to point 2: Since you are not defining a destructor, you are leaking memory everywhere. Fix this immediately.
  4. Copy assignment operators should take their argument by const reference. If you take the other object by value, you incur an unnecessary copy, which is quite costly for a container class.
  5. Instead of manually writing out the default constructor for Queue, you should add a member initializer to mHead (i.e. Node* mHead = nullptr;) and just = default the default constructor.
  6. When writing single chars to std::cout, use 'c' instead of "c" (in particular, this applies to your use of "\n"). The latter is likely to cause performance degradation.
\$\endgroup\$
  • \$\begingroup\$ 1) using visual studio. I will compile in gcc and clang and fix. 2 & 4) I am using one assignment operator for move & copy. It was suggested in another code review codereview.stackexchange.com/questions/189601/… 3) I forgot the destructor!!! will add it asap. \$\endgroup\$ – SRG Mar 23 '18 at 23:06
  • \$\begingroup\$ @SRG I don't like the one-does-all assignment operator very much. The reason is that, in the copy case, you are always making a temporary that is immediately destructed again. If your class is large, this is slower than just doing the cleanup manually and assigning. However, your class contains nothing more than a pointer, so the combined approach is fine. \$\endgroup\$ – Ben Steffan Mar 24 '18 at 14:10
  • \$\begingroup\$ so for big classes you shouldnt use copy-swap idiom? \$\endgroup\$ – SRG Mar 24 '18 at 14:31
  • \$\begingroup\$ @ Ben Steffan i guess i should write a comment pointing out why i am using one-does-all assignment operator. That i know my class is small. But i guess a better approach is to have two different operators and not use copy-swap idiom? as its the best all round approach \$\endgroup\$ – SRG Mar 24 '18 at 14:33
  • \$\begingroup\$ @SRG I recommend against using it for copy assignment for big classes, yes (for move assignment, it is basically the best option there is for both big and small classes). For a small class like yours, copy and swap is fine for combining move and copy assignment, but I'm not completely sure whether I personally would go with it, because making it a habit could lead to less effective code down the line. \$\endgroup\$ – Ben Steffan Mar 24 '18 at 15:01

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