Comment &#111;n template list?

122

Author

January 21, 2003 03:28 AM

Anyone care to give me some useful comments on this code? I will use the templates to create lists of pointers. Is it possible to use STL List to create a list of pointers? There is no exception handling in the code and has to be used properly. The main problem I have now is that the pointer m_pCurrent is not used consistently. start with main(), then the list class CObjectList and finally the Node class CObjectListItem. Hmmm, naming convention seems odd... A main to test with

          
#include "CObjectList.h"
#include <iostream>

using namespace std;
using namespace zitadell;

int main()
{
        //create a list for integers

	CObjectList<int> *list = new CObjectList<int>; 

	int v1, v2, v3, v4;

	v1=10; v2=20; v3=30; v4=40;
        //add the ptrs to the integers to the list

	int *item = 0;
	item = &v1
	list->insertNewItem(item);

	item = &v2
	list->insertNewItem(item);

	item = &v3
	list->insertNewItem(item);

	item = &v4
	list->insertNewItem(item);
        //check the list and print some contents

	cout << "First Item: " << *list->getFirstItem() << '\n';

	while(!list->isLast())
		cout << *list->getNextItem() << '\n';

	cout << "Number of nodes: " << list->getCount() << '\n';
	
	list->moveFirst(&v1); //move v1 to the top of the list


	while(!list->isEmpty()) //delete the nodes, could be done by destructor also

		{
			cout << "Last Item: " << *list->getFirstItem() << '\n';
			cout << "Deleting Last Item...: " << '\n';
			list->deleteItem();
			cout << "Number of nodes: " << list->getCount() << '\n';
		}

	delete list;
	return 0;
};

The list class

                
#ifndef ZITADELL_COBJECTLIST_H
#define ZITADELL_COBJECTLIST_H

#include "CObjectListItem.h"

namespace zitadell
{
	template <class ITEM> 
		class CObjectList 
	{
		private:
			CObjectListItem<ITEM>	*m_pFirst;		//ptr to the first item in the list

			CObjectListItem<ITEM>	*m_pLast;			//ptr to the last item in the list

			CObjectListItem<ITEM>	*m_pCurrent;	//pointer to the current item (if any) in the list

			int m_iNodes;												//number of nodes in the list

			
		public:
			//CONSTRUCTOR

			CObjectList();

			//DESTRUCTOR

			~CObjectList();

			//MODIFICATION MEMBER METHODS

			void insertNewItem	(ITEM *item);	//creates a new node and inserts it first, sets m_pCurrent

			void deleteItem		(ITEM *item);	//delete the node containing *item. sets m_pCurrent

			void deleteItem			();						//delete the current item.sets m_pCurrent


			void moveFirst	(ITEM *item);	//moves the specified item to the top if it exists

			void moveLast	(ITEM *item);	//moves the specified item to the bottom if it exists


			ITEM *getFirstItem	();	//returns a ptr to the first item in the list, sets m_pCurrent

			ITEM *getLastItem		();	//returns a ptr to the last object. sets m_pCurrent

			ITEM *getNextItem		();	//advances one and returns current ptr. sets m_pCurrent

			ITEM *getPrevItem		();	//reverses one and returns current ptr. sets m_pCurrent


			//CONSTANT MEMBER METHODS

			ITEM *getCurrentItem(); //returns a ptr to the current item

			
			int	getCount() { return m_iNodes; };	//returns the number of nodes in the list


			//returns true if the list is empty

			bool isEmpty()	{ return (m_pFirst == 0 && m_pLast == 0);								};
			//returns true if the current position is the first node

			bool isFirst()	{ return (m_pCurrent == m_pFirst && isEmpty() == false);};
			//returns true if the current position is the last node

			bool isLast()	{ return (m_pCurrent == m_pLast && isEmpty() == false);	};

		private:
			//if *item exists in the list, findNode returns a ptr to the node

			CObjectListItem<ITEM> *findNode	(ITEM *item);	
			//creates a new node on the heap and returns a ptr to it

			CObjectListItem<ITEM> *newNode	(ITEM *item);
			//extracts a node out of the list if it exists

			void extractNode(CObjectListItem<ITEM> *node);
			//inserts a node first in the list

			void insertFirst(CObjectListItem<ITEM> *node);
			//inserts a node last in the list

			void insertLast	(CObjectListItem<ITEM> *node);

	};//end class definition


	/**************************************************************************************
	//CONSTRUCTOR
	**************************************************************************************/
	template <class ITEM> 
	CObjectList<ITEM>::CObjectList()
		: m_pFirst(0), m_pLast(0), m_pCurrent(0), m_iNodes(0)
		{	
		};
	/**************************************************************************************
	//DESTRUCTOR
	**************************************************************************************/
	template <class ITEM> 
	CObjectList<ITEM>::~CObjectList()
		{
			m_pCurrent = m_pFirst;
			while(m_pCurrent != 0)
			{
				m_pFirst = m_pCurrent->getNextNode();
				delete m_pCurrent;
				m_pCurrent = m_pFirst;
			}
			m_pLast = 0;
		};
	/**************************************************************************************
	//PUBLIC
	**************************************************************************************/
	///////////////////////////////////////////////////////////////////////////////////////
	//MODFICATION MEMBER METHODS
	///////////////////////////////////////////////////////////////////////////////////////
	template <class ITEM> 
	void CObjectList<ITEM>::insertNewItem(ITEM *item)
		{
			if(findNode(item) != 0)
				return;											//return if node already exists

			m_pCurrent = newNode(item);		//create a new node
			
			insertFirst(m_pCurrent);			//insert the new node first

			m_iNodes += 1;								//increase the number of nodes
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	void CObjectList<ITEM>::deleteItem(ITEM *item)
		{
			m_pCurrent = findNode(item);	//find the node with the correct item

			deleteItem();
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	void CObjectList<ITEM>::deleteItem()
		{
			if(m_pCurrent == 0)						//continue only if valid current node
				return;

			extractNode(m_pCurrent);			//extract the node from the list if found

			m_pCurrent->setItem(0);				//set item to zero
			
			delete m_pCurrent;						//delete the node

			m_pCurrent = m_pFirst;				//reset m_pCurrent to the first node
			
			m_iNodes -= 1;								//decrease the number of nodes		
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	void CObjectList<ITEM>::moveFirst(ITEM *item)
		{
			m_pCurrent = findNode(item);
			
			if(m_pCurrent == 0)
				return;

			extractNode(m_pCurrent);
			insertFirst(m_pCurrent);		
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	void CObjectList<ITEM>::moveLast(ITEM *item)
		{
			m_pCurrent = findNode(item);
			
			if(m_pCurrent == 0)
				return;

			extractNode(m_pCurrent);
			insertLast(m_pCurrent);			
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	ITEM *CObjectList<ITEM>::getFirstItem()
		{
			m_pCurrent = m_pFirst;
			return m_pCurrent != 0 ? m_pCurrent->getItem() : 0;	
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	ITEM *CObjectList<ITEM>::getLastItem()
		{
			m_pCurrent = m_pLast;
			return m_pCurrent != 0 ? m_pCurrent->getItem() : 0;
		};	
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	ITEM *CObjectList<ITEM>::getNextItem()
		{
			if(m_pCurrent != 0)
				m_pCurrent = m_pCurrent->getNextNode();
			return m_pCurrent != 0 ? m_pCurrent->getItem() : 0;
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	ITEM *CObjectList<ITEM>::getPrevItem()
		{
			if(m_pCurrent != 0)
				m_pCurrent = m_pCurrent->getPrevNode();
			return m_pCurrent != 0 ? m_pCurrent->getItem() : 0;
		};
	///////////////////////////////////////////////////////////////////////////////////////
	//CONSTANT MEMBER METHODS
	///////////////////////////////////////////////////////////////////////////////////////
	template <class ITEM> 
	ITEM *CObjectList<ITEM>::getCurrentItem()
		{
			return m_pCurrent != 0 ? m_pCurrent->getItem() : 0;
		};
	/**************************************************************************************
	//PRIVATE
	**************************************************************************************/
	///////////////////////////////////////////////////////////////////////////////////////

	//MODFICATION MEMBER METHODS

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

	template <class ITEM> 
	CObjectListItem<ITEM> *CObjectList<ITEM>::newNode(ITEM *item)
		{
			CObjectListItem<ITEM> *new_node = new CObjectListItem<ITEM>(item);	
			return new_node;
		};
	//-------------------------------------------------------------------------------------

	template <class ITEM> 
	void CObjectList<ITEM>::extractNode(CObjectListItem<ITEM> *node)
		{
			//rest the nodes in front of and after the extracted node

			if(node->getNextNode() != 0)
				node->getNextNode()->setPrevNode(node->getPrevNode());
			else
				m_pLast = node->getPrevNode();

			if(node->getPrevNode() != 0)
				node->getPrevNode()->setNextNode(node->getNextNode());
			else
				m_pFirst = node->getNextNode();
				
			//remove the node links

			node->setNextNode(0);
			node->setPrevNode(0);
		};
	///////////////////////////////////////////////////////////////////////////////////////

	//CONSTANT MEMBER METHODS

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

	template <class ITEM> 
	CObjectListItem<ITEM> *CObjectList<ITEM>::findNode(ITEM *item)
		{
			if(isEmpty())
				return 0;											//return if list is empty


			CObjectListItem<ITEM> *node = 0;
			node = m_pFirst;
			while(node != 0)
			{
				if(node->getItem() == item)
					break;
				node = node->getNextNode();
			}
			return node;
		};
	//-------------------------------------------------------------------------------------

	template <class ITEM> 
	void CObjectList<ITEM>::insertFirst(CObjectListItem<ITEM> *node)
		{
			node->setLink(m_pFirst,0);	
			
			if(m_pFirst != 0)										
				m_pFirst->setPrevNode(node);	//reset current first node


			m_pFirst = node;								//reset the first node pointer

	
			if(m_pLast == 0)								//reset last node ptr if empty

				m_pLast = node;
		};
	//-------------------------------------------------------------------------------------

	template <class ITEM> 
	void CObjectList<ITEM>::insertLast(CObjectListItem<ITEM> *node)
		{
			node->setLink(0,m_pLast);	
			
			if(m_pLast != 0)										
				m_pLast->setNextNode(node);	//reset current first node


			m_pLast = node;								//reset the first node pointer

	
			if(m_pFirst == 0)							//reset last node ptr if empty

				m_pFirst = node;		
		};
};//end namespace


#endif

The node class

                 
#ifndef ZITADELL_COBJECTLISTITEM_H
#define ZITADELL_COBJECTLISTITEM_H

namespace zitadell
{
	template <class ITEM> 
	class CObjectListItem
	{
		private:
			ITEM			*m_pItem;
			CObjectListItem<ITEM>	*m_pNext;
			CObjectListItem<ITEM>	*m_pPrev;

		public:
			//CONSTRUCTOR

			CObjectListItem(ITEM *pItem = 0);

			//DESTRUCTOR

			~CObjectListItem();
		
			//CONSTANT MEMBER METHODS

			ITEM *getItem	() { return m_pItem;	};

			CObjectListItem<ITEM> *getNextNode	()	{ return m_pNext;	};
			CObjectListItem<ITEM> *getPrevNode	()	{ return m_pPrev;	};

			//MODIFICATION MEMBER METHODS

			void setItem	(ITEM *pItem);
			void setLink	(CObjectListItem<ITEM> *pNext, CObjectListItem<ITEM> *pPrev);

			void setNextNode	(CObjectListItem<ITEM> *next)	{ m_pNext		= next;	};
			void setPrevNode	(CObjectListItem<ITEM> *prev)	{ m_pPrev		= prev;	};

	};//end class definition


	/**************************************************************************************
	//CONSTRUCTOR
	**************************************************************************************/
	template <class ITEM> 
	CObjectListItem<ITEM>::CObjectListItem(ITEM *pItem)
		: m_pItem(pItem), m_pNext(0), m_pPrev(0)
		{
		
		};
	/**************************************************************************************
	//DESTRUCTOR
	**************************************************************************************/
	template <class ITEM> 
	CObjectListItem<ITEM>::~CObjectListItem()
		{
			setItem(0);
			setLink(0,0);
		};
	/**************************************************************************************
	//PUBLIC
	**************************************************************************************/
	///////////////////////////////////////////////////////////////////////////////////////
	//MODFICATION MEMBER METHODS
	///////////////////////////////////////////////////////////////////////////////////////
	template <class ITEM> 
	void CObjectListItem<ITEM>::setItem(ITEM *pItem)
		{
			m_pItem		= pItem;
		};
	//-------------------------------------------------------------------------------------
	template <class ITEM> 
	void CObjectListItem<ITEM>::setLink(CObjectListItem<ITEM> *pNext, CObjectListItem<ITEM> *pPrev)
		{
			m_pNext		= pNext;
			m_pPrev		= pPrev;		
		};
	///////////////////////////////////////////////////////////////////////////////////////
	//CONSTANT MEMBER METHODS
	///////////////////////////////////////////////////////////////////////////////////////
	
	//-------------------------------------------------------------------------------------
	
	/**************************************************************************************
	//PRIVATE
	**************************************************************************************/
	///////////////////////////////////////////////////////////////////////////////////////

	//MODFICATION MEMBER METHODS

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


	//-------------------------------------------------------------------------------------


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

	//CONSTANT MEMBER METHODS

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

	
	//-------------------------------------------------------------------------------------


};//end namespace

#endif

Hope this doesnt turn out crappy... Edit: Well some of it came out crappy, sorry for that. Edit: Crappy again. Edit: added more comments in CObjectList Edit: finally edited the subject [edited by - clabinsky on January 21, 2003 4:31:59 AM] [edited by - clabinsky on January 21, 2003 4:36:29 AM] [edited by - clabinsky on January 21, 2003 6:05:56 AM] [edited by - clabinsky on January 21, 2003 6:16:02 AM]

Why make it simple when you can make it sooo nice and complicated?

Qw3r7yU10p!

819

January 21, 2003 04:15 AM

passing comment - learn to write good subject descriptions

clabinsky

122

Author

January 21, 2003 04:30 AM

Ok, petewood. Sorry, I am tired but I''ll try.

The example has three files. I''ll describe them in the order they are listed above.

1. the main() function to test the pointer list
it is just used to create the list, iterate through it in different ways while displying contents, and finally deleting the list.

2. CObjectList
This class is the container for CObjectListItem objects. The objects are stored in a linked list. The class holds pointers to the first, last and current node of the linked list. It also contains a counter m_iNodes which holds the number of nodes currently in the list.

It is a template class which will operate on pointers to the type or object specified when the list is created. Since the list handles pointers, the user has to use pointers (or references) when adding, deleting, and getting items from the list. A few bool functions returns flags for empty list, if current position is at the top or bottom.

When destroyed, it only deletes the nodes, leaving it up to the creator class to destroy the objects contained in each node.

3. CObjectListItem
This is also a template class. Each list item in CObjectList is an object of this class. The class is only used by CObjectList internally and is not supposed to be initialized as a separate object. It gives the CObjectList different functions for setting and retrieving the members. The members are classical two-way linked list members, such as the item(type) which the user choosed upon initialization of the list, a pointer to the next node and to the previous node.

I hope this will suffice.

Why make it simple when you can make it sooo nice and complicated?

Anonymous

January 21, 2003 05:01 AM

clabinsky, I think petewood meant that he will not help you because of the poor subject "Comment?". Change your post to have a more descriptive subject, that will significantly help you to get an answer.

http://www.tuxedo.org/~esr/faqs/smart-questions.html#bespecific

clabinsky

122

Author

January 21, 2003 05:13 AM

Oops, ok you you thanks.

I added some extra comments on the CObjectList.

Now as for the specifics. I guess I was looking for some pointers on how the code is structured, the commenting in the code, memory leaks? and any other thing I cannot think of. Maybe a better way of doing this kind of thing except with the STL list.

However, I realize that it might be too much to ask for because it is not really a problem with the code. So, I do not expect any comments, I guess

.

Well, anyone who needs this kind of list can take it and rip it. Be my guest.

Why make it simple when you can make it sooo nice and complicated?

Qw3r7yU10p!

819

January 21, 2003 05:41 AM

quote:AP: clabinsky, I think petewood meant that he will not help you because of the poor subject "Comment?"

Not true, I''m in the middle of typing up some help at this very moment. I''m just making the suggestion that he/she will get more attention and specific interest if they mention what they are posting about in the subject. That''s actually quite helpful in itself come to think of it.

Qw3r7yU10p!

819

January 21, 2003 05:53 AM

This code is based on yours to try and do what yours did. It uses the std::list class.
What you wish to do with your data significantly affects the container you choose to store it in. It is possible to change the typedef at the start to being a vector or a deque. The only problem with a vector is you can't push values onto the front, only the back. Also lists and deques are far more efficent at pushing and popping.
So you can choose your container and do similar things (but not everything) and get different performances.

I have only used one algorithm - find - from the standard library, but they are the best way to do things rather than writing loops.

[hobbyhorse]The problem with loops is you have to look through it to work out what it's doing. If you use a standard algorithm, or one you've written yourself you can just look at the name and say 'oh that's what it does'. It helps you organise your ideas, reuse code, etc. etc.
[/hobbyhorse]

Anyway, saying that, I haven't deviated too far from your original code. I would code things differently and use more of the library. I felt it would confuse things if I went too far.

                    #include <iostream>#include <list>#include <algorithm>int main(){	// put usings upfront where I can keep my eye on what's being used	using std::list;	using std::cout;	using std::endl; //end line... for output	using std::find;		// I typedef a couple of things to save having really long names later	// if you're not familiar with this you can just go and replace	// the names like 'intPointersIter' with list<int*>::iterator etc.	typedef list<int*> intPointers;	// typedef a list of pointers to ints	typedef intPointers::iterator intPointersIter; //typedef the iterator to save typing	intPointers myInts;// a container of pointers to integers	int v1(10), v2(20), v3(30), v4(40);	myInts.push_back(&v1);	myInts.push_back(&v2);	myInts.push_back(&v3);	myInts.push_back(&v4);	cout << "First Item (pointer to int) " << myInts.front() << endl;//or	intPointersIter it = myInts.begin();	cout << "First Item (pointer to int) " << *it;// *it dereferences the iterator                //and returns the value in the list which is a pointer to an int	cout << ": (actual int) " << **it << endl;	// **it dereferences the pointer                //to the int so	returns the value of the int	// the above double dereferencing is only necessary because you have chosen	// to store pointers to ints and not actual ints	cout << endl;	intPointersIter itEnd = myInts.end();	while(it != itEnd) {		cout << "pointer to int " << *it;		cout << ": actual int " << **it << endl;		++it;//increases iterator to next item	}	cout << endl;	cout << "Number of items " << myInts.size() << endl;	//	list->moveFirst(&v1); your function found the first occurance of the value//  and put it at the front of the list. If there was more than one it wouldn't put all//  of them at the front just the first that it found. If you called it again it//  wouldn't get past the first one... desirable?	intPointersIter itFound = find(myInts.begin(), myInts.end(), &v3); // finds first                    // occurance of the pointer	myInts.erase(itFound);// this erases the entry in the list (the copy of the pointer,                    // not the pointed to value!)	myInts.push_front(&v3);// puts a copy of the pointer to v3 at the front of the list	while(!myInts.empty()) {		cout << "Number of items " << myInts.size();		cout << ": Last Item " << *myInts.back();		myInts.pop_back();		cout << ": pop!";		cout << ": Number of items " << myInts.size() << endl;	}	return 0;};

[edited by - petewood on January 21, 2003 8:00:45 AM]

SabreMan

504

January 21, 2003 07:46 AM

quote:Original post by clabinsky
Anyone care to give me some useful comments on this code?

Where''s the copy and assignment operators? Why can I only store pointers to objects? Why are "constant member methods" not actually constant? Why are the ownership semantics confused (you cannot remove an element without deleting it, while the dtor does not delete elements)?

clabinsky

122

Author

January 21, 2003 12:32 PM

Hey Petewood thanks a lot, very interesting. I cannot believe that I did not see the declaration list described in any of the books I have. I must be blind.

I know I have read somewhere that STL list requires the objects operated on to have default constructors.

Q. How does this apply when we are using pointers?

Ok, the naming should be as close to STL list functions as possible in order to facilitate easiest understanding. Well, thats an easy one.

Q. Doesn''t list add another level of indirection compared to the list I have? It probably won''t have much effect but anyways.

And Sabreman, good questions - as always

quote:Where''s the copy and assignment operators?Why can I only store pointers to objects?

Implementation specifics. So far I have no need for the assignment operator nor the copy constructor. I know it is bad style but I wanted to keep it slim. I would add them at the time they would be needed.

quote:Why are "constant member methods" not actually constant?

You are absolutely right here. I have should have added the keywords and maybe returned a const ref. Usually, I tend to skip this until last and only make sure the constant methods do not change the state of the object.

quote:
Why are the ownership semantics confused (you cannot remove an element without deleting it, while the dtor does not delete elements)?

Now, not sure I am with you on this. The destructor does delete the nodes in the list. It does not delete the elements pointed to because it did not new them. Everything thats newed is deleted as far as I can see. In the implementation I use, deleting the elements could have seroius consequences with wild pointers, which is why I avoided it.

Otherwise, thanks for looking. I have will improve the templates based on what you''ve written. And try out the list after I feel confident with the syntax of templates and iterators.

Why make it simple when you can make it sooo nice and complicated?

Comment on template list?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Comment on template list?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines