Thread: push_front method for class List

Within methods.cpp I am working on the method for push_front for class List. The strings are being displayed backwards and all the string values from push_back disappear.

I'm not sure if (tail) is pointing to the wrong value which is causing the rest of the output from push_back to disappear.

It is supposed to look something like this:
List::List( )

la contains:
00348970 hi next: 00348750
00348750 mom next: 003487D8
003487D8 please next: 00348860
00348860 send next: 003488E8
003488E8 money next: 00000000

Instead it is displays "mom" first then "hi" and everything else disappears.





List.h

Code:

#include    <iostream>
#include    <iomanip>
#include    <string>
using namespace std;


class Node
{
  public:
                                    // constructor
    Node( const string &, Node * );

    const string &get_word( ) const;// get a const reference to word
    Node   *get_next( ) const;      // get a Node * (value of next)
    Node   *set_next( Node * );     // set next to a new value

  private:
    string   word;
    Node    *next;
};


class List
{
  public:
    List( );                        // constructor
    List( const List & );           // copy constructor
    ~List( );                       // destructor

                                    // push a node to the back of list
    void push_back( const string & );
                                    // push a node to the front of list
    void push_front( const string & );

    void pop_front( );              // pop first element of list
                                    // output a list object
    friend ostream &operator <<( ostream &, const List & );

  private:
    Node    *head;
    Node    *tail;
};

main.cpp

Code:

#include    "List.h"


int main( )
{
    List la;                    // create list la

    la.push_front( "mom" );
    la.push_back( "please" );
    la.push_back( "send" );
    la.push_back( "money" );
    la.push_front( "hi" );

    cout << "\nla contains:\n" << la << '\n';

    List lb( la );              // copy list la to lb

    cout << "lb contains:\n" << lb << '\n';

    lb.pop_front( );
    lb.pop_front( );
    lb.push_front( "mother" );
    lb.push_front( "dear" );
    lb.push_back( "Bubba" );

    cout << "lb contains:\n" << lb << '\n';

    return 0;
}

methods.cpp

Code:

#include    "List.h"

/*******************************methods for Node*******************************/
                            
							// constructor: init. a Node
Node::Node( const string &s, Node * p )
{
    word = s;               // init. word with a copy of s
    next = p;               // next points to p
}

                            // return a const ref to word
const string &Node::get_word( ) const
{
    return word;
}

                            // return a pointer to next node
Node *Node::get_next( ) const
{
    return next;
}

                            // sets next to pointer p and return next
Node *Node::set_next( Node * p )
{
    next = p;               // next now points to p
    return next;
}




/*******************************methods for List*******************************/

List::List( )               // constructor: init. head and tail
{
    cout << "List::List( )\n";

    head = tail = 0;
}


List::List( const List & )
{


}


List::~List( )              // destructor: deallocate the list
{
    cout << "List::~List( )\n";

    for( Node *p = head; p; )
    {
        Node *tmp = p;      // remember current pointer
        p = p->get_next( ); // advance p to the next Node
        delete tmp;         // deallocate tmp
        cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n';
    }
}


void List::push_back( const string &s )
{
                            // p points to a new node
    Node *p = new Node( s, 0 );

    if( tail == 0 )         // tail not pointing to a node yet?
    {
        head = tail = p;    // head & tail point to new node in the list
    }
    else
    {                       // tail->next points to new node
        tail->set_next( p );
        tail = p;           // tail points to last node in the list
    }
}


void List::push_front( const string &s )
{
	  Node *p = new Node( s, 0 );

    if( tail == 0 )         
    {
        head = tail = p;   
    }
    else
    {                     
        head->set_next( p );
        tail = p;           
    }
}


void List::pop_front( )
{

	
	
}


ostream &operator <<( ostream &out, const List &list )
{
    for( Node *p = list.head; p != 0; p = p->get_next( ) )
    {
        cout << p << '\t' << setw( 8 ) << p->get_word( )
             << '\t' << "next:" << '\t' << p->get_next( ) << '\n';
    }

    return out;
}

The new node will replace the head, which means the current head should become p's next pointer. Further, if tail has been set then nothing needs to be done with it since only the head of the list is changing:

Code:

