Can you help me find my memory leak?

[Greg Baker]

I don't know what standard protocol is in this newsgroup. Am I allowed to
post code and ask for help? I hope so..

Here's my problem: I am trying problem 127 of the valladolid online
contests (http://online-judge.uva.es/p/v1/127.html). The program I wrote
seems to work fine, but it takes way too much memory to run. I am not that
good at programming C++, unfortunately, so I can't seem to find my memory
leak. As far as I can tell, I am deallocating every bit of memory I am
allocating. If someone can skim through my code to help I'd be forever
grateful. It is not that long....

I think I am doing everything correctly.

Thanks to anyone who can help!!

CODE:
#include <iostream>

// Pile class .. simple STACK implementation
class Pile {
private:
int ncards;
char **cards; // array of pointers

public:
Pile() {
ncards = 0;
cards = new char * [52]; // allocate space for 52 pointers
}

~Pile() {
// deallocate all cards in pile
for(int i = 0; i < ncards; i++) delete [] cards;
delete [] cards; // deallocate pointers
}

void push(char *card) {
// create a new char array & copy values
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];
ncards++;
}

void pop() {
if(ncards > 0) {
delete [] cards[ncards-1]; // deallocate top card
ncards--;
}
}

char* top() {
// create a new char array, copy values and return it
char *p = new char [2];
p[0] = cards[ncards-1][0];
p[1] = cards[ncards-1][1];
return p;
}

bool isEmpty()
{return (ncards == 0);}

int size()
{return ncards;}
};

int npiles;
Pile **piles; // array of pointers to piles

inline void remove(int pos) {
Pile *p = piles[pos]; // save pointer
// shuffle remaining piles
for(int i = pos; i < npiles-1; i++) piles = piles[i+1];
delete p; // deallocate empty pile
npiles--;
}

bool makeMove() { // compares cards, moves like cards, deallocates empty
piles
for(int i = 1; i < npiles; i++) {
char *cardA = piles->top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff]->top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff]->push(cardA);
piles->pop();
if(piles->isEmpty()) remove(i);
return true;
}
diff -= 2;
}
}
return false;
}

using namespace std;

int main() {
char card[2];
while(cin >> card) {
if(card[0] == '#') return 0;

npiles = 0;
piles = new Pile * [52]; // allocate space for 52 pointers
for(int i = 0; i < 52; i++) piles = new Pile(); // allocate 52
piles

piles[npiles++]->push(card);

for(int i = 1; i < 52; i++) {
cin >> card;
piles[npiles++]->push(card);
}

while(makeMove());

cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles->size();
cout << endl;

// finally deallocate all piles, as well as pointers to them.
for(int i = 0; i < npiles; i++) delete piles;
delete [] piles;
}

return 0;
}

SAMPLE INPUT:
QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C
6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C
5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD
KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS
KS
#

 

[John Harrison]

I don't know what standard protocol is in this newsgroup. Am I allowed to
post code and ask for help? I hope so..

Here's my problem: I am trying problem 127 of the valladolid online
contests (http://online-judge.uva.es/p/v1/127.html). The program I wrote
seems to work fine, but it takes way too much memory to run. I am not that
good at programming C++, unfortunately, so I can't seem to find my memory
leak. As far as I can tell, I am deallocating every bit of memory I am
allocating. If someone can skim through my code to help I'd be forever
grateful. It is not that long....

I think I am doing everything correctly.

Thanks to anyone who can help!!

CODE:
#include <iostream>

// Pile class .. simple STACK implementation
class Pile {
private:
int ncards;
char **cards; // array of pointers

public:
Pile() {
ncards = 0;
cards = new char * [52]; // allocate space for 52 pointers
}

~Pile() {
// deallocate all cards in pile
for(int i = 0; i < ncards; i++) delete [] cards;
delete [] cards; // deallocate pointers
}

void push(char *card) {
// create a new char array & copy values
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];
ncards++;
}

void pop() {
if(ncards > 0) {
delete [] cards[ncards-1]; // deallocate top card
ncards--;
}
}

char* top() {
// create a new char array, copy values and return it
char *p = new char [2];
p[0] = cards[ncards-1][0];
p[1] = cards[ncards-1][1];
return p;
}

bool isEmpty()
{return (ncards == 0);}

int size()
{return ncards;}
};

int npiles;
Pile **piles; // array of pointers to piles

inline void remove(int pos) {
Pile *p = piles[pos]; // save pointer
// shuffle remaining piles
for(int i = pos; i < npiles-1; i++) piles = piles[i+1];
delete p; // deallocate empty pile
npiles--;
}

bool makeMove() { // compares cards, moves like cards, deallocates empty
piles
for(int i = 1; i < npiles; i++) {
char *cardA = piles->top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff]->top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff]->push(cardA);
piles->pop();
if(piles->isEmpty()) remove(i);
return true;
}
diff -= 2;
}
}
return false;
}

using namespace std;

int main() {
char card[2];
while(cin >> card) {
if(card[0] == '#') return 0;

npiles = 0;
piles = new Pile * [52]; // allocate space for 52 pointers
for(int i = 0; i < 52; i++) piles = new Pile(); // allocate 52
piles

piles[npiles++]->push(card);

for(int i = 1; i < 52; i++) {
cin >> card;
piles[npiles++]->push(card);
}

while(makeMove());

cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles->size();
cout << endl;

// finally deallocate all piles, as well as pointers to them.
for(int i = 0; i < npiles; i++) delete piles;
delete [] piles;
}

return 0;
}

SAMPLE INPUT:
QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C
6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C
5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD
KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS
KS
#

Well you call top at least twice without freeing the memory returned.

There is also far to much memory allocation in this code. Allocating fixed
size chars arrays is not a good use of dynamic memory allocation especially
when the fixed size is only 2!

john

 

[Greg Baker]

Hi John. Thanks for your reply. I actually completed the problem using
static memory.. However, my misunderstanding of dynamic memory wants me to
figure this out.

I fixed the __top__ problem, and it cut my memory consumption by a lot...
Stupid me...

Thanks again!

I don't know what standard protocol is in this newsgroup. Am I allowed to
post code and ask for help? I hope so..

Here's my problem: I am trying problem 127 of the valladolid online
contests (http://online-judge.uva.es/p/v1/127.html). The program I wrote
seems to work fine, but it takes way too much memory to run. I am not that
good at programming C++, unfortunately, so I can't seem to find my memory
leak. As far as I can tell, I am deallocating every bit of memory I am
allocating. If someone can skim through my code to help I'd be forever
grateful. It is not that long....

I think I am doing everything correctly.

Thanks to anyone who can help!!

CODE:
#include <iostream>

// Pile class .. simple STACK implementation
class Pile {
private:
int ncards;
char **cards; // array of pointers

public:
Pile() {
ncards = 0;
cards = new char * [52]; // allocate space for 52 pointers
}

~Pile() {
// deallocate all cards in pile
for(int i = 0; i < ncards; i++) delete [] cards;
delete [] cards; // deallocate pointers
}

void push(char *card) {
// create a new char array & copy values
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];
ncards++;
}

void pop() {
if(ncards > 0) {
delete [] cards[ncards-1]; // deallocate top card
ncards--;
}
}

char* top() {
// create a new char array, copy values and return it
char *p = new char [2];
p[0] = cards[ncards-1][0];
p[1] = cards[ncards-1][1];
return p;
}

bool isEmpty()
{return (ncards == 0);}

int size()
{return ncards;}
};

int npiles;
Pile **piles; // array of pointers to piles

inline void remove(int pos) {
Pile *p = piles[pos]; // save pointer
// shuffle remaining piles
for(int i = pos; i < npiles-1; i++) piles = piles[i+1];
delete p; // deallocate empty pile
npiles--;
}

bool makeMove() { // compares cards, moves like cards, deallocates empty
piles
for(int i = 1; i < npiles; i++) {
char *cardA = piles->top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff]->top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff]->push(cardA);
piles->pop();
if(piles->isEmpty()) remove(i);
return true;
}
diff -= 2;
}
}
return false;
}

using namespace std;

int main() {
char card[2];
while(cin >> card) {
if(card[0] == '#') return 0;

npiles = 0;
piles = new Pile * [52]; // allocate space for 52 pointers
for(int i = 0; i < 52; i++) piles = new Pile(); // allocate 52
piles

piles[npiles++]->push(card);

for(int i = 1; i < 52; i++) {
cin >> card;
piles[npiles++]->push(card);
}

while(makeMove());

cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles->size();
cout << endl;

// finally deallocate all piles, as well as pointers to them.
for(int i = 0; i < npiles; i++) delete piles;
delete [] piles;
}

return 0;
}

SAMPLE INPUT:
QD AD 8H 5S 3H 5H TC 4D JH KS 6H 8S JS AC AS 8D 2H QS TS 3S AH 4H TH TD 3C
6S
8C 7D 4C 4S 7S 9H 7C 5D 2S KD 2D QH JD 6D 9D JC 2C KH 3D QC 6C 9S KC 7H 9C
5C
AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AD 2D 3D 4D 5D 6D 7D 8D TD 9D JD QD
KD
AH 2H 3H 4H 5H 6H 7H 8H 9H KH 6S QH TH AS 2S 3S 4S 5S JH 7S 8S 9S TS JS QS
KS
#

Well you call top at least twice without freeing the memory returned.

There is also far to much memory allocation in this code. Allocating fixed
size chars arrays is not a good use of dynamic memory allocation especially
when the fixed size is only 2!

john

 

[David White]

Hi John. Thanks for your reply. I actually completed the problem using
static memory..

Well, I hope that doesn't become a habit. Static data, unless it is const,
is usually a bad idea. Static variables are wasteful of memory, make any
code that uses them non-re-entrant, and tie the code down to specific
variables instead of any of your choice. Nothing in your program calls for
any static variables, including the static variables you already had
('npiles' and 'piles'). Maybe for your particular purpose it doesn't matter,
but in normal circumstances a programmer would be willing to do just about
anything before declaring a variable static.

DW

 

[Karl Heinz Buchegger]

I don't know what standard protocol is in this newsgroup. Am I allowed to
post code and ask for help? I hope so..

Here's my problem: I am trying problem 127 of the valladolid online
contests (http://online-judge.uva.es/p/v1/127.html). The program I wrote
seems to work fine, but it takes way too much memory to run. I am not that
good at programming C++, unfortunately, so I can't seem to find my memory
leak. As far as I can tell, I am deallocating every bit of memory I am
allocating. If someone can skim through my code to help I'd be forever
grateful. It is not that long....

The most important thing is:
don't do the allocations by yourself.
In your class it seems you want an array of strings.
So start with

std::vector< std::string > cards;

and the vector and the string will manage all the memory by themselfs

But on to your actual program.

I think I am doing everything correctly.

Thanks to anyone who can help!!

CODE:
#include <iostream>

// Pile class .. simple STACK implementation
class Pile {
private:
int ncards;
char **cards; // array of pointers

public:
Pile() {
ncards = 0;
cards = new char * [52]; // allocate space for 52 pointers

Note: all those pointers have undefined values. They point anywhere.
So you have to assign some values to them:

for( int i = 0; i < 52; ++i )
cards = NULL;

}

~Pile() {
// deallocate all cards in pile
for(int i = 0; i < ncards; i++) delete [] cards;

This will only work, if the pointers point somewhere or are NULL.
So the assignment in the constructor is crucial for this to work.

delete [] cards; // deallocate pointers
}

void push(char *card) {
// create a new char array & copy values
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];

That's not a good idea. let push figure out the length of the passed
string and deal with that instead of assuming it has a length of 2.

int len = strlen( card );
cards[ncards] = new char [ len + 1 ];
strcpy( cards[ncards], card );

ncards++;
}

void pop() {
if(ncards > 0) {
delete [] cards[ncards-1]; // deallocate top card

It's a good idea to immediatly reset cards[ncards-1] to NULL
right now.
Otherwise the destructor of this class will try to delete the
very same memory again.

cards[ncards-1] = NULL;

ncards--;
}
}

char* top() {
// create a new char array, copy values and return it
char *p = new char [2];
p[0] = cards[ncards-1][0];
p[1] = cards[ncards-1][1];

Again: Don't assume 2 characters are sufficient. Allocate as much as you need:

char* p = new char [ strlen( cards[ncards-1] ) + 1 ];
strcpy( p, cards[ ncards-1] );

return p;
}

bool isEmpty()
{return (ncards == 0);}

int size()
{return ncards;}
};

