Queue Implementation

[mpark4656]

This is my implementation of Queue using singly-linked list.

I've been testing this and I quite do not understand why the program crashes when I try using qualified swap in the driver.

For example, this crashes the program. Shouldn't it look for the customized swap and use that function to swap the two objects?

int main()
{
    my::Queue<int> test1;

    test1.push( 4 );
    test1.push( 5 );
    test1.push( 6 );
    test1.push( 7 );

    my::Queue<int> test2;

    test2.push( 1 );
    test2.push( 2 );
    test2.push( 3 );
    test2.push( 4 );


    std::swap( test1 , test2 );
}

Implementation

/*
Queue Implementation - FIFO (First In, First Out)

Supported Operations
1. empty
2. size
3. front
4. back
5. push_back
6. pop_front
7. swap
*/

#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED

#include <utility>
namespace my
{
    /*------------------------------------------------------------------------
                              CLASS DECLARATION
    ------------------------------------------------------------------------*/
    template<typename Type>
    class Queue
    {
    private:
        // Node Structure
        struct QueueNode
        {
            Type data;
            QueueNode* next;

            QueueNode( const Type &x ): data{ x } , next{ nullptr } {}
            QueueNode( Type &x , QueueNode* n ): data{ x } , next{ n } {}
        };

    public:

        // Default Constructor
        Queue();

        // Copy Constructor
        Queue( const Queue &rhs );

        // Move Constructor
        Queue( Queue &&rhs );

        // Copy/Move Assignment
        Queue & operator=( Queue rhs );

        // Destructor
        ~Queue();

        // Public Function to add an element
        void push( const Type &x );

        // Public Function to remove an element
        void pop();

        // Member-wise Swap Function
        Queue & swap( Queue &that );

        // Return theSize
        int size() const;

        // Test whether the container is empty
        bool empty() const;

        // Return modifiable reference to the first element
        Type & front();

        // Return modifiable reference to the last element
        Type & back();

    private:
        // Internal Function to clear all contents - Called by Destructor
        void clear();

        // Internal Function to add an element
        void push_back( const Type &x , QueueNode* t );

        // Internal Function to remove an element
        void pop_front( QueueNode* h );

        QueueNode* head;
        QueueNode* tail;
        int theSize;
    };

    /*------------------------------------------------------------------------
                              FUNCTION DEFINITION
    ------------------------------------------------------------------------*/
    // Default Constructor
    template<typename Type>
    Queue<Type>::Queue(): head{ nullptr } , tail{ nullptr } , theSize{ 0 }
    { }

    // Copy Constructor
    template<typename Type>
    Queue<Type>::Queue( const Queue &rhs )
    : head{ nullptr } , tail{ nullptr } , theSize{ 0 }
    {
        for( auto n = rhs.head ; n != nullptr ; n = n->next ) {
            push_back( n->data , tail );
        }
    }

    // Move Constructor
    template<typename Type>
    Queue<Type>::Queue( Queue &&rhs )
    {
        this->swap( rhs );
    }

    // Copy/Move Assignment
    template<typename Type>
    Queue<Type> & Queue<Type>::operator=( Queue rhs )
    {
        return this->swap( rhs );
    }

    // Destructor
    template<typename Type>
    Queue<Type>::~Queue()
    {
        clear();
    }

    // Public Function to add an element
    template<typename Type>
    void Queue<Type>::push( const Type &x )
    {
        push_back( x , tail );
    }

    // Internal Function to add an element
    template<typename Type>
    void Queue<Type>::push_back( const Type &x , QueueNode* t )
    {
        if( t == nullptr ) {
            tail = new QueueNode{ x };
            head = tail;
        }
        else {
            tail->next = new QueueNode{ x };
            tail = tail->next;
        }

        theSize ++;
    }

    // Public Function to remove an element
    template<typename Type>
    void Queue<Type>::pop()
    {
        pop_front( head );
    }

