Sign in to follow this  
Toonkides

Problems with c++? or template list ? or ???

Recommended Posts

Well, basically I am making a blackjack game. And I wanted to give it a run with the current AI in there. The game works as planned, however the biggest problem I notice is when I open taskmanager and watch the resources it consumes. It's not too bad maybe 50k per few seconds, but the thing is I'm not inserting more items into any list, I am simply shuffling cards from one list to another. I have tried running the game for more than a minute then deleting all the lists and I still have a 'leak' or whatever it is. There is a lot of computation and checking involved in the code; I guess my question is : does this computation take up memory within windows ? Could my memory leaks be due to the fact that I am removing an item from one list and inserting into another (which probably assigns a new address ?) I'm stumped, and I know this will be a problem if I ever decide to run more than 1mil games. Thanks in advance

Share this post


Link to post
Share on other sites
Wow, now tell me if this makes sense. I am running the game to play 1million games while I was typing the above post. And when I looked at taskmanager after posting i noticed that from 2.5k resources it went to 896k, what happened?

The game is still running this is just wierd. I'm confused, anyways thanks again

Share this post


Link to post
Share on other sites
50k sounds like quite a bit for a simple Black Jack game. What library are you using to program this?

Also, it is hard to tell you what is wrong without seeing some code. Paste some code where you think the error is at. Have you tried using software like Glowcode that will tell you where the leak is? Or, you could simply overload the new and delete operators and keep track that way.

Share this post


Link to post
Share on other sites
gonna try glowcode;
I think windows just took too long to update the task manager, that's why it seemed to eat up much memory.

The code has been tested for over a few hours--i'm 95% sure the code is not the problem. If my template list is bad, then that could be the problem

Share this post


Link to post
Share on other sites
Quote:
Original post by Toonkides
If my template list is bad, then that could be the problem


Is is a homebrewed list class or the standard C++ list class?

Share this post


Link to post
Share on other sites
Calling _CrtDumpMemoryLeaks right before your program exits can be very useful when tracking down memory leaks. It will tell you what blocks of memory haven't been deleted yet, and what file they were allocated in. Look it up in your C++ library documentation.

Share this post


Link to post
Share on other sites
unless the ADT was written wrong, I don't see where the problem is.


//-------------------------------------------------------------
// Header for cList.h
// ADT List - Pointer based implementation -- TEMPLATE VERSION
//-------------------------------------------------------------

#ifndef __CLIST_H__
#define __CLIST_H__

template <class T> struct listNode;
template <class T> class cList
{
public:
cList(); // constructor
cList(const cList<T>& L); // copy constructor
virtual ~cList(); // destructor

void createList(); // creates an empty list
void destroyList(); // destroys the list
void copyList(const cList<T> &L); // copys a list
bool isEmpty() const; // returns true if list is empty
int getLength() const; // returns length of the list
void insert(int position,T newItem,bool &success); // inserts item from position x in list
void replace(int position,T newItem,bool &success); // replace item from list at position x with new item
void remove(int position,bool &success); // removes item from position x in list
void retrieve(int position,T &dataItem,bool &success); // retrives an item from position x in list

private:
int listLength; // length of the list
listNode<T> *head; // the pointer to the head of the list
listNode<T> *find(int position) const; // returns pointer to position in list
};
#include "cList.cpp"
#endif















//-----------------------------------------------------------
// Implementation for cList.h
//-----------------------------------------------------------

#include<stddef.h> // for NULL
#include<assert.h> // for assert

template <class T>
struct listNode // node structure
{
T item; // current item of the list
listNode<T> *next; // pointer to next node in list
listNode<T> *previous; // pointer to previous node in list
};

template <class T>
cList<T>::cList()
{
createList(); // create an empty list
}
template <class T>
cList<T>::cList(const cList &L)
{
copyList(L) ;
}
template <class T>
cList<T>::~cList()
{
destroyList(); // destroys the list
}

template <class T>
void cList<T>::createList() // creates an empty list
{
head=new listNode<T>;
head->next=NULL;
head->previous=NULL;
listLength=0;
}
template <class T>
void cList<T>::destroyList() // destroys the list
{
bool success;
while(!isEmpty())
remove(1,success);
}
template <class T>
void cList<T>::copyList(const cList &L) // copies the list
{
if(L.head==NULL) // list to copy is empty
head=NULL;
else
{
// copy first node
head = new listNode<T>;
assert(head!=NULL); // check allocation
head->item=L.head->item;

//copy rest of the list
listNode<T> *newPtr=head; // create pointer and set to head
for(listNode<T> *origPtr=L.head->next;origPtr!=NULL;origPtr=origPtr->next)
{
newPtr->next=new listNode<T>; // create new node
assert(newPtr->next!=NULL); // check allocation
newPtr=newPtr->next; // go to next node
newPtr->item=origPtr->item; // copy item
}
newPtr->next=NULL;
}
listLength = L.getLength() ;
}
template <class T>
bool cList<T>::isEmpty() const // returns true if list is empty
{
return bool(listLength==0);
}
template <class T>
int cList<T>::getLength() const // returns length of the list
{
return listLength;
}
template <class T>
listNode<T>* cList<T>::find(int position) const
{
if((position<1)||(position>getLength()))
return NULL;
else
{
listNode<T> *cur=head;
for(int i=1;i<position;i++)
cur=cur->next;
return cur;
}
}
template <class T>
void cList<T>::insert(int position,T newItem,bool &success) // inserts item from position x in list
{
listNode<T> *prev;
listNode<T> *last;
listNode<T> *newPtr;
int newLength=getLength()+1;

success=bool(position>0&&position<=newLength);

if(success)
{
// create a new node and place item in it
newPtr=new listNode<T>;
success=bool(newPtr!=NULL);
if(success)
{
listLength=newLength;
newPtr->item=newItem;

// attach new node to list
if(position==1)
{
newPtr->previous=NULL;
newPtr->next=head;
if(getLength()>1) // if the current list is greater than one
newPtr->next->previous=newPtr;
head=newPtr;
}
else if(position==getLength()||position==getLength()+1) // if we are at the end of the list
{
newPtr->next=NULL;
last=find(getLength()-1);
newPtr->previous=last;
last->next=newPtr;
}
else
{
prev=find(position-1);
// insert new node after node
// to which prev points
newPtr->next=prev->next;
newPtr->previous=prev;
newPtr->next->previous=newPtr;
prev->next=newPtr;
}
}
}
}
template <class T>
void cList<T>::replace(int position,T newItem,bool &success)
{
listNode<T> *newPtr;
success=bool(position>0&&position<=getLength());

if(success)
{
newPtr=find(position);
newPtr->item=newItem;
}
}
template <class T>
void cList<T>::remove(int position,bool &success)
{
listNode<T> *cur;
listNode<T> *prev;

success=bool(position>0&&position<=getLength());
if(success)
{
listLength--;
if(position==1)
{
cur=head;
head=head->next;
if(head!=NULL)
head->previous=NULL;
}
else
{
prev=find(position-1);
cur=prev->next;
prev->next=cur->next;
if(position-1<getLength())
cur->next->previous=prev;
}
}
cur->next=NULL;
cur->previous=NULL;
delete cur;
}
template <class T>
void cList<T>::retrieve(int position,T &dataItem,bool &success)
{
listNode<T> *printPtr;

success=bool(position>0&&position<=getLength());
if(success)
{
printPtr=find(position);
dataItem=printPtr->item;
}
}


Share this post


Link to post
Share on other sites
Quote:
Original post by Toonkides
homebrewed template, from an ADT list in a book, thought it looked right when i did it, but now i have doubts


use the standard library list, trust us its better than what you've got there, take alook here

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
use the standard library list, trust us its better than what you've got there, take alook here

Not the best advice, he should be able to get a linked-list working. If he just wanted more features, then sure.

Toonkides: just from a quick glance....
1) Why does an empty list contain a node? It looks like this has lead to several inconsitencies in your code.
2) 1-based indexing is odd in C, that could lead to mistakes if your not careful.
3) All the special cases you have for the head/tail of the list indicate that you need to rethink the design.
4) createList() will leak anything currently in the list
5) destroyList() will not destroy the head node created in createList() (or copyList() for that matter), since on creation the list contains a node when listLength==0
6) If your list is storing pointers replace() and remove() could leak memory.
7) A whole lot of bad stuff.... [sad]

It's probably worth you taking a look at a linked-list tutorial.

Share this post


Link to post
Share on other sites
Quote:
Original post by joanusdmentia
If he just wanted more features, then sure.


Well i never suggested it because of features, it isn't to do with that.

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
Quote:
Original post by joanusdmentia
If he just wanted more features, then sure.


Well i never suggested it because of features, it isn't to do with that.

Sorry, wasn't implying that you did. I was just meaning that deferring to the STL for a linked-list because he can't get a basic implementation working himself isn't a good idea.

Share this post


Link to post
Share on other sites
Lot of helpful info, and yes I have decided to convert it to the STL. I always wanted to learn this, but never got around to it, so now I go through the painful process :).

I see in the STL list you can retrieve a node based on the contents of the node. Is it possible to retrieve a node based on the position within the list ?

for eg :
let's say i want the 10th element, can I retrieve it by doing something like this :
(*loc_iter + 10) ?

tia

Share this post


Link to post
Share on other sites
You can't just add ten to the iterator since list does not support random access iterators, but you could do:
std::list<Type>::iterator iterator = myList.begin();
std::advance(iterator, 10);
doSomething(*iterator);

However, saying that an item will be in the tenth position in a list implies that you know that the structure is fairly static. Wanting to retrieve that item means you want some kind of random access. In these cases a deque or vector may be a better choice.

Enigma

Share this post


Link to post
Share on other sites
For linked lists, I think you can only move an iterator by one element at a time. If you want a list with random access, you should probably try an STL vector. Vectors are implemented with a resizable array and its members can be accessed through an iterator or by its index. Otherwise, they work very similarly to a linked list.

For example:

void MyFunc() {
vector<int> myList;

myList.push_back(0);
myList.push_back(1);
myList.push_back(100);
myList.push_back(20);

int i = myList[2]; //i == 100
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Toonkides
I see in the STL list you can retrieve a node based on the contents of the node. Is it possible to retrieve a node based on the position within the list ?


Part of the process of learning how to use the STL is to learn in which situation each container class is suitable. If you want random access (get any item you want), you'll want a vector or a deque. A list is strictly bidirectional access (move to the previous or next element).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this