Problems with overloading operator+ in C++

niteshadw · 07-19-2005, 08:35 PM

I'm trying to overload addition operator where it also sorts the two added things as it adds.

Code:

class PhoneBookEntry{
private:

public:
	string name, number;

	PhoneBookEntry(){};
};

class PhoneBook{
private:
	int size, elements;
	PhoneBookEntry* phoneEntry;

public:
	PhoneBook(): phoneEntry(new PhoneBookEntry[elements]), size(0), elements(1){}
	PhoneBook(const PhoneBook&);
	PhoneBook& operator =(const PhoneBook&);
	~PhoneBook() {delete [] phoneEntry;}

	void insert(string, string);
	void expandArray();
		
	PhoneBook operator +(const PhoneBook&) const;
	PhoneBook operator -(const PhoneBook&) const;
	PhoneBookEntry& operator [](int i) {return phoneEntry[i];}
	friend ostream& operator <<(ostream&, const PhoneBook&);
};
PhoneBook& PhoneBook::operator =(const PhoneBook& rhs){
		
	if (this != &rhs){
		delete [] phoneEntry;	
		phoneEntry = new PhoneBookEntry[rhs.size];
		for (int i = 0; i < rhs.size; i++)
			phoneEntry[i] = rhs.phoneEntry[i];
		size = rhs.size;
	}
	return *this;

} //operator =

////////////////////////////////////////////////////////////////////////////////////

PhoneBook::PhoneBook(const PhoneBook& rhs){
	phoneEntry = NULL;
	*this=rhs;

} //PhoneBook()

////////////////////////////////////////////////////////////////////////////////////

PhoneBook PhoneBook::operator +(const PhoneBook& rhs) const{

	PhoneBook temp;
	temp.size = size + rhs.size;

	int i(0), j(0), k(0);
	for(; i < size && j < rhs.size; k++){
		if(phoneEntry[i].name < rhs.phoneEntry[j].name){
			temp.phoneEntry[k] = phoneEntry[i++];
		} else {
			temp.phoneEntry[k] = rhs.phoneEntry[j++];
		} //if-else
	} //for

	for(; i < size; i++, k++){
		temp.phoneEntry[k] = phoneEntry[i];
	} //for

	for(; j < rhs.size; j++, k++){
		temp.phoneEntry[k] = rhs.phoneEntry[j];
	} //for

	temp.size = size + rhs.size;
	return temp;

} //operator+

int main(){

	PhoneBook x,y,z;
	x.insert("John Doe", "718-260-3657");
	x.insert("Doe", "718-260-3620");
	y.insert("John Doe", "");
	z = x + y;
	
	cout << z; (its overloaded)
}

There is something wrong with the code I have, it crashes..I've tired debugging and I see that the elements from the x and y are not being inserted into the z, I think...does anyone see the problem?? I'm still quite new to C++ so I'm just trying to learn...so things I do here may not be the best but it works..well minus the addition...

How would I be able to do the subtraction...should it make the array smaller each time an item is removed or after all of the items are removed then just shift everything down...would anyone be able to show a quick code..

Any help would be appreciated...thank you

enemorales · 07-20-2005, 12:58 AM

After a quick look: Is this working? What's the value of "elements" when you create the new PhoneBookEntry??

Code:

PhoneBook(): phoneEntry(new PhoneBookEntry[elements]), size(0), elements(1){}

and then here:

Code:

for(; i < size; i++, k++){
	temp.phoneEntry[k] = phoneEntry[i];
} //for

for(; j < rhs.size; j++, k++){
	temp.phoneEntry[k] = rhs.phoneEntry[j];
} //for

what are the values of i and j then you enter the for-loops?

I think you can achieve all this with only one, simple, loop:

Code:

for(i=0;i<temp.size;++i) {
  if(i<size) {
    temp.phoneEntry[i] = phoneEntry[i];
  } else {
    temp.phoneEntry[i] = rhs.phoneEntry[i-size];
  }
}

HTH

ta0kira · 07-20-2005, 01:38 AM

Quote:

After a quick look: Is this working? What's the value of "elements" when you create the new PhoneBookEntry??

Code:

PhoneBook(): phoneEntry(new PhoneBookEntry[elements]), size(0), elements(1){}

Good call. elements needs to be initialized before phoneEntry, otherwise phoneEntry will be of a random size. new doesn't respond well to negative or extremely large numbers which are > 50% likely in this case.

On a side note, it looks like you're using a merge sort algorithm in operator + (or a significant segment of one). In this case your 2 sections are already sorted and you are merging them into temp. I like how that's done.

Quote:

what are the values of i and j then you enter the for-loops?

I think i and j are the reference points on either array since they don't remain parallel; the element with the lesser name is added to temp and that index is incremented. When one list runs out, the remainder of the other list is just added into the output list starting at the current index for that list. That serves to combine and sort the data all at once.

You could streamline the first loop a little though:

Code:

	while (i < size && j < rhs.size) temp.phoneEntry[k++] = 
	                                 (phoneEntry[i].name < rhs.phoneEntry[j].name)? 
	                                 phoneEntry[i++] : rhs.phoneEntry[j++];

You can save a lot of debugging time if you use std::list or std::vector instead of doing your own new[] and delete[]. I admit it took me about a year to give in and use the stl for that type stuff, but for array management I think it's the way to go.
http://www.sgi.com/tech/stl/table_of_contents.html

Can you show the insert function? Do you delete[], new[], and copy when the size of the list changes? Try the elements thing we suggested, and if that doesn't work, post the insert code. Thanks.
ta0kira

PS Please disable the smilies so that they don't show up in your code. Thanks.

elyk1212 · 07-20-2005, 02:18 AM

First off, that elements variable is garbage (never initialized) so it may have any value for the length of the phonebook entries array (as our friend mentioned). That is a REALLY bad thing as any value could be placed in there (including ZERO!!!) and your compiler may not even catch this.
I think you should consider changing the data when adding entries to a 'Phonebook' and grow the array appropriately based on the combined size. I see you have a method listed to do this, but no definition. THIS IS VERY IMPORTANT SINCE YOUR ADD METHOD MAY ADD PAST THE ALLOCATED SPACE FOR PhoneBookEntry. YOU MUST MALLOC MORE SPACE! IF YOU DO NOT YOU *CAN* WRITE TO INVALID MEMORY SPACE CAUSING AN EXCEPTION. Data structure books are a lot of help on this stuff.

Also, making data public *could* be a bad idea. This is like a global variable. You might use accessor methods, that way you can check to make sure the data is valid (e.g. not zero length strings, make sure a phone_number really contains only numbers and dashes, etc). If this detection is not important, I guess it is not really a big issue. But this obviates the need for a class and data hiding (could just use struct).

Anyhow here is some sample code (it assumes public members):

Code:

//**************************************************
/*
*   Used to add phonebooks together to form a larger
* phonebook containing combined entries.
*     @param rhs PhoneBook to add to this phonebook.
*     @returns new PhoneBook with entries from
*     this phonebook as well as from rhs
*/
PhoneBook* PhoneBook::operator +(const PhoneBook& rhs) const
{

   //  Allocate a new PhonebookEntry data array based on the size
   // of both phonebooks
   int new_size = rhs.size + this.size;
   PhonebookEntry book_to_add = rhs.phoneEntry;
   PhoneBookEntry* temp = (PhonBookEntry*)malloc(new_size);

   //   Transfer all Phonebook#1 entry data and all
   //   PhoneBook#2 entry data to a temp PhoneBookEntry pointer

   //  Total entries placed in array, so far
   int total = 0;
   // Index into this PhoneBooks entries
   int i = 0;
   // Index into rhs PhoneBook entries
   int a = 0;

   while(total < new_size)
   {
      // Entry from this PhoneBook
      PhoneBookEntry* entry1 = NULL;
      // Entry from rhs PhoneBook
      PhoneBookEntry* entry2 = NULL;

      if(i < this.size)
      {
         entry1 = (this.phoneEntry + i);
         i++;
      }
      if(a < rhs.size)
      {
         entry2 = (rhs.phoneEntry + a);
         a++
      }

      // If both Books still have entries left to compare,
      //  Do this and sort.
      if(entry1 != NULL && entry2 != NULL)
      {
         // If entry1 comes before entry2, add it
         if(entry1 < entry2)
         {
            (temp + total)->name = (entry1 + (i-1))->name;
            (temp + total)->number = (entry1 + (i-1))->number;
         }
         // If not entry2 is either greater or equal to entry1
         //   Add it (order does not matter on 'equal entries).
         else
         {
            (temp + total)->name = (entry2 + (a-1))->name;
            (temp + total)->number = (entry2 + (a-1))->number;
         }
      }
      // If only this Book still has entries
      else if(entry1 != NULL)
      {
         (temp + total)->name = (entry1 + (i-1))->name;
         (temp + total)->number = (entry1 + (i-1))->number;
      }
      // If only rhs still has entries.
      else if(entry2 != NULL)
      {
         (temp + total)->name = (entry2 + (a-1))->name;
         (temp + total)->number = (entry2 + (a-1))->number;
      }

      total++;
   }
   PhoneBook to_return;
   to_return.phoneEntry = temp;
   to_return.size = new_size;

   // Return the new added PhoneBook!
   return to_return;
}
//**************************************************

Please bear with me for syntax errors as I did not compile. But you get the picture with this conceptual solution.

Code assumes NULL is defined and that the < operator is overloaded in the PhoneEntries class (which it is not, yet). I suggest doing so because as far as my string implementations I have linked against, none can compare the entire string with just the < operator. But you may have such a library. It is correct to not assume others do, howerver and I suggest implementing a compare algorithm for your PhoneBook entry class.

This is simply done by comparing each character in each string (of the name field, I assume).

Code:

// NOT CODE, algorithm

LOOP START
{
  get nth char of string1;
  get nth char of string2;

  if(string1 char is null and string2 char is null)
  {
     string1 and string2 are equal!;
  }
  if(string1 char is null)
  {
       string1 is first;
  }
  else if(string2 char is null)
  {
      string 2 is first;
  }
  else
  {
     (compare nth char of string1 to nth char of string2)
      if (string1 char < string2 char)
      {
           string1 is first;
      }
     else if(string1 char > string2 char)
     {
          string2 is first
     }
    increment n;  // Of course :)
 }

Convention is returning -1 for less than, 1 for greater than, 0 for equal. Assumes string class is null terminated. Have fun!

ta0kira · 07-20-2005, 03:14 AM

I don't think returning dynamic objects is appropriate in this case. I think the way operator + is written is just fine for OP's purpose (except 1 line; see below a little). As far as resizing phoneEntry; that is a good observation about needing to resize phoneEntry in temp, however this should be executed from temp. I'd suggest adding an unsigned int argument to the default constructor:

Code:

	PhoneBook(unsigned int sSize = 1): elements(sSize), size(0),
	                                   phoneEntry(elements? new PhoneBookEntry[elements] : NULL) {}

Also, you should make both elements and size unsigned int to prevent negative values.

Then in operator + you would do this:

Code:

	PhoneBook temp;

//-->

	PhoneBook temp(size + rhs.size);

That will make sure temp is large enough for both of the lists.

So; you really only need to do 4 small things (aside from individual style preferences) to make your code work (from what I see anyway):

1) make sure elements comes before phoneEntry in the initialization list
2) add an argument to your constructor that tells what size it should be to start with
3) make your size and elements variables unsigned
4) add a constructor argument when creating temp

On another note; I would make the following change (in operator =), even though it probably won't cause errors in this case:

Code:

		phoneEntry = new PhoneBookEntry[rhs.size];

//-->

		phoneEntry = new PhoneBookEntry[rhs.elements];

ta0kira

elyk1212 · 07-20-2005, 03:56 AM

Just a friendly reminder that 'new' is a dynamic allocated object, just the same as malloc. malloc is the 'C' style, 'new' the C++ style. The same side effects and object scope apply.

Also, for large object data, may I suggest perhaps it is more appropriate to return a pointer to the object instead of the actual object (the stack could get HUGE for large PhoneBooks), in the worst case. Just a thought. Also a correction/note to add to my example code....

This code assumes that if 2 entries have the same name, they are the same entry!!! This may not be appropriate for your class. You may need to add both entries and change the indexes to suite your needs.

Code:

 // If not entry2 is either greater or equal to entry1
         //   Add it (order does not matter on 'equal entries).
         else
         {
            (temp + total)->name = (entry2 + (a-1))->name;
            (temp + total)->number = (entry2 + (a-1))->number;
         }

ta0kira · 07-20-2005, 04:49 AM

Quote:

Just a friendly reminder that 'new' is a dynamic allocated object, just the same as malloc. malloc is the 'C' style, 'new' the C++ style. The same side effects and object scope apply.

Yes, I was pointing out that your operator + returned a dynamic pointer, but OP is using the result as an assignment operator argument.

I'll stick to my argument that the content of OP's operator + is suitable for his/her purpose. I think there's been some misunderstanding as to what's going on in the function. Please see my first post.
ta0kira

niteshadw · 07-20-2005, 12:40 PM

Well elements is initialized to 1, it allows me to know when the current array is full, so when size = elements, then I call the resize function and elements is increased...anyhow, here is a little refined code which also crashes...

Code:

PhoneBook PhoneBook::operator +(const PhoneBook& rhs) const{

	//PhoneBookEntry* temp = new PhoneBookEntry[size + rhs.size];
	PhoneBook temp;
	temp.size = size + rhs.size;

     int indexA(0), indexB(0), indexC(0);	// initialize the Array Indices

	 while((indexA < size) && (indexB < rhs.size)){
		 if(temp.phoneEntry[indexA].name < rhs.phoneEntry[indexB].name){
			 temp.phoneEntry[indexC] = phoneEntry[indexA];
			 indexA++;    //increase the index
		 } //if
         else{
			 temp.phoneEntry[indexC] = rhs.phoneEntry[indexB];
             indexB++;      //increase the index
         } //else

        indexC++;      //move to the next position in the new array
     } //while

     // Push remaining elements to end of new array when 1 feeder array is empty
     while(indexA < size){
		 temp.phoneEntry[indexC] = phoneEntry[indexA];
         indexA++;
         indexC++;
	 } //while

     while(indexB < rhs.size){
		 temp.phoneEntry[indexC] = rhs.phoneEntry[indexB];
         indexB++;
         indexC++;
	 }
	 
	 return temp;

} //operator+

Here is the debug info that I'm watching:

Code:

phoneEntry[indexA].name	{0x00321288 "John Doe"}	std::basic_string<char,std::char_traits<char>,std::allocator<char> >
rhs.phoneEntry[indexB].name	{0x00321160 "John Doe"}	std::basic_string<char,std::char_traits<char>,std::allocator<char> >
	size	2	int
	rhs.size	1	int
	temp.size	3	int
temp.phoneEntry[0].name	{0x003210e8 "Doe"}	std::basic_string<char,std::char_traits<char>,std::allocator<char> >
temp.phoneEntry[1].name	{0x00321120 "��������"}	std::basic_string<char,std::char_traits<char>,std::allocator<char> >
temp.phoneEntry[2].name	{0x00321158 ""}	std::basic_string<char,std::char_traits<char>,std::allocator<char> >
	indexA	1	int
	indexB	0	int
	indexC	1	int

and when the debugger this the middle line (temp.phoneEntry...) of:

Code:

         else{
			 temp.phoneEntry[indexC] = rhs.phoneEntry[indexB];
             indexB++;      //increase the index

it goes to 'isofwd' and to the code:
[code]
static int __cdecl compare(const _Elem *_First1, const _Elem *_First2,
size_t _Count)
{ // compare [_First1, _First1 + _Count) with [_First2, ...)
return (::memcmp(_First1, _First2, _Count));
}
[code]

So, as you see it inserts the entry with the smaller letter but then when its about to add the other entry, it just cashes and I don't understand the reason for it...does anyone see the problem with this code? I appreciate other suggestions but I would like to be able to find the error in the code I have...thank you once again...

elyk1212 · 07-20-2005, 12:58 PM

[RESPONDING TO POST BEFORE LAST]
Yes, it looks like the logic *looks* correct on the + operator. I just thought the usage of the for loops was a little unconventional what with all the 3 indexed variables, all with different control logic. That's a little difficult to read (if I turned that in to my engineering professor, I'd have to rewrite and consolidate). Not to mention difficult for someone else to debug (if not the author). Sorry if it sounded like I was being picky. I guess after being graded 100+ times on such things, I develop a need to consolidate and make the code more conventional (to most). As they tell our peers: "Just because it 'works', it does not mean it is well written code... Readability and style are factors...[comments too!]". But that is subjective anyhow

. I have no need to enforce a certain style on anyone else, and I am sorry if it seemed this way.

Also, is the '<' operator overloaded for strings?! I am not sure if it is, but the code assumes so. I do not remember seeing this in C++'s standard string library. I could be 100% wrong though.. not sure. I just know every time I have done a comparison, I needed to write the algorithm myself, char for char.

As for the stack thing I mentioned, it won't be a problem for 'smaller' PhoneBooks. I am just considering the "worst case". To each their own, I appreciate the feedback.

niteshadw · 07-20-2005, 01:09 PM

nevermind, I got it

elyk1212 · 07-20-2005, 01:16 PM

Hi again,
I think I know...

Here is the problem:

Code:

PhoneBook temp;
temp.size = size + rhs.size;

Are you really sure there is enough elements space for the temp PhoneBookElements array? No, you cannot be since elements is set to is default size with the default constructor (try writting another constructor PhoneBook::PhoneBook(int element_size), etc so you can set this yourself (if not already done). Since you are setting the size integer to some other value, it may be larger than the default size you allocated for the array elements. (In this case it is ONLY ONE!, as you mentioned). So you are indexing past the array bounds. A VERY common error.

niteshadw · 07-20-2005, 04:32 PM

Quote:

Originally posted by elyk1212
[RESPONDING TO POST BEFORE LAST]
Yes, it looks like the logic *looks* correct on the + operator. I just thought the usage of the for loops was a little unconventional what with all the 3 indexed variables, all with different control logic. That's a little difficult to read (if I turned that in to my engineering professor, I'd have to rewrite and consolidate). Not to mention difficult for someone else to debug (if not the author). Sorry if it sounded like I was being picky. I guess after being graded 100+ times on such things, I develop a need to consolidate and make the code more conventional (to most). As they tell our peers: "Just because it 'works', it does not mean it is well written code... Readability and style are factors...[comments too!]". But that is subjective anyhow . I have no need to enforce a certain style on anyone else, and I am sorry if it seemed this way.

