Jump to content

  • Log In with Google      Sign In   
  • Create Account

Is it safe to use classes in containers?


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
9 replies to this topic

#1 Vortez   Crossbones+   -  Reputation: 2698

Like
0Likes
Like

Posted 15 September 2013 - 11:09 PM

That's the question...

 

Oh and if some have the time, can they tell me if it would be safe to use classes in THIS containers i've made, a simple linked list (it work with structs):

 

(Im a bit worried about the zeromemory in the constructor and the assignment in the other...)

#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_
#ifdef __cplusplus
//----------------------------------------------------------------------//
#include <Windows.h>
//----------------------------------------------------------------------//

// Node 
template <class DataT> class CNode {
public:
	DataT Data;
	CNode<DataT> *Next;
	CNode<DataT> *Prev;
	CNode(){
		ZeroMemory(&Data, sizeof(DataT));
		Next = NULL;
		Prev = NULL;
	}
	CNode(DataT d){
		Data = d;
		Next = NULL;
		Prev = NULL;
	}

	CNode<DataT> *GetNext(){return Next;}
	CNode<DataT> *GetPrev(){return Prev;}
};

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

// LinkedList 
template <class DataT> class CLinkedList : public CNode<DataT> {	
private:
	CNode<DataT> *First, *Last;
	UINT NumNodesAllocated;
public:
	CLinkedList(){
		First = NULL;
		Last  = NULL;
		NumNodesAllocated = 0;
		srand(GetTickCount());
	}
	~CLinkedList(){
		Clear();
	}
	 
	UINT GetNodesCount();

	CNode<DataT> *GetNode(UINT Indx);
	CNode<DataT> *GetFirstNode();
	CNode<DataT> *GetLastNode();

	CNode<DataT>* Push(DataT *d);
	bool Pop(DataT *d);
	bool Delete(CNode<DataT> *pNode);
	void Clear();

	void Randomize();

	void Fill(CNode<DataT> *pNode);
};

template <class DataT> UINT CLinkedList<DataT>::GetNodesCount()
{
	return NumNodesAllocated;
}

template <class DataT> CNode<DataT>* CLinkedList<DataT>::GetNode(UINT Indx)
{
	CNode<DataT> *pNode = First;
	if(!pNode){return NULL;}
	if(Indx >= NumNodesAllocated){return NULL;}

	UINT i = 0;
	while(i < Indx){
		pNode = pNode->GetNext();
		if(!pNode){return NULL;}
		i++;
	}

	return pNode;
}

template <class DataT> CNode<DataT>* CLinkedList<DataT>::GetFirstNode()
{
	return First;
}

template <class DataT> CNode<DataT>* CLinkedList<DataT>::GetLastNode()
{
	return Last;
}

template <class DataT> CNode<DataT>* CLinkedList<DataT>::Push(DataT *d)
{
	CNode<DataT> *pNewNode = new CNode<DataT>;
	NumNodesAllocated++;

	pNewNode->Data = *d;
	if(First == NULL){
		Last  = pNewNode;
		First = pNewNode;
    } else {
		pNewNode->Prev = Last;
		Last->Next = pNewNode;
		Last = pNewNode;
    }

	return pNewNode;
}

template <class DataT> bool CLinkedList<DataT>::Pop(DataT *d)
{
	if(Last){
		if(d != NULL)
			*d = Last->Data;
		return Delete(Last);
	}

	return false;
}

template <class DataT> bool CLinkedList<DataT>::Delete(CNode<DataT> *pNode)
{
	if(pNode){
		if(pNode->Prev){
			pNode->Prev->Next = pNode->Next;
			if(pNode->Next){
				pNode->Next->Prev = pNode->Prev;
			} else {
				Last = pNode->Prev;
			}
		} else {
			if(pNode->Next){
				pNode->Next->Prev = NULL;
				First = pNode->Next;
			} else {
				First = NULL;
				Last  = NULL;
			}
		}

		delete pNode;
		NumNodesAllocated--;

		return true;
	}

	return false;
}

template <class DataT> void CLinkedList<DataT>::Clear()
{
	while(Pop(NULL));
}

template <class DataT> void CLinkedList<DataT>::Randomize()
{
	CLinkedList<DataT> TmpList;

	UINT NumItems = this->GetNodesCount();

	while(NumItems > 0){
	
		UINT RandVal = rand() % NumItems;
	
		CNode<DataT> *pNode = this->GetNode(RandVal);
		
		DataT d = pNode->Data;
		TmpList.Push(&d);

		this->Delete(pNode);

		NumItems--;
	}
	this->Clear();

	for(UINT Cpt = 0; Cpt < TmpList.GetNodesCount(); Cpt++){

		CNode<DataT> *pNode = TmpList.GetNode(Cpt);

		DataT d = pNode->Data;
		this->Push(&d);
	}

	TmpList.Clear();
}

template <class DataT> void CLinkedList<DataT>::Fill(CNode<DataT> *pNode)
{
	this->Clear();
	
	while(pNode){
		this->Push(&pNode->Data);
		pNode = pNode->GetNext();
	}
}

#endif
#endif //--_LINKED_LIST_H_

Thx.


Edited by Vortez, 15 September 2013 - 11:15 PM.


Sponsor:

#2 Hodgman   Moderators   -  Reputation: 30352

Like
13Likes
Like

Posted 15 September 2013 - 11:23 PM

Yes, all the std:: containers work well with any data type.

There are some issues with your container though:

1)
ZeroMemory(&Data, sizeof(DataT));
If DataT is a non-POD class (if it has constructors, or members that have constructors), then this is very, very bad. Just delete that line.
 
e.g. in the example below, std::vector is a non-POD class. It has constructors/destructors that perform careful memory management. On line #1, this constructor allocates 42 integers.
On line #2, this vector is overwritten with zeros... This is a really bad error. In the best case, maybe your program won't crash right away, and you've simply corrupted the object.
On line #3, we try to use the corrupted object, and this will likely crash.
std::vector<int> myVector(42); // #1
ZeroMemory(&myVector, sizeof(std::vector<int>)); // #2
myVector[12] = 12; // #3
 
2)
 Your other constructor isn't wrong, but it's very inefficient:
/// old
	CNode(DataT d)//copying 'd' by value here, means that the input class is copied from it's original location to 'd'
	{//hidden here: C++ default-constructs all members
		Data = d;//after 'Data' has been default-constructed, then copy d over the top of it
		Next = NULL;
		Prev = NULL;
	}
///new
	CNode(const DataT& d) // don't pass 'd' by value, pass by reference to avoid making an extra copy
	 : Data(d) // instead of default-constructing Data, use a copy-constructor
	{
		Next = NULL;
		Prev = NULL;
	}
 
3) You wrote that constructor above that takes a DataT argument, but don't even use it:
/// old
template <class DataT> CNode<DataT>* CLinkedList<DataT>::Push(DataT *d)
{
	CNode<DataT> *pNewNode = new CNode<DataT>;//default constructs 'Data', then uses ZeroMemory over it
	NumNodesAllocated++;

	pNewNode->Data = *d; // then copies '*d' over 'Data' again

/// new
template <class DataT> CNode<DataT>* CLinkedList<DataT>::Push(const DataT& d)
{
	CNode<DataT> *pNewNode = new CNode<DataT>(d);//construct 'Data' just once, using the right value
	NumNodesAllocated++;
Other issues:

4) This has no place in a linked list class :-P
It has no impact on your question (whether classes work), but the average user would be surprised to find that the global srand value was being changed whenever they create a linked list.
srand(GetTickCount());
5) Why does CLinkedList inherit from CNode?

6) Your CLinkedList class violates the rule of 3 / rule of 2, which will cause code like below to crash:
{
  int value = 42;
  CLinkedList<int> myList;
  myList.Push( &value );
 
  CLinkedList<int> myOtherList = myList; // at the moment, this will perform a shallow copy
  //both lists now point to the same nodes!
  //when they're destructed, they will both try to delete these same nodes!
}//crash!!! double deletion bug!
You can fix this in two ways:
A) make CLinkedList non-copyable:
template <class DataT> class CLinkedList {	
private:
  CLinkedList( const CLinkedList& );
  CLinkedList& operator=( const CLinkedList& );
  //if anyone tries to copy a CLinkedList now, they'll get a compile-time error saying that copying is private
...
B) Implement copying
template <class DataT> class CLinkedList {
...	
public:
...
  CLinkedList( const CLinkedList& otherList )
  {
    First = NULL;
    Last  = NULL;
    NumNodesAllocated = 0;
    *this = otherList;
  }
  CLinkedList& operator=( const CLinkedList& otherList )
  {
    Clear();
    for each node in otherList //pseudo code
      this.Push(node.Data);
    return *this;
  }
...

Edited by Hodgman, 15 September 2013 - 11:39 PM.


#3 Vortez   Crossbones+   -  Reputation: 2698

Like
0Likes
Like

Posted 15 September 2013 - 11:48 PM

Hey, thx for the quick answer. Just to be sure

 

(const DataT *d)

 

is the same as (const DataT& d)

 

right?



#4 L. Spiro   Crossbones+   -  Reputation: 13574

Like
6Likes
Like

Posted 15 September 2013 - 11:58 PM

No.

 

One is a pointer and one is a reference.  They both refer to another location in memory, but to access a pointer’s referenced memory you use indirection ((*d).GetValue()) or the arrow operator (d->GetValue()).  To access the memory to which a reference refers, you use the . operator (d.GetValue()).

 

Pointers can also be reassigned to point to other memory locations whereas references cannot be.

 

Both consume the same amount of memory (4 bytes on x86, 8 bytes on x64) no matter the size of the object to which they point.

 

As a general rule when deciding to pass a reference or a pointer to a function or method, you should always pass a reference when the parameter must refer to a valid memory address, and a pointer when NULL is a possible parameter.

Although you can follow any rules you want, if you adopt such a practice and are consistent with it, it will make your intentions easier to understand and reduce the amount of  “if ( d == NULL ) { return false; }” you will have in your code, which will reduce the risk of accidentally forgetting a NULL check where there should be one and also improve your performance thanks to fewer NULL checks.

 

 

L. Spiro


Edited by L. Spiro, 16 September 2013 - 12:00 AM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#5 SiCrane   Moderators   -  Reputation: 9594

Like
4Likes
Like

Posted 16 September 2013 - 08:12 AM

Yes, all the std:: containers work well with any data type.

That's not quite right. In order to work with a standard library container a class needs to fulfill certain requirements. Under the previous version of the standard every class pretty much needed to satisfy the copy constructable and assignable requirements, but with the current version the requirements vary by container and by container operation. For instance if a class doesn't have an accessible destructor you can't stick it in a container. Nor can you have a container that stores abstract base classes by value.

#6 Servant of the Lord   Crossbones+   -  Reputation: 19499

Like
1Likes
Like

Posted 17 September 2013 - 12:46 PM

Yes, it's safe to use classes in the standard library containers. Some standard library containers requires the class to have certain operations (like operator < for sortable containers like std::map, or operator ==, or copy constructors, etc...) to be defined, but will thankfully refuse to compile if that specific container's the required operators aren't defined, so they are safe to use.

 

About this time last year I was designing a custom container and running into alot of questions about proper allocation and copying and things like that - you might find the resulting thread useful.


It's perfectly fine to abbreviate my username to 'Servant' rather than copy+pasting it all the time.
All glory be to the Man at the right hand... On David's throne the King will reign, and the Government will rest upon His shoulders. All the earth will see the salvation of God.
Of Stranger Flames - [indie turn-based rpg set in a para-historical French colony] | Indie RPG development journal

[Fly with me on Twitter] [Google+] [My broken website]

[Need web hosting? I personally like A Small Orange]


#7 Vortez   Crossbones+   -  Reputation: 2698

Like
0Likes
Like

Posted 18 September 2013 - 02:50 AM

Turn out i decided to use my other linked list class for now, which is not templatized. I have to rewrite some parts there and there each time i use it but in return i know it work

perfectly and let me do more advanced stuffs if needed. (Still, im gonna keep that page bookmarked to fix it later, thx to HodMan for the inputs)

 

L. Spiro ---> So, if i understand correctly, a reference is like a read-only pointer, that cannot be modified or point to NULL, am i right?


Edited by Vortez, 18 September 2013 - 03:08 AM.


#8 L. Spiro   Crossbones+   -  Reputation: 13574

Like
1Likes
Like

Posted 18 September 2013 - 05:06 AM

L. Spiro ---> So, if i understand correctly, a reference is like a read-only pointer, that cannot be modified or point to NULL, am i right?

It is only read-only if it is const.


L. Spiro
It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

#9 ProgrammerDX   Members   -  Reputation: 157

Like
1Likes
Like

Posted 18 September 2013 - 06:14 AM

Afaik you can't tell the difference between a pointer and a reference once you debug the machine code in an assembler. Both are 'pointers' in there.

References are more like a compile-time pointer that disallow referring to invalid objects (ie NULL).

#10 Vortez   Crossbones+   -  Reputation: 2698

Like
0Likes
Like

Posted 18 September 2013 - 07:31 AM

Ok, thanx!






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