void List::push_front( const string &s )
{
    head = new Node( s, head );

    if( tail == 0 )         
    {
        // Set tail if it hasn't been set yet
        tail = head;   
    }
}

My attempts at creating a copy constructor in methods.cpp has gotten me; error: function will cause runtime stack overflow (line 47).

Code:

#include    "List.h"

/*******************************methods for Node*******************************/
                            
							// constructor: init. a Node
Node::Node( const string &s, Node * p )
{
    word = s;               // init. word with a copy of s
    next = p;               // next points to p
}

                            // return a const ref to word
const string &Node::get_word( ) const
{
    return word;
}

                            // return a pointer to next node
Node *Node::get_next( ) const
{
    return next;
}

                            // sets next to pointer p and return next
Node *Node::set_next( Node * p )
{
    next = p;               // next now points to p
    return next;
}




/*******************************methods for List*******************************/

List::List( )               // constructor: init. head and tail
{
    cout << "List::List( )\n";

    head = tail = 0;
}


List::List( const List & la)
{
	List lb = la;
}


List::~List( )              // destructor: deallocate the list
{
    cout << "List::~List( )\n";

    for( Node *p = head; p; )
    {
        Node *tmp = p;      // remember current pointer
        p = p->get_next( ); // advance p to the next Node
        delete tmp;         // deallocate tmp
        cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n';
    }
}


void List::push_back( const string &s )
{
                            // p points to a new node
    Node *p = new Node( s, 0 );

    if( tail == 0 )         // tail not pointing to a node yet?
    {
        head = tail = p;    // head & tail point to new node in the list
    }
    else
    {                       // tail->next points to new node
        tail->set_next( p );
        tail = p;           // tail points to last node in the list
    }
}


void List::push_front( const string &s )
{
	head = new Node( s, head );
 
		if( tail == 0 )        
		{       
			tail = head;    // Set tail
		}
}


void List::pop_front( )
{

	/*head = head->get_next(  );*/
	
}


ostream &operator <<( ostream &out, const List &list )
{
    for( Node *p = list.head; p != 0; p = p->get_next( ) )
    {
        cout << p << '\t' << setw( 8 ) << p->get_word( )
             << '\t' << "next:" << '\t' << p->get_next( ) << '\n';
    }

    return out;
}

I was under the assumption that you can just simply set one list to another.

Elysia, thank you very much for taking the time to help me understand the logic. I appreciate you.

Originally Posted by Elysia

Code:

List::List( const List & la)
{
    List lb = la;
}

What does this do? This creates some temporary lb, copies la into lb, then destroys lb. What good does that do?

The purpose of a copy constructor is to make *this == that, where that is the parameter to the copy constructor.
The copy is meant to be invoked outside the class by

List lb = la;

where la is some List.
So it is even worse--your copy constructor does no useful work and just calls itself over and over. You need to write code that makes *this == that, by copying over member variables, ie internal state, and possibly do housekeeping as necessary.

The output seems to be favorable now, but after the destructor deallocates the list and prints the deallocation to the screen an error is recognized.

Unhandled exception

CXX0017: Error: symbol "la" not found

CXX0017: Error: symbol "lb" not found

I'm not to sure what this means or what I should be focusing my attention to.

Originally Posted by Elysia

Post thy updated code.

Code:

#include    "List.h"

/*******************************methods for Node*******************************/
                            
							// constructor: init. a Node
Node::Node( const string &s, Node * p )
{
    word = s;               // init. word with a copy of s
    next = p;               // next points to p
}

                            // return a const ref to word
const string &Node::get_word( ) const
{
    return (*this).word;
}

                            // return a pointer to next node
Node *Node::get_next( ) const
{
    return (*this).next;
}

                            // sets next to pointer p and return next
Node *Node::set_next( Node * p )
{
    next = p;               // next now points to p
    return (*this).next;
}




/*******************************methods for List*******************************/

List::List( )               // constructor: init. head and tail
{
    cout << "List::List( )\n";

    head = tail = 0;
}


List::List( const List & la)
{
	 if( this != &la )
	 {
		/* delete [  ] lb;*/

			for( Node *p = la.head; p != 0; p = p->get_next( ) )
			{
	
				*this = la;
				
			}
	 
	 }
}


List::~List( )              // destructor: deallocate the list
{
    cout << "List::~List( )\n";

    for( Node *p = head; p; )
    {
        Node *tmp = p;      // remember current pointer
        p = p->get_next( ); // advance p to the next Node
        delete tmp;         // deallocate tmp
        cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n';
    }
}


void List::push_back( const string &s )
{
                            // p points to a new node
    Node *p = new Node( s, 0 );

    if( tail == 0 )         // tail not pointing to a node yet?
    {
        head = tail = p;    // head & tail point to new node in the list
    }
    else
    {                       // tail->next points to new node
        tail->set_next( p );
        tail = p;           // tail points to last node in the list
    }
}


void List::push_front( const string &s )
{
	head = new Node( s, head );
 
		if( tail == 0 )        
		{       
			tail = head;    // Set tail
		}
}


void List::pop_front( )
{

	head = head->get_next(  );
	
}


ostream &operator <<( ostream &out, const List &list )
{
    for( Node *p = list.head; p != 0; p = p->get_next( ) )
    {
        cout << p << '\t' << setw( 8 ) << p->get_word( )
             << '\t' << "next:" << '\t' << p->get_next( ) << '\n';
    }

    return out;
}

Code:

#include    <iostream>
#include    <iomanip>
#include    <string>
using namespace std;


class Node
{
  public:
                                    // constructor
    Node( const string &, Node * );

    const string &get_word( ) const;// get a const reference to word
    Node   *get_next( ) const;      // get a Node * (value of next)
    Node   *set_next( Node * );     // set next to a new value

  private:
    string   word;
    Node    *next;
};


class List
{
  public:
    List( );                        // constructor
    List( const List & );           // copy constructor
    ~List( );                       // destructor

                                    // push a node to the back of list
    void push_back( const string & );
                                    // push a node to the front of list
    void push_front( const string & );

    void pop_front( );              // pop first element of list
                                    // output a list object
    friend ostream &operator <<( ostream &, const List & );

  private:
    Node    *head;
    Node    *tail;
};

Great my compiler crashed again. I gotta reboot. Why does it keep happening?? gosh

The program no longer gives an error after deallocation, but the output is still unfavorable.
Rewriting the copy constructor and pop_front produced very little positive results, even though it helped remove a bug.

Code:

#include    "List.h"

/*******************************methods for Node*******************************/
                            
							// constructor: init. a Node
Node::Node( const string &s, Node * p )
{
    word = s;               // init. word with a copy of s
    next = p;               // next points to p
}

                            // return a const ref to word
const string &Node::get_word( ) const
{
    return (*this).word;
}

                            // return a pointer to next node
Node *Node::get_next( ) const
{
    return (*this).next;
}

                            // sets next to pointer p and return next
Node *Node::set_next( Node * p )
{
    next = p;               // next now points to p
    return (*this).next;
}




/*******************************methods for List*******************************/

List::List( )               // constructor: init. head and tail
{
    cout << "List::List( )\n";

    head = tail = 0;
}


List::List( const List & la)
{	
			for( Node *p = la.head; p != 0; p = p->get_next( ) )  // p->set-next( 0 ) ?
			{
				 tail = head = 0;

				push_back( p->get_word(  ) );
				
				/**this = la;*/		
				
			}
}


List::~List( )              // destructor: deallocate the list
{
    cout << "List::~List( )\n";

    for( Node *p = head; p; )
    {
        Node *tmp = p;      // remember current pointer
        p = p->get_next( ); // advance p to the next Node
        delete tmp;         // deallocate tmp
        cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n';
    }
}


void List::push_back( const string &s )
{
                            // p points to a new node
    Node *p = new Node( s, 0 );

    if( tail == 0 )         // tail not pointing to a node yet?
    {
        head = tail = p;    // head & tail point to new node in the list
    }
    else
    {                       // tail->next points to new node
        tail->set_next( p );
        tail = p;           // tail points to last node in the list
    }
}


void List::push_front( const string &s )
{
	head = new Node( s, head );
 
		if( tail == 0 )        
		{       
			tail = head;    // Set tail
		}
}


void List::pop_front( )
{

	//head = head->get_next(  );

	if( head )              
    {
        Node *tmp = head;
        head      = head->get_next( );

        delete tmp;         // delete node to be removed

        if( head == 0 )     
        {
            tail = 0;
        }
        else
        {
            head->set_next( 0 );
        }
    }
}


ostream &operator <<( ostream &out, const List &list )
{
    for( Node *p = list.head; p != 0; p = p->get_next( ) )
    {
        cout << p << '\t' << setw( 8 ) << p->get_word( )
             << '\t' << "next:" << '\t' << p->get_next( ) << '\n';
    }

    return out;
}

Originally Posted by Elysia

>>*this = la;
This essentially calls the copy assignment operator. And so, for every node in your list, you call the copy assignment operator on the whole list passed to the copy constructor. Seems pretty excessive.
Then question is: what does the copy assignment operator do? Well, you don't have one, so the compiler would provide one for you that does shallow copying of the list (copying over the pointers). That would seem to work until you made a change in one list, which causes the changes to carry over to the copy of the list. Not so good idea.

Here's the thing. You need to stop thinking in terms of lists. This is inside the list. You must define how a list is copied. For example, if you have a car and want to make a copy of it, you would do

Car a = b;

(assuming b is a Car.)
This will call Car::Car(const Car& that). In that function, you must copy over all the state in that into *this such that after the copy constructor is run, a == b should yield true.
You can't do *this = that, because again, that would copy the car. But the compiler doesn't know how to copy a car, so it calls Car::Car(const Car&), which is what you are trying to define!
In short, you must copy over member variables and sometimes, you may have to do additional work manipulating these member variables such that it causes both objects to be equal (but don't worry about that later bit just yet; experience will let you know what I mean).

Here's an example of a Number class:

Code:

Number::Number(const Number& that)
{
	a = that.a;
	b = that.b;
}

I see what you mean about coping over the member variables.

I'm still getting an unhandled exception.

Why is money being copied over twice??

Code:

#include    "List.h"

/*******************************methods for Node*******************************/
                            
							// constructor: init. a Node
Node::Node( const string &s, Node * p )
{
    word = s;               // init. word with a copy of s
    next = p;               // next points to p
}

                            // return a const ref to word
const string &Node::get_word( ) const
{
    return (*this).word;
}

                            // return a pointer to next node
Node *Node::get_next( ) const
{
    return (*this).next;
}

                            // sets next to pointer p and return next
Node *Node::set_next( Node * p )
{
    next = p;               // next now points to p
    return (*this).next;
}




/*******************************methods for List*******************************/

List::List( )               // constructor: init. head and tail
{
    cout << "List::List( )\n";

    head = tail = 0;
}


List::List( const List & la)
{	
			for( Node *p = la.head; p != 0; p = p->get_next( ) ) 
			{
				 tail = la.tail;
				 head = la.head;

				push_back( p->get_word(  ) );
								
			}
}


List::~List( )              // destructor: deallocate the list
{
    cout << "List::~List( )\n";

    for( Node *p = head; p; )
    {
        Node *tmp = p;      // remember current pointer
        p = p->get_next( ); // advance p to the next Node
        delete tmp;         // deallocate tmp
        cout << "deallocated\t" << tmp << "\tnext is\t" << p << '\n';
    }
}


void List::push_back( const string &s )
{
                            // p points to a new node
    Node *p = new Node( s, 0 );

    if( tail == 0 )         // tail not pointing to a node yet?
    {
        head = tail = p;    // head & tail point to new node in the list
    }
    else
    {                       // tail->next points to new node
        tail->set_next( p );
        tail = p;           // tail points to last node in the list
    }
}


void List::push_front( const string &s )
{
	head = new Node( s, head );
 
		if( tail == 0 )        
		{       
			tail = head;    // Set tail
		}
}


void List::pop_front( )
{

	head = head->get_next(  );

}


ostream &operator <<( ostream &out, const List &list )
{
    for( Node *p = list.head; p != 0; p = p->get_next( ) )
    {
        cout << p << '\t' << setw( 8 ) << p->get_word( )
             << '\t' << "next:" << '\t' << p->get_next( ) << '\n';
    }

    return out;
}