Also, is the '<' operator overloaded for strings?! I am not sure if it is, but the code assumes so. I do not remember seeing this in C++'s standard string library. I could be 100% wrong though.. not sure. I just know every time I have done a comparison, I needed to write the algorithm myself, char for char.

As for the stack thing I mentioned, it won't be a problem for 'smaller' PhoneBooks. I am just considering the "worst case". To each their own, I appreciate the feedback.

Yes, I totally agree, good thing I'm not a CS major and I know how picky the professors are because I had to take a few classes in C++...I got used to the style, then the next class a different professor wants the samething but totally a different way so...well can't pealse everyone...I just want to make this code work at the moment and then I'll worry about make it clear and easy to read..as long as it will work then I will try to make it as effictient as best as I know how to...this is just for practice and I don't really plan to make programming into my career...heh...oh and the < operator is not overloaded, it appears to be able to compare the strings...I would have to overload it if I were compaint the whole class...but since its just the string, it appears to work

elyk1212, yes that's what was wrong...so I just deleted the second line and made a the temp a dynamic for time being...thanks for catching it though =)

Now, I have to do the samething but for the -, any suggestions on how to make do it the easiest way? Thanks for everything!

elyk1212 · 07-20-2005, 07:23 PM

That is going to be a pain, but not too bad

. You will have to find every element NOT in PhoneBook you are subtracting and make a new PhoneElements array with just the ones left over. If none are found that match the records you are subtracting, it will do nothing (but naturally, and do not make this a special case).

Also, I think your '<' operator may only be comparing pointers for those string objects... not really sure though, it all depends on the 'default' usage of that operator. You better verify that string in fact implements this operator to do what you think it does. C++ can do interesting things when you are not explicit and it is hard to say what this operator is doing if it is not overloaded.

A good example is, logical operators evaluate to true if there is an integer other than 0 as an argument. That might be unexpected.. .so for instance this would evaluate true, even if it were a boolean *kind of* object, with a false value:

Code:

Pointer* some_pointer = &some_object;
if(some_pointer)
{
   cout << "It was True!";
}

But I am sure you probably have ran into such things.

Or how about?:

Code:

Pointer* some_pointer = &some_object;
Pointer* some_pointer2 = &some_second_object;
if(some_pointer < some_pointer2)
{
   cout << "It was True!";
}

Do we really know what this will do? You architecture/OS nuts can probably know your system well enough to know what pointer values are picked from the heap, but this is not a clear outcome and *may* have unexpected results.

niteshadw · 07-20-2005, 07:45 PM

Quote:

Originally posted by elyk1212
That is going to be a pain, but not too bad . You will have to find every element NOT in PhoneBook you are subtracting and make a new PhoneElements array with just the ones left over. If none are found that match the records you are subtracting, it will do nothing (but naturally, and do not make this a special case).

Also, I think your '<' operator may only be comparing pointers for those string objects... not really sure though, it all depends on the 'default' usage of that operator. You better verify that string infact implements this operator to do what you think it does. C++ can do intersting things when you are not explicit and it is hard to say what this operater is doing if it is not overloaded.

A good example is, logical operators evaluate to true if there is an integer other than 0 as an argument. That might be unexpected.. .so for instance this would evaluate true, even if it were a boolean *kind of* object, with a false value:

Code:

Pointer* some_pointer = &some_object; if(some_pointer) { cout << "It was True!"; }

But I am sure you probably have ran into such things.

Eh, got me, either way the < works...but if it would compare the addresses of the objects its pointing to, then they all would be different...so < would not work if its not overloaded...so I assume it should be working just on what's in the string..anyways...I figured out that I would make a new temp dynamic array of size corresponding to the lhs since temp will never be larger than the object that is being subtracted from...then took the lhs name, looped throuh rhs and if it was not found, then I add to temp, else I just move on..that may take a while for it to loop if rhs has many entires that need to be compared..but I don't think there is any other way...at least from what I know...anyhow, everything works now..so thanks everyone for the help and now I just have to try and figure out how to make it better..thanks again =)