int npiles;
Pile **piles; // array of pointers to piles

inline void remove(int pos) {
Pile *p = piles[pos]; // save pointer
// shuffle remaining piles
for(int i = pos; i < npiles-1; i++) piles = piles[i+1];
delete p; // deallocate empty pile
npiles--;
}

bool makeMove() { // compares cards, moves like cards, deallocates empty
piles
for(int i = 1; i < npiles; i++) {
char *cardA = piles->top();
int diff = (i > 2) ? 3 : 1;
while(diff > 0) {
char *cardB = piles[i-diff]->top();
if(cardA[0] == cardB[0] || cardA[1] == cardB[1]) {
piles[i-diff]->push(cardA);
piles->pop();
if(piles->isEmpty()) remove(i);
return true;
}
diff -= 2;
}
}

remember what top() did?
It allocated a new character array and returned that.
But I can't see you deleteing it somewhere in this function.

return false;
}

using namespace std;

int main() {
char card[2];
while(cin >> card) {

Oha. Looking at the input file, I can see that you intend
to store 2 characters in card. cin >> card will store them as
C style string, meaning: you will need an array size of 3 for storing
this string. Remember: a C-style string is allways terminated with
a '\0' character!

if(card[0] == '#') return 0;

npiles = 0;
piles = new Pile * [52]; // allocate space for 52 pointers
for(int i = 0; i < 52; i++) piles = new Pile(); // allocate 52
piles

May I suggest you drop the habit of writing the decendent line
on the same line even if it's only a single statement ...

for( int i = 0; i < 52; i++ )
piles = new Pile;

.... It's much easier to see what is controlled by the for loop.

piles[npiles++]->push(card);

for(int i = 1; i < 52; i++) {
cin >> card;
piles[npiles++]->push(card);
}

while(makeMove());

Same here. It often happens that somebody writes the above by accident.
To make it clear that your intent *is* an empty loop body, write:

while( makeMove() )
;

cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
for(int i = 0; i < npiles; i++) cout << " " << piles->size();
cout << endl;

// finally deallocate all piles, as well as pointers to them.
for(int i = 0; i < npiles; i++) delete piles;
delete [] piles;
}

return 0;
}

Also note: you class Pile is in need for a copy constructor and an assignment
operator. Read up on the 'rule of three' to learn why.
Even if you don't know what all this things do, you should make it a habit
to at least declare them private and don't implement them. Then the compiler
and/or linker will warn you when they are used by accident:

class Pile {
private:
int ncards;
char **cards; // array of pointers

Pile( const Pile& Arg ); // not implemented by intention
Pile& operator=( const Pile& Arg ); // not implemented by intention

public:
Pile() {
ncards = 0;
cards = new char * [52]; // al

...

--
Karl Heinz Buchegger, GASCAD GmbH
Teichstrasse 2
A-4595 Waldneukirchen
Tel ++43/7258/7545-0 Fax ++43/7258/7545-99
email: (e-mail address removed) Web: www.gascad.com

Fuer sehr grosse Werte von 2 gilt: 2 + 2 = 5