Operator assignment issue, part III

[Chemical Engineer]

Sorry to make so many threads about a similar issue; just changed up the code so I didn't want the different versions getting mixed up since this is confusing enough already.

I have a statistics program. It reads a file that looks like this:

1   1
2   4
3   9
4   16
5   25
60  3600

I want to read each line there into a linked list of points. Each point is held by a struct

struct Point{
    Point *next;
    double x, y, alY;
};

The linked list of these points is called class Points. class Points starts with one struct Point stored as Point *first. The next point on the list is given by first->next, and so forth. It ends when the Point *next is NULL.

The class Points also have some statistcal regression features, making it too large to post in full. None of these features modify the basic backbone.

Everything described so far works, and has worked for a long time. All of this code is good.

The problem came in when I figured, "Hey, it'd be fun to try out overloaded operators to extend the program." So I started with an assignment operator. There's no copy operator nor any other overloaded operator. But it's not working as intended.

As an example, I have a simple program:

#include "RegressionHeader.h"

void main(){
    Points *aList = OpenPointsFile("C:\\Users\\Username\\Desktop\\testfile.txt"), *bList = new Points();

    aList->Print();     //Works
    *bList = *aList;
    bList->Print();     //Crashes	

    cin.ignore();
    return;
}

I think that my assignment operator is bad. Here it is:

Points Points::operator= (const Points &inc){
    Points *tempPoints = new Points;
    Point *current = inc.first;
    tempPoints->length = 0;
    while(current){
        tempPoints->addPoint(current->x, current->y);
        cout << "Copying (" << current->x << "," << current->y << ") to " << tempPoints->last << "\n";
        current = current->next;
    }
    tempPoints->Print();  //Works
    return *tempPoints;
}

The ->Print() command works in the main program for *aList. It also works in the assignment operator for *tempPoints. However, it crashes for *bList.

Why?

For reference, this is the addPoint function (which I know to work):

void addPoint(double x, double y){
    if (length){
        last->next = new Point();
        last = last->next;
    } else {
        first = new Point();
        last = first;
    }
    last->x = x;
    last->y = y;
    last->next = NULL;
    length++;
    recalc = true;
}

Ultimately what confuses me the most is that in the assignment operator, tempPoints->Print() works. Then I return tempPoints to bList, but bList->Print() doesn't work.

[Disch]

(main should always return int! not void!)

You're assignment operator looks like it's assigning a 'tempPoints' variable and then returning it, which is nonsensical. I think you're thinking that the value you return becomes 'this', but that is not the case. The assignment operator should be assigning 'this'.

You then typically return a reference to (not a copy of!) 'this'. The only thing this does is it makes assignments stackable. IE: a = b = c;

Your assignment operator should probably look something like this:

Points& Points::operator= (const Points &inc){  // returns a reference, not a copy
//    Points *tempPoints = new Points;  // no need for tempPoints, get rid of that
    Point *current = inc.first;
//    tempPoints->length = 0;  // don't modify tempPoints, instead... modify this:
    length = 0;

    while(current){
//        tempPoints->addPoint(current->x, current->y);  // again....
        addPoint(current->x,current->y);

        cout << "Copying (" << current->x << "," << current->y << ") to " << tempPoints->last << "\n";
        current = current->next;
    }
//    tempPoints->Print();  // again...
    Print();

//    return *tempPoints;  // and one more time...
    return *this;
}

And of course printing in the assignment operator kind of makes sense for debug purposes, but you wouldn't want that in a completed program.


EDIT:

Also note that you'll have a memory leak if you assign a list after it has any elements. For example:

Points a;
a.addPoint(0,0);  // point 0,0

Point b;
b.addPoint(1,1);

a = b;  // point 0,0 is lost, but memory for it was never freed!  Memory leak! 

To correct this, you should delete all points in the original list when assigning:

Points& Points::operator= (const Points &inc)
{
    DeleteAllPoints();

    // ... then proceed with = operator as normal
}

[moorecm]

Why not add assignment and copy construction to the Point class? The compiler generated one is not sufficient, so it's up to you to never copy or take one by value. That seems like a mistake waiting to happen. This will also simplify the implementation of the Points class.

[Disch]

Also I figured he was doing this as an acedemic exercise....

but why have a Points class at all? Why not just use std::list<Point>? And make Point an actual point (just x and y), instead of a node (with a pointer)

[Chemical Engineer]

The exercise is quasi-academic. I'm both using the programs that I make and learning from making them. They're practical because, well, they do what would take a long time to do by hand. Automation's awesome at work.

However, Disch is very much right about it being academic. This is pretty much my second program; I'm still in the "Hello world" phase of my programming education. At this point, efficiency isn't as important as learning.

This said, I do appreciate the suggestions on how I could have improved efficiency since they contribute to that learning.

[Chemical Engineer]

Disch,

