Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Trouble with copy constructor


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
10 replies to this topic

#1 shaqb4   Members   -  Reputation: 469

Like
0Likes
Like

Posted 16 December 2012 - 05:06 PM

Hi, I'm reading the c++ book Beginning C++ Game Programming by Michael Dawson and one of the exercises is to make a copy constructor for a game Lobby object which has a linked list of Player objects on the heap. It's supposed to create a new memory address for all the copy's data members so that the list pointers don't point to the same instances as the original.

I created a constructor that seems to work, but I think it might more complicated than needed.

Here's the Lobby class:

class Lobby
{
	friend ostream& operator<<(ostream& os, const Lobby& aLobby);
	public:
		Lobby(): m_pHead(0) {}
		~Lobby() {Clear();}
		Lobby(const Lobby& l);
		void AddPlayer();
		void RemovePlayer();
		void Clear();
	private:
		Player* m_pHead; //First Player on list
};

Here's the Player class:

class Player
{
	public:
		Player(const string& name = ""): m_Name(name), m_pNext(0) {}
		string GetName() const {return m_Name;}
		Player* GetNext() const {return m_pNext;}
		void SetNext(Player* next) {m_pNext = next;}
	private:
		string m_Name;
		Player* m_pNext;
};

and here's the copy constructor:

Lobby::Lobby(const Lobby& l)
{
	if (l.m_pHead != 0)
	{
		m_pHead = new Player;
		*m_pHead = *l.m_pHead;
		Player* pIter = m_pHead->GetNext();
		Player* pHeap;
		while (pIter != 0)
		{
			pHeap = new Player;
			*pHeap = *pIter;
			pIter = pIter->GetNext();
		}
	}
	else
	{
		m_pHead = 0;
	}
}

Thanks, any help/explanations would be appreciated.

Edited by shaqb4, 16 December 2012 - 05:07 PM.


Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13652

Like
0Likes
Like

Posted 16 December 2012 - 05:20 PM

I haven't read the code in detail, but it's about the length I expect for copying a linked list. The last time I wrote something like that was about 15 years ago (Thank you standard C++ library!) and I seem to remember that using double pointers simplified a lot of the logic in this type of code.

#3 BeerNutts   Crossbones+   -  Reputation: 2978

Like
0Likes
Like

Posted 16 December 2012 - 05:26 PM

How else do you think it'd be possible to do something like you did that's simplier? The method you've chosen looks good to me, and is probably the best method for this job
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#4 Álvaro   Crossbones+   -  Reputation: 13652

Like
0Likes
Like

Posted 16 December 2012 - 05:40 PM

This is the type of code I remember writing with double pointers. The function `copy' is the equivalent of your copy constructor. I hope it helps:

#include <iostream>

struct Node {
  int data;
  Node *next;
};

void copy(Node **dest, Node **orig) {
  for (; *orig; orig = &(*orig)->next, dest = &(*dest)->next) {
    *dest = new Node;
    (*dest)->data = (*orig)->data;
  }
  *dest = 0;
}

void add_node(Node **list, int data) {
  Node *n = new Node;
  n->data = data;
  n->next = *list;
  *list = n;
}

void print(Node *n) {
  for (; n; n = n->next)
    std::cout << n->data << ' ';
  std::cout << '\n';
}

void destruct(Node *n) {
  Node *next;
  for (; n; n = next) {
    next = n->next;
    delete n;
  }
}

int main() {
  Node *list = 0;
  add_node(&list, 1);
  add_node(&list, 2);
  add_node(&list, 3);
  print(list);
  Node *another_list;
  copy(&another_list, &list);
  print(another_list);
  destruct(list);
  destruct(another_list);
}


#5 rip-off   Moderators   -  Reputation: 8515

Like
0Likes
Like

Posted 16 December 2012 - 05:44 PM

I'm not convinced your copy constructor currently works. It appears to create copies of each of the members in the original list, but the pointer in the head node is still pointing at the original list. The copied nodes are leaked.

#6 shaqb4   Members   -  Reputation: 469

Like
0Likes
Like

Posted 16 December 2012 - 09:24 PM

m_pHead = new Player;
*m_pHead = *l.m_pHead;
Doesn't that create a new address for the head node? If not, how would I test it?

#7 Trienco   Crossbones+   -  Reputation: 2208

Like
1Likes
Like

Posted 16 December 2012 - 11:22 PM

You seem to be getting lost in your own variable names. pHeap is created, assigned and then never used for anything.

It's also weird that the code in front of your loop is exactly the same as the one inside the loop. Also, where are you setting up the next pointers? From what little code I can see, all your nodes next pointers are either pointing to the original list or to random garbage.

Your test should be to print out both lists with the players name and the address. If your code is working, all the names must be the same, but the addresses must be different.

If you don't mind a bit of headache, you can usually avoid all the "is this the head?" or "is the head NULL?" special cases by using pointer to pointer (ie. pointer to next pointer instead of using next pointer directly, so your head elements turns into just the first "next" element). But that isn't something to worry about until stuff is actually working in the first place.
f@dzhttp://festini.device-zero.de

#8 rip-off   Moderators   -  Reputation: 8515

Like
1Likes
Like

Posted 17 December 2012 - 02:35 AM

Doesn't that create a new address for the head node?

You are allocating nodes, but you are not linking them correctly. Note that code is copying the Player instance, which implicitly copies the "next" pointer. Thus, after that line the head->next of both Lobbies point to the same sublist. Since head->next isn't subsequently modified, the loop following effectively just leaks a bunch of memory.

If not, how would I test it?

Trienco's suggestion of printing both the names and addresses of the Player instances is a good one, you can visualise the list that way.

#9 shaqb4   Members   -  Reputation: 469

Like
0Likes
Like

Posted 17 December 2012 - 07:13 AM

Thanks, I finally got it to work with the following modified constructor. Posted Image

Lobby::Lobby(const Lobby& l)
{
    if (l.m_pHead != 0)
    {
	    m_pHead = new Player;
	    *m_pHead = *l.m_pHead;
	    Player* pIter = m_pHead;
	    Player* pHeap;
	    while (pIter->GetNext() != 0)
	    {
		    pHeap = new Player;
		    *pHeap = *pIter->GetNext();
		    pIter->SetNext(pHeap);
		    pIter = pIter->GetNext();
	    }
    }
    else
    {
	    m_pHead = 0;
    }
}

Your explanations helped a lot.

#10 rip-off   Moderators   -  Reputation: 8515

Like
0Likes
Like

Posted 17 December 2012 - 08:51 AM

Consider:
Lobby::Lobby(const Lobby& other)
{
    if(other.head)
    {
	    this->head = new Player(other.head->GetName());
	    Player *previous = this->head;
	    for(Player *current = other.head->next; current ; current = current->next)
	    {
		    Player *copy = new Player(current->GetName());
		    previous->SetNext(copy);
		    previous = copy;
	    }
    }
    else
    {
	    this->head = nullptr;
    }
}
I haven't tested this, but I believe it should work. I think it is slightly cleaner because it initialises as opposed to copies, and avoids copying pointers from the source list into the new list (even temporarily).

You could also go with the pointer to a pointer, but I find that more difficult to reason about.

Finally, neither is exception safe, these implementations will leak memory if one of the Player allocations or constructors throws an exception. But I won't go into too much detail in "For Beginners" on this point.

#11 shaqb4   Members   -  Reputation: 469

Like
0Likes
Like

Posted 18 December 2012 - 05:59 AM

Thanks rip-off, it works great.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS