Greg Baker wrote:[color=blue]
>
> 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....[/color]
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.
[color=blue]
>
> 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[/color]
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[i] = NULL;
[color=blue]
> }
>
> ~Pile() {
> // deallocate all cards in pile
> for(int i = 0; i < ncards; i++) delete [] cards[i];[/color]
This will only work, if the pointers point somewhere or are NULL.
So the assignment in the constructor is crucial for this to work.
[color=blue]
> 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];[/color]
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 );
[color=blue]
> ncards++;
> }
>
> void pop() {
> if(ncards > 0) {
> delete [] cards[ncards-1]; // deallocate top card[/color]
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;
[color=blue]
> 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];[/color]
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] );
[color=blue]
> 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[i] = 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[i]->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[i]->pop();
> if(piles[i]->isEmpty()) remove(i);
> return true;
> }
> diff -= 2;
> }
> }[/color]
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.
[color=blue]
> return false;
> }
>
> using namespace std;
>
> int main() {
> char card[2];
> while(cin >> card) {[/color]
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!
[color=blue]
> if(card[0] == '#') return 0;
>
> npiles = 0;
> piles = new Pile * [52]; // allocate space for 52 pointers
> for(int i = 0; i < 52; i++) piles[i] = new Pile(); // allocate 52
> piles[/color]
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[i] = new Pile;
.... It's much easier to see what is controlled by the for loop.
[color=blue]
>
> piles[npiles++]->push(card);
>
> for(int i = 1; i < 52; i++) {
> cin >> card;
> piles[npiles++]->push(card);
> }
>
> while(makeMove());[/color]
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() )
;
[color=blue]
>
> cout << npiles << " pile" << (npiles > 1 ? "s" : "") << " remaining:";
> for(int i = 0; i < npiles; i++) cout << " " << piles[i]->size();
> cout << endl;
>
> // finally deallocate all piles, as well as pointers to them.
> for(int i = 0; i < npiles; i++) delete piles[i];
> delete [] piles;
> }
>
> return 0;
> }[/color]
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:
kbuchegg@gascad.at Web:
www.gascad.com
Fuer sehr grosse Werte von 2 gilt: 2 + 2 = 5