I made the modifications that you suggested. It got a little further but still crashed on the bList->Print(); line.

That line is supposed to give the output:

Points:
(1,1) at [some address];
(2,4) at [some address];
(3,9) at [some address];
(4,16) at [some address];
(5,25) at [some address];
(6,3600) at [some address];

And the aList->Print(); and the Print(); inside of the assignment both gave that, as before. Previously, it on bList->Print();, it'd give this:

Points:
//crashes 

Now it's giving:

Points:
(-2.65698e+303,-2.65698e+303) at [some address]
//crashes 

.

I'm thrilled that the address for the nonsense value matches the address for the first value in the assignment operator, meaning that it's now passed the linked list's first node's address properly. What doesn't make sense is why it claims that that address contains a nonsense value instead of (1,1).

EDIT: The deconstructor for the class deletes all of the points in its linked list. Does the this object get deleted when it's returned? If so, maybe ~Points() is deleting all of the points, causing the bug.

[Chemical Engineer]

Woot! It works! The deconstructor was destroying the list, so I moved that code to a void Delete function instead.

Thanks guys.

[Disch]

I'm worried. I suspect your "fix" isn't really a fix.

EDIT: The deconstructor for the class deletes all of the points in its linked list.

That is what it should do.

Does the this object get deleted when it's returned? If so, maybe ~Points() is deleting all of the points, causing the bug.

No. 'this' is the object you're assigning. So if you have a = b;, inside the assignment operator, 'this' would be &a. It is not deleted unless 'a' is deleted.

What you're PROBABLY doing is copying the object, then the copy is getting destructed. And since you don't have a proper copy constructor, that is causing the point data to be deleted when 'a' is still using it.

Did you make this change?

Points& Points::operator= (const Points &inc)

Note it returns Points& not Points. That is very important!

[Chemical Engineer]

I just tried that change. It crashes when I have the code in the destructor uncommented. It works when the destructor is effectively empty.

Sadly, I thought that things were working properly, so I've already moved on and editted the code pretty severely. Working through a new issue now: making sure that the temporary copies in a chain addition operation are properly destructed. Also avoiding the destruction of temporary copies and reusing the struct Points inside of them so that I can avoid deleting the temporary struct Points only to remake them.

Once I'm done figuring out the bugs in the new code, I'll post it to ask if it's sensible. Or come asking for help again if I can't work out the bugs.

PS- Working through this, I get the feeling that I don't really understand how temporary objects are being created and destroyed behind the scenes. My code's throwing errors due to some automatic deletion that I'm having trouble pinning down.

PPS- Code works now. I'll post it in a sec. (It's on another computer.)

[Chemical Engineer]

It now has addition overloaded operators. I added in a bool temporary to keep track of whether or not a copy in a chain operation (i.e., *c = *a + *b + *c) is non-temporary (i.e., *a, *b, or *c) or a temporary made while combining (i.e., *b + *c).

The code appears to be working as intended. Is this sensible?

The full code:

main.cpp:

#include "RegressionHeader.h"

int main(){
    Points *aList = OpenPointsFile("C:\\testfile.txt"), *bList = new Points();
    cout << "aList:" << endl;
    aList->Print();

    cout << endl;

    *bList = *aList + *aList;

    cout << "bList:" << endl;
    bList->Print();

    aList->Delete();  //destructor won't auto-delete because it's not temporary
    bList->Delete();  //destructor won't auto-delete because it's not temporary
    
    Pause();
    return 0;
}

RegressionHeader.h:

#include <iostream>
#include <fstream>

using namespace std;

//Prototypes
struct Point;

//Functions
void Pause(){
    cin.ignore();
};

struct Point{
    Point *next;
    double x, y, alY;
    Point(){}
    Point(double incX, double incY){
        x = incX;
        y = incY;
    }

};

class Points{
    double slope, intercept, coefficient;
    Point *first, *last;
    long length;
    bool recalc, temporary;

    void InternalRegress(){
        Point *considered = first;
        double toX = 0, toY = 0, toXY = 0, toXS = 0, SSerr = 0, SStot = 0, avY;
    
        while(considered){
            toX += considered->x;
            toY += considered->y;
            toXY += considered->x * considered->y;
            toXS += considered->x * considered->x;
            considered = considered->next;
        }

        slope = (toXY - (toX * toY / length)) / (toXS - (toX * toX) / length);
        intercept = (toY - slope * toX) / length;
        avY = toY / (double)length;

        considered = first;
        while(considered){
            SSerr += (considered->y - (slope * considered->x + intercept)) * (considered->y - (slope * considered->x + intercept));
            SStot += (considered->y - avY) * (considered->y - avY);
            considered = considered->next;
        }
        coefficient = 1 - (SSerr / SStot);

        recalc = false;
        return;
    }

public:
    Points(){
        length = 0;
        temporary = false;
    }

    ~Points(){if(temporary) {Delete();}}

    void Delete(){
        Point *current = first, *next;
        
        while(current){
            next = current->next;
            delete current;
            current = next;
        } 
        length = 0;      //Incase pointer is reused after deletion, this line will help to minimize damage.
        recalc = true;   //Incase pointer is reused after deletion, this line will help to minimize damage.
        delete this;
    }

    Points &Points::operator= (const Points &inc){
        cout << "Assigning..\n";
        Point *current = inc.first;
        length = 0;
        while(current){
            addPoint(current->x, current->y);
            //cout << "Copying (" << current->x << "," << current->y << ") to " << last << "\n";
            current = current->next;
        }
        slope = inc.slope;
        intercept = inc.intercept;
        recalc = inc.recalc;
        coefficient = inc.coefficient;
        temporary = false;
        return *this;
    }

    Points &Points::operator+ (const Points &inc){
        cout << "Adding..\n";
        Point *current = inc.first;
        
        if(temporary){
            while(current){
                addPoint(current->x, current->y);
                //cout << "Adding (" << current->x << "," << current->y << ") at " << last << "\n";
                current = current->next;
            }
            recalc = true;
            return *this;
        } else {
            Points *temp = new Points();
            *temp = *this;
            while(current){
                temp->addPoint(current->x, current->y);
                //cout << "Adding (" << current->x << "," << current->y << ") at " << last << "\n";
                current = current->next;
            }
            temp->recalc = true;
            temp->temporary = true;
            return *temp;
        }
    }

    Points &Points::operator+ (const Point &inc){
        cout << "Adding..\n";
        if(temporary){
            addPoint(inc.x, inc.y);
            //cout << "Adding (" << inc.x << "," << inc.y << ") at " << last << "\n";
            recalc = true;
            return *this;
        } else {
            Points *temp = new Points();
            *temp = *this;
            temp->addPoint(inc.x, inc.y);
            //cout << "Adding (" << inc.x << "," << inc.y << ") at " << last << "\n";
            temp->recalc = true;
            temporary = true;
            return *temp;
        }
    }

    void addPoint(double x, double y){
        if (length){
            last->next = new Point();
            last = last->next;
        } else {
            first = new Point();
            last = first;
        }
        last->x = x;
        last->y = y;
        last->next = NULL;
        length++;
        recalc = true;
    }

    long getLength(){return length;}
    Point *getFirst(){return first;}

    double getSlope(){
        if(length < 2){
            cout << "Error:  Regressions must have more than two points." << endl;
            return 0;
        }
        if(recalc){
            InternalRegress();
        }
        return slope;
    }

    double getIntercept(){
        if(length < 2){
            cout << "Error:  Regressions must have more than two points." << endl;
            return 0;
        }
        if (recalc){
            InternalRegress();
        }
        return intercept;
    }
    
    double getCoefficient(){
        if (recalc){
            if(length < 2){
                cout << "Error:  Regressions must have more than two points." << endl;
                return 0;
            }
            InternalRegress();
        }
        return coefficient;
    }
    void Print(){
        Point *considered = first;
        cout << "Points: \n";
        while(considered){
            cout << "(" << considered->x << "," << considered->y << ") at " << considered << ";" << endl;
            considered = considered->next;
        }
        if(this->getIntercept() < 0){
            cout << "y = " << this->getSlope() << "x - " << abs(this->getIntercept()) << "  (R^2 = " << this->getCoefficient() << ").\n";
        } else {
            cout << "y = " << this->getSlope() << "x + " << this->getIntercept() << "  (R^2 = " << this->getCoefficient() << ").\n";
        }
        return;
    }
};

Points *OpenPointsFile (char fileName[150]){
    double xValue, yValue;
    Points *tempPoints = new Points;
    ifstream in(fileName);
    
    while(in >> xValue){
        in >> yValue;
        //cout << "Adding point (" << xValue << ","  << yValue << ")" << endl;
        tempPoints->addPoint(xValue, yValue);
    }
    in.close();
    return tempPoints;
};

C:\testfile.txt:

1    1
2    4
3    9
4    16
5    25
60   3600

[Chemical Engineer]

Okay, after some playing with it, this is what it seems like to me:

-Using bool temporary allows the code to reuse already-made temporary objects when possible and creates new objects when needed. This is a good optimization strategy.
-Using the reference return type avoids creating redundant temporary objects. This is also a good optimization strategy.

Mostly, I added in some std::cout statements into the various if branches to see when temporary methods were and weren't being used in an operation
*b = *a + *a + *a + *a;

Good stuff?

PS- Oh, I realize that leak you mentioned earlier, when the assignment goes off. I added a void Clear() function that's just like void Delete(), only without delete this;, and I put a call to it at the top of the assignment operator's block.