    // Internal Function to remove an element
    template<typename Type>
    void Queue<Type>::pop_front( QueueNode* h )
    {
        if( h == nullptr ) {
            ; // If the container is empty, do nothing
        }
        else if( h->next == nullptr ) {
            tail = nullptr;
            head = nullptr;
            delete h;
            theSize --;
        }
        else {
            head = h->next;
            delete h;
            theSize --;
        }
    }

    // Return modifiable reference to the front
    template<typename Type>
    Type & Queue<Type>::front()
    {
        return head->data;
    }

    // Return modifiable reference to the back
    template<typename Type>
    Type & Queue<Type>::back()
    {
        return tail->data;
    }

    // Return theSize
    template<typename Type>
    int Queue<Type>::size() const
    {
        return theSize;
    }

    // Test whether the container is empty
    template<typename Type>
    bool Queue<Type>::empty() const
    {
        return theSize == 0;
    }

    // Member-wise Swap Function
    template<typename Type>
    Queue<Type> & Queue<Type>::swap( Queue<Type> &that )
    {
        using std::swap;
        swap( head , that.head );
        swap( tail , that.tail );
        swap( theSize , that.theSize );

        return *this;
    }

    // Internal Function to delete all contents - Called by Destructor
    template<typename Type>
    void Queue<Type>::clear()
    {
        while( head != nullptr ) {
            pop_front( head );
        }
    }

    template<typename Type>
    void swap( Queue<Type> &lhs , Queue<Type> &rhs )
    {
        lhs.swap( rhs );
    }
}
#endif // QUEUE_H_INCLUDED

[JLBorges]

> I quite do not understand why the program crashes when I try using qualified swap

The move constructor does not initialise the members.

// Queue<Type>::Queue( Queue &&rhs ) 
Queue<Type>::Queue( Queue &&rhs ) : head { nullptr }, tail { nullptr }, theSize { 0 }
{
        this->swap( rhs );
}

> Shouldn't it look for the customized Tswap and use that function to swap the two objects?

To use the customised swap, use unqualified swap.

// std::swap( test1 , test2 );
using std::swap ; swap( test1 , test2 ); // canonical; ADL would find my::swap 

[mpark4656]

Thank you both for the replies.

@gentleguy
Queue::swap() is utilized in the move constructor and the assignment operator. This swap function is more efficient than the qualified swap and that's why I made it - http://www.cplusplus.com/forum/beginner/196459/. Also, std::queue offers a public swap() function - http://www.cplusplus.com/reference/queue/queue/swap/. The goal in this exercise was to provide similar operations as the Standard Template Library, so I made Queue::swap() a public function and allow users to call it and swap objects as they would with std::queue.

test1.swap( test2 );

One operation I did not implement here is the emplace function and I will probably do that later.
Did you find any problems with how the Queue::swap() is coded?


@JLBorges
That fixed the issue.

The funny thing is I made the same mistake with the copy constructor. After testing, I fixed the copy constructor and included the initialization list but totally forgot about the move constructor. Spent 3-4 hours trying to figure this out before posting here and now I feel like bashing my head against the monitor.

In the last thread, you said

To protect uninformed programmers who may write std::swap(a,b) ;
where they should have written using std::swap ; swap(a,b) ;.
If swap in namespace std is spcialised, the specialisation would call the custom swap.

So, for a minute, I thought using std::swap would still call the customized swap that I defined outside the class declaration. Now that I think about it.. I did not really specialize the std::swap, did I? I defined the non-member swap inside my namespace.

[JLBorges]

> The funny thing is I made the same mistake with the copy constructor.

Specifying in-class default member initialisers would mitigate this kind of error.

    private:
        QueueNode* head = nullptr ;
        QueueNode* tail = nullptr ;
        int theSize = 0 ;

> I did not really specialize the std::swap, did I?

No. To specialise std::swap for my::Queue

namespace std
{
    template< typename T > 
    void swap( my::Queue<T>& first, my::Queue<T>& second ) { first.swap(second) ; } 
}

[mpark4656]

Thanks again, JLBorges!