127 - "Accordian" Patience

[xbeanx]

Thanks again guys.

As a side note: when I add the delete [] piles line and compile it under linux using GCC I get a runtime error. However when I compile it under windows using Mingw it works fine!! ?

But I'll look at my destructor and figure it out.

[Krzysztof Duleba]

On my PC (win2k + cygwin) I get runtime error too and that's the only thing that should happen. You're trying to refer to memory that isn't allocated at all (and free it!), but apparently MinGW didn't notice that. Adding the line delete [] piles launched the destructor, which as I said is corrupt.

[xbeanx]

Hmm.. I compiled it with cygwin under Win98 and it also works.

What memory is not allocated? I mean, DO allocate the memory for piles, and in my Pile constructor I allocate memory for the data structures needed there.

I'm on my girlfriend's computer now and its really hard to fix a problem that doesn't happen (at least on this computer).

[Krzysztof Duleba]

Win98 doesn't protect the memory, systems from NT family do.

Try to change
[cpp]for(int i = 0; i < 52; i++) delete [] cards;[/cpp]
into
[cpp]for(int i = 0; i < ncards; i++) delete [] cards;[/cpp]
It should work now (I haven't tried it out, though). Do you see what was wrong?

[xbeanx]

Hmm.. No that didn't work either. I'll figure it out eventually. Funny thing is, it worked when I used malloc and free. But it doesn't with new and delete.

[Krzysztof Duleba]

Ups, now I don't know what's wrong there. You can always remove that line

[UFP2161]

[cpp]int main ()
{
char *card = new char[2];

while (cin >> card)
{
...
piles[npiles++].push(card);
....
delete [] piles;
....
}
}[/cpp]
Okay, so initially you have a pointer to a two character array stored in *card, correct? .. Okay, so then you push it into your pile .. so now the pile also has a pointer to this same two character array, correct? .. And then at the end you need to free up memory, so you call the Pile's destructor, which deletes all the cards that it contains, right? .. So what happened to the original *char pointer? (esp. think about when you try to cin >> card a second time)

If you want more substantiveproof, try adding:
[c]printf ("%p\n", card);[/c]
after you allocate the card, and when you're deleting the cards in the pile .. You should see that one of the cards in the pile will equal what was in *card .. (not sure how to output a pointer using cout...)

P.S. Also, remember that "new char*[52]" allocates an array of pointers.

[Krzysztof Duleba]

[cpp]int * a;
[...]
cout<<a;[/cpp]
will display the address of a. I guess that's what you want to do.

[UFP2161]

That doesn't work for a character pointer .. cout will just dereference them and print them out =( .. Works for most other types of pointers though =P

[Krzysztof Duleba]

You're right. For every class T (including char) you can write
[cpp]T *a;
[...]
cout<<(void*)a;[/cpp]

[xbeanx]

I still am confused as to what's happening here. With the assumption that I put a delete [] piles at the end of the while loop:

At the beginning of the while loop, 52 new piles get allocated. So, if I deallocate these at the end of the while loop, won't they get reallocated next time around?

I put a cout in the destructor of Pile, and saw it was getting called 52 times. The crash doesn't happen within the destructor. Actually, it happend the second time around in the for(i=1 to 52) loop.

This makes me wonder, if it works the first time through the while loop, why won't it work the second time around?

Here's a modified version of my program. It is cleaned up a little. If anyone knows C++ well, can he help me figure out what is wrong with my memory routines?

Also, am I right the using delete only deletes the memory allocated to a pointer, and not a pointer itself?

[cpp]#include <iostream>

class Pile {
private:
int ncards;
char **cards;

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

~Pile() {
for(char **p = cards; p < cards+ncards; p++)
delete [] *p;
delete [] cards;
}

void push(char *card) {
cards[ncards] = new char [2];
cards[ncards][0] = card[0];
cards[ncards][1] = card[1];
ncards++;
}

void pop() {
if(ncards > 0) {
char *p = cards[ncards-1];
delete [] p;
ncards--;
}
}

char* top() {
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;

inline void remove(int pos) {
for(int i = pos; i < npiles-1; i++)
piles = piles[i+1];
npiles--;
}

bool makeMove() {
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];

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(Pile *p = piles; p < piles+npiles; p++) cout << " " << p->size();
cout << endl;

delete [] piles;
}

return 0;
}[/cpp]

[UFP2161]

You're not deallocating correctly .. Well, actually, more correctly, you're trying to delete a lot of the same pointers .. Here's some code that might help you debug further this phenomena (basically, label each unique object with it's own identification code):
[cpp]static int PileID = 0;

class Pile
{
private:
int id;
...
public:
Pile ()
{
id = PileID++;
cout << "Pile(" << id << ") - constructing..." << endl;
...
}

~Pile ()
{
cout << "Pile(" << id << ") - destructing..." << endl;
...
}
}[/cpp]
You should get 52 distinct constructing and 52 distinct destructing messages, but you only get 7 distinct destructing messages (the unique 6 piles that are left, and the the empty piles) for the first set of cards. Since I'm no expert on internal C++ memory management, I can't say why doing two deletes on the same pointer doesn't 'cause an immediate crash, but that is where the problem actually lies, not necessarily in the "cin >> card" statement in the for(1..51) loop in main(). [Perhaps it only queues the deletes up somewhere and only goes deleting the memory after some other non-deletes are executed, *shrug*]

The delete function will remove the memory pointed to by a pointer. The pointer itself will remain unchanged and will continue to point to the now unallocated memory (which will 'cause unknown errors if you try to access the memory again) until you either update it to some new location, or it goes out of scope and disappears forever.

[xbeanx]

The delete function will remove the memory pointed to by a pointer. The pointer itself will remain unchanged and will continue to point to the now unallocated memory (which will 'cause unknown errors if you try to access the memory again) until you either update it to some new location, or it goes out of scope and disappears forever.

This is where I am confused.. I thought I WAS updating it at the beginning of the while loop. Specifically, piles = new Pile[52]. Wouldn't that reallocate another 52 Piles? Obviously its not, because when I try to push something on the second pile, I get the crash. However, through debugging I noticed that it successfully pushes a card on the FIRST pile. Its only when it tries to push a card on the second pile that I get a crash.

EDIT::
I also tried what you said with the id#, and found that the destructors are messed up. The same pile gets destructed many times. My question is: does anyone know how I can delete my array of piles, and reallocate them again later? Seems simple enough, huh?

[UFP2161]

Maybe it'd be better if you just stuck with some static memory allocation:
[cpp]
class Pile
{
private:
char cards[52][2];
...
public:
...
reset ()
{
ncards = 0;
}
}

Pile piles[52];[/cpp]

[xbeanx]

Yeah, that would be a lot easier. However, I'm still perplexed.

[/cpp]