void Delete(){
    Clear();
    delete this;
    return;
}

now replaces the old void Delete().

[Disch]

delete this

no no no no.

Don't do that!

no no no no.

I'll look over this more and give a more thorough critique after work.

[Disch]

Okay you have quite a few problems here that I noticed right off the bat:

1) Your + operator is behaving like a += operator. Consider the following code:

int a = 5, b = 2;
int c = a + b;

cout << a; // you expect this to output 5 

You expect output to be 5 because you set 'a' to 5. Logically, the + operator should not change a.

Your + operator changes 'this' and thus if you do something like this:

Points a, b;
// init a and b here

Points c = a + b;  // surprise!  this line will change a! 

2) Your delete this bit is fundamentally flawed for a few reasons. It's a very specific design pattern for objects to "commit suicide", one which you're not really doing. wxWidgets does it, but in that context it makes sense only because the objects that commit suicide own themselves. Here, ownership of your Points does not belong to the Points class, and therefore suicide is ill advised.

Not to mention, even when you suicide, you should never suicide in the destructor.

Think about it... let's say I do the following:

Lists a = new Lists;
a->Delete();

Here's what happens:
- a->Delete() does delete this
- delete calls the dtor
- the dtor calls Delete()
- Delete() does delete this again
- delete calls the dtor again
- the dtor calls Delete() again
- etc
- etc

Nevermind the fact that it's an infinite loop, but you're also deleting the same buffer multiple times which is terrible.

3) I didn't look closely at your 'temporary' trick, but it sounds like a bad idea. It sounds like it's pseudo-reference counting. Honestly, since you're still struggling with proper encapsulation and memory management, I really recommend you avoid such minor optimization attempts. Get it working first.

Maybe if you're not happy with the performance later you can go back and optimize it. But you're biting off more than you can chew.

Besides... the best way to optimize away expensive copies is to not make unnecessary copies of objects.

(Actually on closer look your 'temporary' trick opens tons of memory leaks by allocating objects with new and never deleting them. Not to mention it gives you tons of duplicated code)

4) You also have some const correctness issues, but that's very minor.



Anyway -- basically you're doing too much. You need to focus on how memory is managed.

Here's some guidelines:

a) Define a rigid model to specify how much memory is allocated and when. In your case this can be very simple. All you really have is that 'first' pointer... so you can say that if 'first' is null, then nothing is allocated... and if 'first' is non-null, then memory is allocated.

b) Minimize the number of functions that allocate/free memory. If you have multiple ways to add new nodes (like with the + operator) try to write one common functions that adds nodes and have your + operator call it. Don't add the nodes directly in every single function. The fewer places you do it, the fewer chances there are to screw up.

c) Clearly define who owns what and allocate/free memory accordingly. Simply put... whoever allocates the memory is in charge of freeing it. Logically, Points should own the list of points pointed to by the 'first' pointer. Therefore Points (and no one else) should be responsible for allocating the points. And Points (and no one else) should free those points when it's done with them.

Points does not own instances of itself, and therefore it should not be attempting to delete instances of itself. This is wrong on so many levels.



I don't know how much that helps.

Here's an example of how I would do it (note this isn't perfect as it's not exception safe, but making it exception safe would make it more complicated. One step at a time...):

class Points
{
public:
  // the default ctor.  zeros out the pointer and size members
  //  so it is clear that nothing is allocated
  Points()
    : first(0), length(0)
  {}

  // the copy ctor.  Copies data from another Points object
  Points(const Points& p)
    : first(0), length(0)   // do this to indicate no memory is allocated (yet)
  {
    Copy(p);  // note:  let 'Copy' do all the work
  }

  // the assignment operator
  Points& operator = (const Points& p)
  {
    Copy(p);  // copy the points from p
    return *this;
  }

/*
   Note that both the copy ctor and assignment operator call the same 'Copy' function.
   This lets us avoid duplicate code, since they both basically do the same task, just in slightly different ways.
*/

  ~Points()
  {
    Clear();  // clear out all existing points (freeing memory)
    // that's all you have to do here
  }

/*
  Notice with the above design, we have a fully functional copy ctor, assignment operator, default ctor, and dtor.
  And ZERO memory management code.  It's all very simple, right?

  Everything is taken care of by Clear and Copy.  This is what I meant by my point 'b' above.  Keep the memory management
  code in all the same place.  Minimize the number of functions that mess with that stuff.
*/

  void Clear()
  {
    // step through the nodes and delete all of them
    // then reset 'first' and 'length' to zero to indicate that no memory is allocated
    //  (remember point 'a' above.  Stick with your defined terms)
  }

  void Copy(const Points& p)
  {
    Clear();  // clear the existing points (if any)

    // then copy all the points from p
  }
};

It's really that simple.


Anyway I'm about out of steam... and this is a pretty length post. If you read it all and still have questions, lemme know.