C++ RSS C++ RSS

Linked List of Pointers

Please support our C++ advertiser: Intel Parallel Studio Home
Reply

•
•
Join Date: Mar 2006
Posts: 9
Reputation: Kanvas is an unknown quantity at this point 
Solved Threads: 0
Kanvas Kanvas is offline Offline
Newbie Poster

Linked List of Pointers

 
0
  #1
Oct 21st, 2008
how do you make a node of pointer of a device? (device is just a class that i made up, i need to use pointers in LL so i can "share" one object with multiple LLs)

C++ Syntax (Toggle Plain Text) 
  1. struct node
  2. {
  3.   device * devicePtr;
  4.   node * left, * right, * next;
  5.   node(const device * dvptr)               {
  6.               dvptr = NULL;
  7.               left = right = next = NULL;                          }
  8. }

then how can i access to the pointer? such as when i do a copy constructor
C++ Syntax (Toggle Plain Text) 
  1. const list& list::operator= (const list& aList)
  2. {
  3. 	//if self copy, don't do anything
  4. 	if(this == &aList)
  5. 		return *this;
  6.  
  7. 	//release exist memory , if there's any
  8. 	if (head)
  9. 	{
  10. 		destroyList();
  11. 	}
  12. 	//make *this a deep copy of "aList"
  13. 	if(!aList.head)
  14. 		head = NULL;
  15. 	else
  16. 	{
  17. 		//copy the first node
  18. 		head = new node(aList.head->dvptr);
  19.  
  20. 		node * currSrc = aList.head->dvptr;
  21. 		node * currDes = head;
  22.  
  23. 		while(currSrc)
  24. 		{
  25. 			currDes->next = new node(currSrc->dvptr);
  26. 			currDes = currDes->next;
  27.  
  28. 			currSrc = currSrc->next;
  29. 		}
  30.  
  31. 		currDes->next = NULL;
  32. 	}
  33. 	return *this;
  34. }
I know that aList.head->dvptr and currSrc->dvptr are wrong but i don't know how else
Can anyone point it out for me?
Thanks
Last edited by Kanvas; Oct 21st, 2008 at 2:55 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: Linked List of Pointers

 
0
  #2
Oct 21st, 2008
•
•
•
•
Originally Posted by Kanvas View Post
how do you make a node of pointer of a device? (device is just a class that i made up, i need to use pointers in LL so i can "share" one object with multiple LLs)

C++ Syntax (Toggle Plain Text) 
  1. struct node
  2. {
  3.   device * devicePtr;
  4.   node * left, * right, * next;
  5.   node(const device * dvptr)               {
  6.               dvptr = NULL;
  7.               left = right = next = NULL;                          }
  8. }

then how can i access to the pointer? such as when i do a copy constructor
C++ Syntax (Toggle Plain Text) 
  1. const list& list::operator= (const list& aList)
  2. {
  3. 	//if self copy, don't do anything
  4. 	if(this == &aList)
  5. 		return *this;
  6.  
  7. 	//release exist memory , if there's any
  8. 	if (head)
  9. 	{
  10. 		destroyList();
  11. 	}
  12. 	//make *this a deep copy of "aList"
  13. 	if(!aList.head)
  14. 		head = NULL;
  15. 	else
  16. 	{
  17. 		//copy the first node
  18. 		head = new node(aList.head->dvptr);
  19.  
  20. 		node * currSrc = aList.head->dvptr;
  21. 		node * currDes = head;
  22.  
  23. 		while(currSrc)
  24. 		{
  25. 			currDes->next = new node(currSrc->dvptr);
  26. 			currDes = currDes->next;
  27.  
  28. 			currSrc = currSrc->next;
  29. 		}
  30.  
  31. 		currDes->next = NULL;
  32. 	}
  33. 	return *this;
  34. }
I know that aList.head->dvptr and currSrc->dvptr are wrong but i don't know how else
Can anyone point it out for me?
Thanks
there are a lot of things I don't understand in your code, or that seem wrong

C++ Syntax (Toggle Plain Text) 
  1. struct node
  2. {
  3.   device * devicePtr;
  4.   node * left, * right, * next;
  5.   node(const device * dvptr)               {
  6.               dvptr = NULL;
  7.               left = right = next = NULL;                          }
  8. }

i don't understand the node's constructor. I mean u pass to it a pointer to a device and put that pointer to NULL, why? I mean, no initzialization is done here. I think you wanted to write devicePtr = dvptr... makes more sense


C++ Syntax (Toggle Plain Text) 
  1. //copy the first node
  2. head = new node(aList.head->dvptr);

this doesn't look like a deep copy, I mean, it doesn't copy the devices !!, if you do it this way the new list nodes will point to the same devices as the old one and then you'll don't know what list is responsible for the object destruction. If you still want to have shared devices between two linked lists you should replace the device* with shared_ptr<device>
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2006
Posts: 9
Reputation: Kanvas is an unknown quantity at this point 
Solved Threads: 0
Kanvas Kanvas is offline Offline
Newbie Poster

Re: Linked List of Pointers

 
0
  #3
Oct 21st, 2008
ahhh....that was a typo it's supposed to be
C++ Syntax (Toggle Plain Text) 
  1. struct node
  2. {
  3.   device * dvptr;
  4.   node * left, * right, * next;
  5.   node(const device * dvptr)               
  6. {
  7.               dvptr = NULL;
  8.               left = right = next = NULL;                          
  9. }
  10. }


Can you explain how do you use share_ptr<device> in this? I just don't want ended up with 50 copies of the same object in 50 different LLs. Also is there a way without using share_ptr? I don't think my class cover that yet.

Sorry, i'm so clueless right now
Last edited by Kanvas; Oct 21st, 2008 at 4:45 am.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: Linked List of Pointers

 
0
  #4
Oct 21st, 2008
http://www.onlamp.com/pub/a/onlamp/2...rs.html?page=1

try reading this... it's kind of long, but it also explains the RAII idiom and a large variety of smart pointers.
If your STL version doesn't have std::tr1 you will probably have to install boost in order to have access to the shared_ptr, or you could just implement it yourself ( a trivial implementation is quite easy once you understand how a shared_ptr works: u just have to increase the reference count when you copy and assign the shared_ptr, decrease it in the destructor if count>1 or permanentrly destroy the pointed resource in the destructor if count = 1. )
Reply With Quote Quick reply to this message  
•
•
Join Date: Mar 2006
Posts: 9
Reputation: Kanvas is an unknown quantity at this point 
Solved Threads: 0
Kanvas Kanvas is offline Offline
Newbie Poster

Re: Linked List of Pointers

 
0
  #5
Oct 21st, 2008
•
•
•
•
Originally Posted by kux View Post
http://www.onlamp.com/pub/a/onlamp/2...rs.html?page=1

try reading this... it's kind of long, but it also explains the RAII idiom and a large variety of smart pointers.
If your STL version doesn't have std::tr1 you will probably have to install boost in order to have access to the shared_ptr, or you could just implement it yourself ( a trivial implementation is quite easy once you understand how a shared_ptr works: u just have to increase the reference count when you copy and assign the shared_ptr, decrease it in the destructor if count>1 or permanentrly destroy the pointed resource in the destructor if count = 1. )

Thanks for the hints. I kinda understand shared_ptr now but i think it's out of the scope of what i'm doing right now (a assignment for a CS class)

Can you think of any think else that allows LLs to share?
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: Linked List of Pointers

 
0
  #6
Oct 21st, 2008
well, this is the "good" way of doing it... of course... you could find a workarround that would kind of be based on the same principle... I'll try to make a short implementation.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 119
Reputation: kux is on a distinguished road 
Solved Threads: 10
kux kux is offline Offline
Junior Poster

Re: Linked List of Pointers

 
0
  #7
