Please help: The copy constructor for the Queue Class

[robbinn]

In the Queue Class, I have head and rear pointer for the first and last node in the list.

template <typename T>
class Queue
{
public:
    //CTOR
    Queue();

    //Big Three
    ~Queue();
    Queue(const Queue<T> &copyThis);
    Queue& operator = (const Queue&RHS);

    //other functions..

private:
    int _size;
    node<T>* head;
    node<T>* rear;

Here is the problem, my assignment operator (=) works perfect, but the copy constructor doesn't work.

which means:

Queue <int> new_node (old_node); //doesn't work.

Queue <int> new_node;
new_node = old_node;             //works.

Below is the code.

template <typename T>
Queue<T>::Queue(const Queue<T> &copyThis)   //copy constructor
{
    _size = copyThis._size;
    this->rear = _CopyList(copyThis.head,this->head);
}

template <typename T>
Queue<T>& Queue<T>::operator = (const Queue&RHS)  //assignment operator
{
    _size = RHS._size;
    this->rear = _CopyList(RHS.head,this->head);
    return *this;
}

The _CopyList function is passed by reference,so it will update the head.
Just in case, here is the _CopyList function:

template <typename T>
node<T>* _CopyList(node<T>* old_head,node<T>* &new_head)       //return the last node of the destination
{
    _insert_head(new_head,old_head->_item);  //copy the old head to new head

    node<T>* walker = new_head;             //walker for the new head

    old_head = old_head->_next;             //starts from the node after head

    while (old_head!= nullptr)              //insert after each node
    {
        _insert_after(walker,old_head->_item);
        old_head = old_head->_next;
        walker = walker->_next;
    }

    return walker;     //return the last node of the destination
}

I'm so confused why only the copy constructor doesn't work, what could be the problem? Thanks!!!

[keskiverto]

_CopyList_h is not _CopyList

Nevertheless, I don't understand how the assignment could possibly work. You don't handle the existing nodes.

[robbinn]

Sorry.. the wrong function, I edit to the right function now.

[JLBorges]

We can write the destructor, copy and move constructors/assignment operators in terms of push() and pop()

This is not the most efficient way of writing these foundation operators;
this ought to be fine here (a linked list implementation of the queue is not the most efficient implementation).


For example:

#include <iostream>
#include <cassert>

template < typename T > struct queue
{
    queue() = default ;

    ~queue() { assert( valid() ) ; while( !empty() ) pop() ; }

    queue( const queue& that ) // note: first and last are initialised (nullptr)
    {
        assert( that.valid() ) ;

        for( const node* n = that.first ; n != nullptr ; n = n->next ) push(n->value) ;

        assert( valid() ) ;
    }

    // move constructor: you may want to ignore this for now
    queue( queue&& that ) noexcept // note: first and last are initialised (nullptr)
    {
        assert( that.valid() ) ;

        using std::swap ;
        swap( first, that.first ) ;
        swap( last, that.last ) ;

        assert( valid() ) ;
    }

    queue& operator= ( const queue& that )
    {
        // EDIT: added check for self-assignment
        if( first == that.first ) return *this ;

        assert( that.valid() ) ;

        while( !empty() ) pop() ;
        for( const node* n = that.first ; n != nullptr ; n = n->next ) push(n->value) ;

        assert( valid() ) ;
        return *this ;
    }

    // move assignment operator: you may want to ignore this for now
    queue& operator= ( queue&& that ) noexcept
    {
        assert( that.valid() ) ;

        using std::swap ;
        swap( first, that.first ) ;
        swap( last, that.last ) ;

        assert( valid() ) ;
        return *this ;
    }

    bool empty() const noexcept { return first == nullptr ; }

    T& top() { if( empty() ) throw "queue is empty" ; return first->value ; }
    const T& top() const { if( empty() ) throw "queue is empty" ; return first->value ; }

    void push( const T& v )
    {
        if( empty() ) first = last = new node {v} ;
        else
        {
            last->next = new node {v} ;
            last = last->next ;
        }

        assert( valid() ) ;
    }

    void pop()
    {
        if( empty() ) throw "queue is empty" ;

        const node* old_first = first ;
        first = first->next ;
        delete old_first ;
        if( first == nullptr ) last = nullptr ;

        assert( valid() ) ;
    }

    void debug_dump() const
    {
        #ifndef NDEBUG

            assert( valid() ) ;

            if( !empty() )
            {
                std::cout << "top == " << top() << " : " ;
                for( const node* n = first ; n != nullptr ; n = n->next )
                    std::cout << n->value  << " => " ;
            }

            std::cout << "nullptr\n" ;

        #endif // NDEBUG
    }

    private:

        struct node { T value ; node* next = nullptr ; };

        node* first = nullptr ;
        node* last = nullptr ;

        bool valid() const
        {
            if( first == nullptr ) return last == nullptr ;
            return last->next == nullptr ;
        }
};

int main()
{
    queue<std::string> q ;
    q.debug_dump() ;

    for( std::string str : { "abc", "def", "ghi", "jkl", "mno", "pqr" } )
    {
       std::cout << "\npush " << str << '\n' ;
       q.push(str) ;
       q.debug_dump() ;
    }

    std::cout << "\n----------------\n" ;

    q.debug_dump();
    const queue another = q ; // copy construct
    another.debug_dump() ;

    std::cout << "----------------\n" ;

    while( !q.empty() )
    {
       std::cout << "\npop\n"  ;
       q.pop() ;
       q.debug_dump() ;
    }

    std::cout << "\n----------------\n" ;

    another.debug_dump() ;
    q = another ; // assign
    q.debug_dump();
}

http://coliru.stacked-crooked.com/a/8ec3fffa4efdbe1b

[keskiverto]

@JLBorges: Am I right in saying:

int main()
{
  queue<int> answer;
  answer.push( 42 );

  answer = answer; // ouch
}

[JLBorges]

Thanks! I've added a check for self-assignment now.

[keskiverto]

@robbinn:
Can you spot differences in the logic between JLBorges' push()
and your _CopyList(), _insert_head(), _insert_after()?

(Yours is obviously different, but where in there do the fatal errors lurk?

[robbinn]

@JLBorges @keskiverto Thank you soooo much! Even though the logic is different, I can see you are using a better way to solve this. I like your empty() function so much, that way I don't have to write while(walker!=nullptr) anymore.
btw: The for loop in the copy constructor is very interesting :)