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.

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;
  }
...

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

(const DataT *d)

is the same as (const DataT& d)

right?

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

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?

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

Ok, thanx!