Understanding linked list copy constructor

[Paul]

The code below is copy-pasted from a university website. I don't understand the need for void make_empty() which is called in the copy constructor. This function deletes all the nodes in the same way the destructor does. Also, I've read that you almost never need to invoke the destructor explicitly. If you shouldn't need to invoke the destructor explicitly, then surely you also shouldn't need to call a function which is an exact copy-paste of everything the destructor does.

Paul

BEGIN PASTE
This page presents an example of a class that implements an ordered list abstract data type using a linked list. The page begins with the class's header file; following the header file is the class's implementation file. The type of objects that a list contains is defined by the typedef statement near the beginning of the class's definition section. The comment accompanying the declaration specifies operations that must be defined for the Item type, since the class's functions apply those operations to Items.


// FILE: llist.h
// CLASS PROVIDED: List - an ordered list of Items.
//
// TYPEDEF for the List class:
// typedef _____ Item;
// Item is the data type of the items in a List. It may be any of
// the C++ built-in types (int, char, etc.) or a class with a default
// constructor, an assignment operator, operators to test for
// equality (==) and inequality (!=), a comparison operator (<), and
// output via the inserter (<<).
//
// CONSTRUCTORS for the List class:
// List( )
// Postcondition: The List has been initialized as an empty List.
//
// List ( const List& source )
// Postcondition: The invoking list has been initialized as a copy of
// the source List.
//
// MODIFICATION MEMBER FUNCTIONS for the List class:
// void make_empty ( )
// Postcondition: The List has been re-initialized to be empty.
//
// void insert ( const Item& entry )
// Precondition: The list does not currently contain the value entry.
// Postcondition: entry has been inserted in the position appropriate
// to its value.
//
// void remove ( const Item& target )
// Precondition: The list contains the value target.
// Postcondition: target has been removed from the List.
//
// void operator = ( const List& source )
// Postcondition: The invoking list has been assigned a copy of the
// source list.
//
// CONSTANT MEMBER FUNCTIONS for the List class:
// bool empty( ) const
// Postcondition: If the invoking List is empty, 1 (TRUE) has been
// returned; if the List is not empty, 0 (FALSE).
//
// size_t length( ) const
// Postcondition: The return value is the length (number of Items) in
// the List.
//
// bool present ( const Item& target ) const
// Postcondition: If target is in the list, 1 (TRUE) is returned,
// otherwise 0 (FALSE).
//
// int kth ( int k ) const
// Precondition: The list is not empty and 1 <= k <= length().
// Postcondition: The kth element in the List is returned.
//
// FRIEND FUNCTION for the List class:
// friend ostream& operator << ( ostream& out_s, const List& b )
// Postcondition: The contents of the List b have been written to the
// output stream out_s.
//
// VALUE SEMANTICS for the List class:
// Assignment and the copy constructor may be used with List objects.

#ifndef LIST1_H
#define LIST1_H

#include <cstdlib> // Provides size_t
#include <iostream> // Provides ostream

namespace CSCI301_list
{
class List
{
public:
// TYPEDEF
typedef int Item; // What can go in a list

// CONSTRUCTORS
List( ) { first = NULL; } // Inline
List( const List& source ); // Copy constructor

// DESTRUCTOR
~List( );

// MODIFICATION MEMBER FUNCTIONS
void make_empty ( );
void insert ( const Item& entry );
void remove ( const Item& target );
void operator = ( const List& source );

// CONSTANT MEMBER FUNCTIONS
bool empty( ) const { return first == NULL; } // Inline
std::size_t length( ) const;
bool present ( const Item& target ) const;
Item kth ( std::size_t k ) const;

// FRIEND FUNCTION for the List class:
friend std::ostream& operator << ( std::ostream& out_s,
const List& l );
private:
// DATA MEMBERS
struct Node
{
Item data;
Node *next;
};
Node *first;

// PRIVATE FUNCTION
Node* get_node ( const Item& entry, Node* link );
};
}
#endif







// FILE: llist.cxx

// CLASS IMPLEMENTED: List - an ordered list of Items.
// See llist.h for documentation.

// INVARIANT for the List implementation:
// 1. The items in the List are stored in a linked list in
// ascending order.
// 2. The member variable first points to the first node in
// the linked list. When the list is empty, first is NULL.

#include <cstdlib>
#include <iostream>
#include <cassert>
#include "llist.h"
using namespace std;

namespace CSCI301_list
{
// Default constructor is inline.

// Copy constructor
List::List ( const List& source )
{
Node* p; // Will traverse the source List.
Node* last; // Will always point to the new List's last Node.

if ( source.first == NULL ) // If the source list is empty ...
first = NULL;
else
{
first = get_node(source.first->data,NULL); // Copy the first Node.
last = first;
p = source.first->next;
while ( p != NULL ) // Copy remaining Nodes.
{
last->next = get_node(p->data,NULL);
last = last->next;
p = p->next;
}
}
}

// Destructor
List::~List( )
{
Node* temp;

while ( first != NULL )
{
temp = first;
first = first -> next;
delete temp;
}
}

// Modification member functions
void List::make_empty ( )
{
Node* temp;

while ( first != NULL )
{
temp = first;
first = first -> next;
delete temp;
}
}

void List::insert ( const Item& entry )
{
Node *prev;

assert ( ! present(entry) );

if ( first == NULL || entry < first->data )
first = get_node(entry,first);
else
{
prev = first;
while ( prev->next != NULL && prev->next->data < entry )
prev = prev->next;
prev->next = get_node(entry,prev->next);
}
}

void List::remove ( const Item& target )
{
Node *temp;
Node *prev;

assert ( present(target) );

prev = first;
if ( prev->data == target )
{
first = first->next;
delete prev;
}
else
{
while ( prev->next != NULL && prev->next->data < target )
prev = prev->next;
temp = prev->next;
prev->next = temp->next;
delete temp;
}
}

void List::operator = ( const List& source )
{
Node* p;
Node* last;

if ( &source != this ) // Self-assignment?
{
make_empty();
if ( source.first != NULL )
{
first = get_node(source.first->data,NULL); // Copy the first Node.
last = first;
p = source.first->next;
while ( p != NULL ) // Copy the remaining Nodes.
{
last->next = get_node(p->data,NULL);
last = last->next;
p = p->next;
}
}
}
}

// Constant member functions
size_t List::length( ) const
{
Node *cursor;
size_t count;

count = 0;
for ( cursor=first; cursor != NULL; cursor=cursor->next )
++count;
return count;
}

bool List::present ( const Item& target ) const
{
Node *cursor;

for ( cursor=first;
cursor!=NULL && cursor->data!=target;
cursor=cursor->next )
; // The loop's body is empty.
return ( cursor != NULL );
}

List::Item List::kth ( size_t k ) const
{
Node *cursor;
size_t count;

assert ( 1 <= k && k <= length() );

cursor = first;
for (count=1; count<k; ++count)
cursor = cursor->next;
return cursor->data;
}

// Friend Function
ostream& operator << ( ostream& out_s, const List& l )
{
List::Node *cursor;

out_s << '(';
for ( cursor=l.first;
cursor != NULL && cursor->next != NULL;
cursor=cursor->next )
out_s << cursor->data << ", ";
if ( cursor != NULL )
out_s << cursor->data;
out_s << ')';

return out_s;
}

// Private function
List::Node* List::get_node ( const Item& entry, Node* link )
{
Node *temp;

temp = new Node;
temp->data = entry;
temp->next = link;
return temp;
}
}

[Paul N]

On Sunday, 21 June 2015 17:02:09 UTC+1, Paul wrote:
> The code below is copy-pasted from a university website. I don't understand the need for void make_empty() which is called in the copy constructor.

I can't see it being called in the copy constructor - are you sure?

> This function deletes all the nodes in the same way the destructor does. Also, I've read that you almost never need to invoke the destructor explicitly. If you shouldn't need to invoke the destructor explicitly, then surely you also shouldn't need to call a function which is an exact copy-paste of everything the destructor does.

Presumably when a list goes out of existence you want the memory used by its members to be freed. You may also want to clear the members of a list without destroying the list itself. So there is code to do this. It all seems perfectly normal. Except, that, if you're going to write the code for make_empty() it would seem sensible to just call this function in the destructor instead of writing the code again.


[snip actual code]

[JiiPee]

On 21/06/2015 21:05, Paul N wrote:
> Except, that, if you're going to write the code for make_empty() it
> would seem sensible to just call this function in the destructor
> instead of writing the code again. [snip actual code]

agree

[Paul]

Thanks. Sorry, I meant assignment, not the copy constructor.

Paul

[Paul]

On Sunday, June 21, 2015 at 9:05:21 PM UTC+1, Paul N wrote:

Thanks. make_empty() is called in assignment but not in the copy constructor. Is there a good reason to treat these two cases differently? Thank You.

Paul

[Carlos Romero Brox]

I think copy ctor is used to initialize new objects (initialize a variable, pass an argument/return a value from a function) , there is no a previous value involved. Assignment operator replaces an "old" value with a "new" one and if there are resources associated to the old value, they should be freed

[Paul N]

If you do an assignment - say A = B where A and B are both lists - then you want to clear out the existing members of A, and then fill A up with copies of what is in list B. That's why you need the make_empty(). When you run a copy constuctor, the new list being created won't have any members yet and so there is no need to clear them out.

[Paul]

On Monday, June 22, 2015 at 9:38:21 PM UTC+1, Paul N wrote:
> On Monday, 22 June 2015 13:18:13 UTC+1, Paul wrote:
> > On Sunday, June 21, 2015 at 9:05:21 PM UTC+1, Paul N wrote:
> > > On Sunday, 21 June 2015 17:02:09 UTC+1, Paul wrote:
> > > > The code below is copy-pasted from a university website. I don't understand the need for void make_empty() which is called in the copy constructor.
> > >
> > > I can't see it being called in the copy constructor - are you sure?
> > >
> > > > This function deletes all the nodes in the same way the destructor does. Also, I've read that you almost never need to invoke the destructor explicitly. If you shouldn't need to invoke the destructor explicitly, then surely you also shouldn't need to call a function which is an exact copy-paste of everything the destructor does.
> > >
> > > Presumably when a list goes out of existence you want the memory used by its members to be freed. You may also want to clear the members of a list without destroying the list itself. So there is code to do this. It all seems perfectly normal. Except, that, if you're going to write the code for make_empty() it would seem sensible to just call this function in the destructor instead of writing the code again.
> > >
> > >
> > > [snip actual code]
> >
> > Thanks. make_empty() is called in assignment but not in the copy constructor. Is there a good reason to treat these two cases differently? Thank You.
>

Thanks for the explanations.

Paul

[alf.p.s...@gmail.com]

On Monday, June 22, 2015 at 10:01:57 AM UTC+2, Paul wrote:
> On Sunday, June 21, 2015 at 9:05:21 PM UTC+1, Paul N wrote:
> > On Sunday, 21 June 2015 17:02:09 UTC+1, Paul wrote:
> > > The code below is copy-pasted from a university website. I don't understand the need for void make_empty() which is called in the copy constructor.
>

> Thanks. Sorry, I meant assignment, not the copy constructor.

When a copy assignment operator is called, the list is already initialized and may contain nodes. These have to be removed. This is work that the copy constructor doesn't have to do.

Conversely, when the copy constructor is invoked there are no nodes to be removed, and the list is not yet initialized, so the copy constructor has to initialize various members. This is work that the copy assignment operator doesn't have to do.

Copy assignment: clear first.
Copy construction: initialize first.

Still, there is no need to do that removal/clearing by duplicating code...

The basic approach for a copy assignment operator is to express it in terms of copy construction, destruction and a no-throwing swap (like std::swap):

class List
{
...

void swap_with( List& other ) noexcept
{
// Implementation of no-throwing swap
// For example, std::swap( head, other.head ), etc.
}

auto operator=( List const& other )
-> List&
{
List the_copy( other ); // Invokes copy constructor
swap_with( the_copy );
return *this; // Invokes destructor for old list
}

With this idiomatic approach code is not duplicated, just reused, and any exception occurring during the copying will leave the list in its original good state.

Some people prefer to pass the argument by value, which means that the copy constructor is invoked at the point of call rather than in the assignment operator implementation itself, but at first sight it may be a little baffling:

auto operator=( List the_copy )
-> List&
{
swap_with( the_copy );
return *this; // Invokes destructor for old list
}

Notes about the notation above:

* Instead of a "swap_with" method, it's my impression that most people prefer a non-member "swap" function, perhaps expressed as an inline "friend" function. However, a non-member "swap" function can easily be expressed in terms of a "swap_with" method. The opposite, expressing a member function in terms of non-member function, is a bit unnatural to me.

* Instead of the C++11 "auto" syntax for functions (a.k.a. trailing return type), most people still prefer the old C++03 function declaration syntax. I see no reason to use the old syntax except inertia, since the new syntax covers it all. The new syntax e.g. allows using class-local types in the return type without qualification, and it makes it easier for me to spot the function name.

Cheers & hth.,

- Alf

[alf.p.s...@gmail.com]

On Tuesday, June 23, 2015 at 12:00:12 AM UTC+2, alf.p.s...@gmail.com wrote:
> ...

Sorry for the Quoted Printable encoding etc., that's Google Groups, not me. ;-)

[Paul N]

You say that "the copy constructor has to initialize various members. This is work that the copy assignment operator doesn't have to do." but your code means that the copy assignment operator goes through all that the copy constructor does and all that the destructor does. Is it assumed that the neatness of the code and the ease of making it exception-safe outweighs any possible run-time inefficiency?

[Paul N]

On Monday, 22 June 2015 22:43:11 UTC+1, Paul wrote:
> Thanks for the explanations.
>
> Paul

I found a tutorial about linked lists at http://www.panix.com/~elflord/cpp/list_howto/ It's unintentionally quite funny, as he starts off by saying that most textbooks make a terrible mess of linked links, and gives examples, but later finds he has painted himself into a corner and comments of his own code that "the ugliness of this is noted"! The code may also be a bit old-fashioned nowadays. Nevertheless, it covers a lot of the details in depth and is worth reading.

[alf.p.s...@gmail.com]

On Wednesday, June 24, 2015 at 1:11:22 AM UTC+2, Paul N wrote:
> On Monday, 22 June 2015 23:00:12 UTC+1, alf.p.s...@gmail.com wrote:

> > ...

> You say that "the copy constructor has to initialize various members. This is work that the copy assignment operator doesn't have to do." but your code means that the copy assignment operator goes through all that the copy constructor does and all that the destructor does. Is it assumed that the neatness of the code and the ease of making it exception-safe outweighs any possible run-time inefficiency?

Yes.

For many types there will not be any significant run-time cost anyway, but with a linked list there may for example be a dummy header node which has to be established at construction but not for assignment. And in that situation the copy-swap idiom for assignment will have an extra dynamic allocation, which can be significant. So in the end, if there is a speed problem and this code is suspected of being the culprit, the first rule of optimization is to measure.

So, one may choose to not implement copy assignment in terms of copy construction, for efficiency. But that's as far as one should go, IMHO. I have had to maintain code where copy construction was implemented in terms of copy assignment, i.e. the other way around, and it was ... unpleasant. The problems start manifesting themselves when the classes are inherited from.

So, summing up, the compiler's generated assignment operator is a nice default, but it can leave the object in a partially changed state when some copying throws an exception; the copy-swap idiom is a nice simple exception safe alternative when the compiler's default doesn't do; a more direct assignment implementation can be reasonable depending on efficiency requirements and measurements,;and doing the opposite of the idiomatic way, namely expressing construction in terms of assignment, can/will be problematic and costly.

[Paul]

Thanks. I like it that it covers templates, something that's left out of most accounts. It's particularly important because many programmer-interview questions say things like "how would you reverse a linked list?" To my mind, any answer that doesn't generalize using templates is a weak one.

Paul

[Richard]

[Please do not mail me a copy of your followup]

Paul N <gw7...@aol.com> spake the secret code
<4e652310-4c8d-4cc9...@googlegroups.com> thusly:

>On Monday, 22 June 2015 22:43:11 UTC+1, Paul wrote:
>> Thanks for the explanations.
>>
>> Paul
>
>I found a tutorial about linked lists at
>http://www.panix.com/~elflord/cpp/list_howto/

The main disadvantage of a list or map is that it pummels the cache
because the data doesn't retain memory locality.

Try this short video from Bjarne Stroustrup:
<https://www.youtube.com/watch?v=YQs6IC-vgmo>
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Öö Tiib]

On Wednesday, 24 June 2015 06:03:06 UTC+3, alf.p.s...@gmail.com wrote:
>
> So, one may choose to not implement copy assignment in terms of copy
> construction, for efficiency. But that's as far as one should go, IMHO.
> I have had to maintain code where copy construction was implemented
> in terms of copy assignment, i.e. the other way around, and it was ...
> unpleasant. The problems start manifesting themselves when the classes
> are inherited from.

When classes are inherited from then it is perhaps better not
to have public 'swap' or public copy constructions/assignments.

I typically move copy/move construction of base classes to protected
and assignments I delete. Otherwise it is too fragile in sense that
bad usages will compile and manifest themselves only runtime.