Oct 21st, 2008
C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. template<class T>
  7. class myPointer
  8. {
  9. public:
  10. 	T* pT_;
  11. 	int *refcount_;
  12.  
  13. public:
  14. 	myPointer(): pT_(NULL), refcount_(NULL) {};
  15.  
  16. 	myPointer ( T* objP )
  17. 	{
  18. 		pT_ = objP;
  19. 		refcount_ = new int(1);
  20. 	}
  21. 	myPointer( const myPointer& node )
  22. 	{
  23. 		pT_ = node.pT_;
  24. 		refcount_ = node.refcount_;
  25. 		*refcount_ = *refcount_ + 1;
  26. 	}
  27.  
  28. 	myPointer & operator= ( const myPointer& node )
  29. 	{
  30. 		if( this != &node )
  31. 		{
  32. 			pT_ = node.pT_;
  33. 			refcount_ = node.refcount_;
  34. 			*refcount_ = *refcount_ + 1;
  35. 		}
  36. 		return *this;
  37. 	}
  38.  
  39. 	~myPointer ()
  40. 	{
  41. 		if( refcount_ != NULL )
  42. 		{
  43. 			if ( *refcount_ == 1 )
  44. 			{
  45. 				delete pT_;
  46. 				delete refcount_;
  47. 			}
  48. 			else
  49. 				*refcount_ = *refcount_ - 1;		
  50. 		}
  51. 	}
  52. };
  53.  
  54.  
  55. template < class T >
  56. class List
  57. {
  58. 	struct Node
  59. 	{
  60. 		myPointer<T> p_;
  61. 		Node* next_;
  62.  
  63. 		Node( const myPointer<T>& obj )
  64. 		{
  65. 			p_ = obj;
  66. 			next_ = NULL;
  67. 		}
  68.  
  69.  
  70. 	};
  71.  
  72. 	Node *head_;
  73. public:
  74. 	List( const myPointer<T>& obj )
  75. 	{
  76. 		head_ = new Node ( obj );
  77. 	}
  78.  
  79. 	void addToList( const myPointer<T>& obj )
  80. 	{
  81. 		Node * newHead = new Node( obj );
  82. 		newHead->next_ = head_;
  83. 		head_ = newHead;
  84. 	}
  85.  
  86. 	void printList()
  87. 	{
  88. 		Node *p = head_;
  89. 		while ( p != NULL )
  90. 		{
  91. 			cout<< *(p->p_.pT_) << endl;
  92. 			p = p->next_;
  93. 		}
  94. 	}
  95. 	~List()
  96. 	{
  97. 		Node * p = head_;
  98. 		while ( p != NULL )
  99. 		{
  100. 			Node *paux = p->next_;
  101. 			delete p;
  102. 			p = paux;
  103. 		}
  104. 	}
  105. };
  106.  
  107.  
  108. int main(int argc, char* argv[])
  109. {
  110. 	{
  111. 		myPointer<int> x1( new int(5) );
  112. 		myPointer<int> x2( new int(7) );
  113.  
  114. 		List<int> myList( x1 );
  115. 		myList.addToList( x2 );
  116. 		myList.addToList( x2 );
  117. 		myList.addToList( x1 );
  118.  
  119. 		List<int> mySecondList( x1 );
  120. 		mySecondList.addToList( x1 );
  121. 		mySecondList.addToList( x2 );
  122. 		mySecondList.addToList( x2 );
  123.  
  124. 		myPointer<int> x3( new int(9) );
  125.  
  126. 		myList.addToList( x3 );
  127. 		mySecondList.addToList( x3 );
  128.  
  129. 		myList.printList();
  130. 		cout<<endl;
  131. 		mySecondList.printList();
  132. 	}
  133.  
  134. 	_CrtDumpMemoryLeaks();
  135.  
  136. }

well, this is what I did as fast as I could, maybe it still has bugs, but none that I could find right now . For the test i made it has no leaks.
As you can see you have only three objects ( x1, x2, x3 ) that are shared among 2 lists.
More over, you can have the same object more times in the same list ( x1 and x2 appear twice in both lists ).
Insted of the device class you have a template parameter to the myPointer and List classes that will be the contained type. The test provided uses int as the template parameter.
Last edited by kux; Oct 21st, 2008 at 7:14 am. Reason: small mistake
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread is more than three months old.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the C++ Forum
Thread Tools Search this Thread



api application array arrays based beginner binary bitmap c++ c/c++ calculator char char* class classes code coding compile compiler console conversion convert count data database delete deploy developer dll download dynamiccharacterarray email encryption error file forms fstream function functions game generator getline givemetehcodez graph homeworkhelp homeworkhelper iamthwee ifstream input int java lib list loop looping loops map math matrix memory multiple news node number numbertoword output parameter pointer problem program programming project proxy python random read recursion recursive reference rpg simple sorting string strings temperature template text tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC