Problem with a stack...

[Mark S.]

Hi,
I'm working on the "Thinking in C++" exercises and have the problem that
while I did make the code work, I don't know why. Here is the code:

/* Use aggregate initialization to create an array of string objects.
Create a Stack to hold these strings and step through your array,
pushing each string on your Stack. Finally, pop the strings off your
Stack and print each one. */

#include "../../C04/Stack.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
string s[] = { "This ", "is ", "a ", "very strange test." };
string* sp;
Stack test;
test.initialize();
for(int i = 0; i < sizeof(s) / sizeof*(s); i++)
{
cout << "Adding " << s << endl;
test.push(new string(s)); // works
// test.push(&s); // works but crashes at the end!
}
while((sp = (string*)test.pop()) != 0)
{
cout << *sp << endl;
delete sp;
}
test.cleanup();
}

Stack.h and Stack.cpp can be found here (the exercise 6.8):
http://www.linuxtopia.org/online_books/programming_books/thinking_in_c++/Chapter04_016.html

The output is:
Adding This
Adding is
Adding a
Adding very strange test.
very strange test.
a
is
This
Stack empty

My problem is that when I use test.push(&s); instead of test.push(new
string(s)); , the program compiles and runs (output is the same), but
crashes at the end. I don't understand this - both are using the address
of a string and obviously the elements have been added successfully
since they are can be called with pop().

I did some testing and it looks to me (who is new at this) that the
error is here:
(sp = (string*)test.pop()) != 0

sp should be 0 when the head is empty, but somehow with &s, this
isn't the case. BUT WHY???

Thank you for your time!

Kind regards
Mark

 

[Pascal J. Bourguignon]

Hi,
I'm working on the "Thinking in C++" exercises and have the problem
that while I did make the code work, I don't know why. Here is the
code:

/* Use aggregate initialization to create an array of string
objects. Create a Stack to hold these strings and step through your
array, pushing each string on your Stack. Finally, pop the strings off
your Stack and print each one. */

#include "../../C04/Stack.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
string s[] = { "This ", "is ", "a ", "very strange test." };
string* sp;
Stack test;
test.initialize();
for(int i = 0; i < sizeof(s) / sizeof*(s); i++)
{
cout << "Adding " << s << endl;
test.push(new string(s)); // works
// test.push(&s); // works but crashes at the end!
}
while((sp = (string*)test.pop()) != 0)
{
cout << *sp << endl;
delete sp;
}
test.cleanup();
}

[...]
My problem is that when I use test.push(&s); instead of
test.push(new string(s)); , the program compiles and runs (output
is the same), but crashes at the end. I don't understand this - both
are using the address of a string and obviously the elements have been
added successfully since they are can be called with pop().

What is "the end"? If you found it exactly where it crashes, you'd
learn something.

In this case, it will crash in delete, because you are trying to
delete a memory storage that has not been allocated by new, namely the
_static_ strings allocated in the array.


Notice that std::string are designed so that you can easily copy them.
It should be O(1), and not more costly than three or four pointers copy.
The text in the strings is usually shared between two copies of the string.

std::string a="abc ... and some million characters more.";
std::string b=a; // copies only a few pointers worth of memory.

So you could store directly std::string in your stack, and avoid
allocating them dynamically.

Otherwise, if you want to use pointers, then you should be careful,
and remember where these pointers come from, either static memory or
dynamically allocated.

I did some testing and it looks to me (who is new at this) that the
error is here:
(sp = (string*)test.pop()) != 0

sp should be 0 when the head is empty, but somehow with &s, this
isn't the case. BUT WHY???

I don't think so. But there's something strange here, it's why do you
have to type cast? Oh! I see:

struct Stack {
struct Link {
void* data;
Link* next;
void initialize(void* dat, Link* nxt);
}* head;
void initialize();
void push(void* dat);
void* peek();
void* pop();
void cleanup();
};


This Stack class is not good C++. In C++, you should never have to
use void*. Rather, use templates. It is also missing a isEmpty
predicate.

template <class Element>
struct Stack {
template <class Element>
struct Link {
Element data;
Link* next;
void initialize(const Element& dat, Link* nxt);
}* head;
void initialize();
void push(const Element& dat);
bool isEmpty();
Element peek();
Element pop();
void cleanup();
};

So you can write things like:

Stack<std::string> stackOfStrings;
stackOfStrings.push(s);
if(not(stackOfStrings.isEmpty())){
std::string s=stackOfStrings.pop();
}

 

[Mark S.]

Hi,
I'm working on the "Thinking in C++" exercises and have the problem
that while I did make the code work, I don't know why. Here is the
code:

/* Use aggregate initialization to create an array of string
objects. Create a Stack to hold these strings and step through your
array, pushing each string on your Stack. Finally, pop the strings off
your Stack and print each one. */

#include "../../C04/Stack.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
string s[] = { "This ", "is ", "a ", "very strange test." };
string* sp;
Stack test;
test.initialize();
for(int i = 0; i < sizeof(s) / sizeof*(s); i++)
{
cout << "Adding " << s << endl;
test.push(new string(s)); // works
// test.push(&s); // works but crashes at the end!
}
while((sp = (string*)test.pop()) != 0)
{
cout << *sp << endl;
delete sp;
}
test.cleanup();
}

[...]
My problem is that when I use test.push(&s); instead of
test.push(new string(s)); , the program compiles and runs (output
is the same), but crashes at the end. I don't understand this - both
are using the address of a string and obviously the elements have been
added successfully since they are can be called with pop().

What is "the end"? If you found it exactly where it crashes, you'd
learn something.

How would I learn something? All I get is an apology for the
inconvenience and if I lock at the "Error Report Contens", I get a lot
of info but nothing that indicates where exactly the program crashed.

In this case, it will crash in delete, because you are trying to
delete a memory storage that has not been allocated by new, namely the
_static_ strings allocated in the array.

You mean it is trying to delete the strings in s[]?

Notice that std::string are designed so that you can easily copy them.
It should be O(1), and not more costly than three or four pointers copy.
The text in the strings is usually shared between two copies of the string.

std::string a="abc ... and some million characters more.";
std::string b=a; // copies only a few pointers worth of memory.

I understand what you are saying but that does not make sense to me:
What you are saying is that when I COPY a string, it doesn't really get
copied (O(n))???

So you could store directly std::string in your stack, and avoid
allocating them dynamically.

Yes, but the idea of this stack was to demonstrate that with this stack,
any type could be stored...I think.

Otherwise, if you want to use pointers, then you should be careful,
and remember where these pointers come from, either static memory or
dynamically allocated.

But I assumed that with the "Link* newLink = new Link;" in "void
Stack:ush(void* dat)", I would create new dynamic memory.

I did some testing and it looks to me (who is new at this) that the
error is here:
(sp = (string*)test.pop()) != 0

sp should be 0 when the head is empty, but somehow with &s, this
isn't the case. BUT WHY???

I don't think so. But there's something strange here, it's why do you
have to type cast? Oh! I see:

struct Stack {
struct Link {
void* data;
Link* next;
void initialize(void* dat, Link* nxt);
}* head;
void initialize();
void push(void* dat);
void* peek();
void* pop();
void cleanup();
};


This Stack class is not good C++. In C++, you should never have to
use void*. Rather, use templates.

I'm in chapter 7 right now and chapter 16 is templates...

It is also missing a isEmpty
predicate.

I'm sorry, I don't know what you mean.

template <class Element>
struct Stack {
template <class Element>
struct Link {
Element data;
Link* next;
void initialize(const Element& dat, Link* nxt);
}* head;
void initialize();
void push(const Element& dat);
bool isEmpty();
Element peek();
Element pop();
void cleanup();
};

So you can write things like:

Stack<std::string> stackOfStrings;
stackOfStrings.push(s);
if(not(stackOfStrings.isEmpty())){
std::string s=stackOfStrings.pop();
}

Again, I'm not sure what exactly to make of this yet. I hope I will
understand it soon.

Thank you for your reply, even though I still don't really understand it.

 

[Bart van Ingen Schenau]

[...]
My problem is that when I use test.push(&s); instead of
test.push(new string(s)); , the program compiles and runs (output
is the same), but crashes at the end. I don't understand this - both
are using the address of a string and obviously the elements have been
added successfully since they are can be called with pop().

What is "the end"?  If you found it exactly where it crashes, you'd
learn something.

How would I learn something? All I get is an apology for the
inconvenience and if I lock at the "Error Report Contens", I get a lot
of info but nothing that indicates where exactly the program crashed.

I have never found those Windows error reports any useful either.
What Pascalprobably meant was: At which point in your program (judging
by the output that it produced) did Windows decide that your program
had done something seriously wrong (wrong enough to create an error
report)?

What often also helps in locating the cause of a crash is to run your
program under the control of a debugger. The advantage is that the
debugger freezes the state of your program at the point where it
crashes and allows you to inspect that state. This way you can see the
exact instruction that caused the crash and the contents of the stack.

In this case, it will crash in delete, because you are trying to
delete a memory storage that has not been allocated by new, namely the
_static_ strings allocated in the array.

You mean it is trying to delete the strings in s[]?

Yes.
If the pointers you present to push() were not obtained from new, then
you *must not* call delete on the pointers that pop() returns.

When you are using new/new[] and delete/delete[], for every call to
new that is executed, there must be exactly one corresponding call to
delete (and similarly for new[] and delete[]).
In your non-working version, you had commented out the calls to new
but not those to delete.

I understand what you are saying but that does not make sense to me:
What you are saying is that when I COPY a string, it doesn't really get
copied (O(n))???

The truth is a bit more complicated than that.
There are essentially two ways to implement std::string:
1. Each std::string object has its own buffer with the string
contents.
2. std::string objects that represent the same string share one common
buffer. Copies of the buffer are made on-demand.

With style 1, copying a string implies also copying the contents,
which is an O(n) operation.
With style 2, copying a string only copies some bookkeeping data and
is very cheap, but a potential write to a string triggers a copy of
the string contents.

For technical reasons, essentially all implementations of std::string
are nowadays of style 1 and I am not aware of any serious performance
issues with that choice. Compilers are fairly good at optimising
unneeded copies.

I'm in chapter 7 right now and chapter 16 is templates...

I hope the book revisits the Stack examples then and shows how
templates can really help you.
Until then, just be very careful when you use the Stack class. It is
easy to make mistakes that the compiler can't pick up for you.

I'm sorry, I don't know what you mean.

A predicate is a function that returns a boolean value, telling you if
something is true or false.
Pascal expected this member-function to exist:
bool Stack::isEmpty() const
{
if (head == 0)
return true;
else
return false;
}

The reason is that it is usually incorrect to call pop() on an empty
stack.

Bart v Ingen Schenau

 

[Mark S.]

[...]
My problem is that when I use test.push(&s); instead of
test.push(new string(s)); , the program compiles and runs (output
is the same), but crashes at the end. I don't understand this - both
are using the address of a string and obviously the elements have been
added successfully since they are can be called with pop().
What is "the end"? If you found it exactly where it crashes, you'd
learn something.

How would I learn something? All I get is an apology for the
inconvenience and if I lock at the "Error Report Contens", I get a lot
of info but nothing that indicates where exactly the program crashed.

I have never found those Windows error reports any useful either.
What Pascalprobably meant was: At which point in your program (judging
by the output that it produced) did Windows decide that your program
had done something seriously wrong (wrong enough to create an error
report)?

Hmm, I don't think he meant that because I wrote that in my initial
post: "the program compiles and runs (output is the same), but crashes
at the end." Or what are you referring to?

What often also helps in locating the cause of a crash is to run your
program under the control of a debugger. The advantage is that the
debugger freezes the state of your program at the point where it
crashes and allows you to inspect that state. This way you can see the
exact instruction that caused the crash and the contents of the stack.

That sounds good. At the moment I'm programming with a simple editor
(Textpad) and MinGW. I know there is the GDB, but to be honest I don't
know what to do there. *blush*

In this case, it will crash in delete, because you are trying to
delete a memory storage that has not been allocated by new, namely the
_static_ strings allocated in the array.

You mean it is trying to delete the strings in s[]?

Yes.
If the pointers you present to push() were not obtained from new, then
you *must not* call delete on the pointers that pop() returns.

When you are using new/new[] and delete/delete[], for every call to
new that is executed, there must be exactly one corresponding call to
delete (and similarly for new[] and delete[]).
In your non-working version, you had commented out the calls to new
but not those to delete.

I think I understand now. Since the element in the Stack only points to
the data, two items were dynamically created so that two can be deleted
(the element and the data). My main error was that I confused this a
little the the Stash, which is also a big part of the book.

The truth is a bit more complicated than that.
There are essentially two ways to implement std::string:
1. Each std::string object has its own buffer with the string
contents.
2. std::string objects that represent the same string share one common
buffer. Copies of the buffer are made on-demand.

With style 1, copying a string implies also copying the contents,
which is an O(n) operation.
With style 2, copying a string only copies some bookkeeping data and
is very cheap, but a potential write to a string triggers a copy of
the string contents.

For technical reasons, essentially all implementations of std::string
are nowadays of style 1 and I am not aware of any serious performance
issues with that choice. Compilers are fairly good at optimising
unneeded copies.

Ahh, that makes sense now. Thank you for explaining!

I hope the book revisits the Stack examples then and shows how
templates can really help you.
Until then, just be very careful when you use the Stack class. It is
easy to make mistakes that the compiler can't pick up for you.

Alright, I will keep this in mind.

A predicate is a function that returns a boolean value, telling you if
something is true or false.
Pascal expected this member-function to exist:
bool Stack::isEmpty() const
{
if (head == 0)
return true;
else
return false;
}

The reason is that it is usually incorrect to call pop() on an empty
stack.

But this check is implemented in the peek() and pop() functions. Did he
mean that this should have been split up?

Kind regards
Mark

 

[SG]

That sounds good. At the moment I'm programming with a simple editor
(Textpad) and MinGW. I know there is the GDB, but to be honest I don't
know what to do there. *blush*

Since you're using MinGW you might want to try Code::Blocks. I was
pleasently surprized with the integration of GDB with the Code::Blocks
IDE. It's not as good as it could be but it's better than fumbling
around with GDB directly, IMHO.


Cheers!
SG

 

[highegg]

The truth is a bit more complicated than that.
There are essentially two ways to implement std::string:
1. Each std::string object has its own buffer with the string
contents.
2. std::string objects that represent the same string share one common
buffer. Copies of the buffer are made on-demand.

With style 1, copying a string implies also copying the contents,
which is an O(n) operation.
With style 2, copying a string only copies some bookkeeping data and
is very cheap, but a potential write to a string triggers a copy of
the string contents.

For technical reasons, essentially all implementations of std::string
are nowadays of style 1 and I am not aware of any serious performance
issues with that choice.

That may only be true if you don't count GCC within "essentially all",
because it uses the second style. It has the big advantage that
std::string can be efficiently passed around by values, at the cost of
making an uniqueness check on write access.

Compilers are fairly good at optimising
unneeded copies.

No, they're not *that* good. They can't optimize out a copy stored in
a container or at some other "permanent" place. OTOH, they're even
better at optimizing out repeated uniqueness checks that occur in the
shared-memory implementation.

 

[Bart van Ingen Schenau]

That may only be true if you don't count GCC within "essentially all",
because it uses the second style. It has the big advantage that
std::string can be efficiently passed around by values, at the cost of
making an uniqueness check on write access.

To my knowledge, recent GCC versions don't use cow-strings anymore,
because the uniqueness test became prohibitively expensive with the
support for multiple threads.
Additionally, it is very hard for cow-strings to meet the performance
requirements that the standard requires. In particular,
std::string::begin() can give write-access to the string contents but
should be a constant-time operation. That does not fit well with the
concept of cow.

Bart v Ingen Schenau

 

[Bart van Ingen Schenau]

But this check is implemented in the peek() and pop() functions. Did he
mean that this should have been split up?

No, he meant that the user of Stack should have the ability to make
the same test.
There are various ways in which a stack class can be designed. What
sets your Stack class apart from most of the others is that your class
allows the user to call pop() on an empty stack and it will give a
sensible answer back.

peek() on the other hand can not be called on an empty stack. This can
be seen by the require(...) call in peek(). If the condition in the
require is not met, then peek will not return normally (it will either
abort or throw an exception).

A normal stack implementation has the following functions (regarless
of the language used to implement the stack):
- A function to push a new item on top
- A function to remove the topmost item
- A function to inspect/access the topmost item without changing the
stack
- A function to test if there is anything contained in the stack
You were missing that last one.

Kind regards
        Mark

Bart v Ingen Schenau

 

[highegg]

To my knowledge, recent GCC versions don't use cow-strings anymore,
because the uniqueness test became prohibitively expensive with the
support for multiple threads.

How recent? Looking at g++ 4.3 header files, the sharing seems to be
there, and it doesn't seem to be conditional based on multithreading.
Also, I don't see it mentioned in 4.4 changes, and I hope they would
do if they changed it. Can you give references?

Additionally, it is very hard for cow-strings to meet the performance
requirements that the standard requires. In particular,
std::string::begin() can give write-access to the string contents but
should be a constant-time operation.

Whoa, since when? AFAIK the only complexity requirement in the C++98
standard is that std::string::swap should be a constant-time
operation.
Has this changed in C++0x? Can you give some references?

 

[Mark S.]

Since you're using MinGW you might want to try Code::Blocks. I was
pleasently surprized with the integration of GDB with the Code::Blocks
IDE. It's not as good as it could be but it's better than fumbling
around with GDB directly, IMHO.

It looks interesting (I was also considering using Visual Studio but
considering that I was hoping to make the switch to Linux at some point
in the future I was reluctant to do so). I will give it a try!

 

[Mark S.]

No, he meant that the user of Stack should have the ability to make
the same test.
There are various ways in which a stack class can be designed. What
sets your Stack class apart from most of the others is that your class
allows the user to call pop() on an empty stack and it will give a
sensible answer back.

peek() on the other hand can not be called on an empty stack. This can
be seen by the require(...) call in peek(). If the condition in the
require is not met, then peek will not return normally (it will either
abort or throw an exception).

A normal stack implementation has the following functions (regarless
of the language used to implement the stack):
- A function to push a new item on top
- A function to remove the topmost item
- A function to inspect/access the topmost item without changing the
stack
- A function to test if there is anything contained in the stack
You were missing that last one.

That's what I meant by splitting it up - having the check as a separate
function which has to be called before peek() and pop().

Cheers
Mark

 

[Pascal J. Bourguignon]

Pascal J. Bourguignon wrote:
[...]
My problem is that when I use test.push(&s); instead of
test.push(new string(s)); , the program compiles and runs (output
is the same), but crashes at the end. I don't understand this - both
are using the address of a string and obviously the elements have been
added successfully since they are can be called with pop().
What is "the end"? If you found it exactly where it crashes, you'd
learn something.
How would I learn something? All I get is an apology for the
inconvenience and if I lock at the "Error Report Contens", I get a lot
of info but nothing that indicates where exactly the program crashed.

I have never found those Windows error reports any useful either.
What Pascal probably meant was: At which point in your program (judging
by the output that it produced) did Windows decide that your program
had done something seriously wrong (wrong enough to create an error
report)?

Hmm, I don't think he meant that because I wrote that in my initial
post: "the program compiles and runs (output is the same), but crashes
at the end." Or what are you referring to?

Well, what I meant was more clearly explained in the following
paragraph of Bart's answer (by the way, thanks Bart!). The problem is
that when a "crash" occurs, the program is terminated so it's the end
for the process, but the "crash" usually doesn't occur at the end of
the program (when it calls exit()), but earlier. Moreover with C++,
destructors may be automatically called "at the end", so when you
reach the closing bracket, there may still be a lot of processing
pending (the C++ compiler inserts there the destructions). So this
formulation, "at the end" is actually totally ambiguous. The program
"crashes", ie. executes an illegal operation, at a very specific
point, and this is that you must determine to know where the problem
occurs, and what may cause it.

That sounds good. At the moment I'm programming with a simple editor
(Textpad) and MinGW. I know there is the GDB, but to be honest I don't
know what to do there. *blush*

gdb myprogram.exe RET
run RET
# when it "crashes":
backtrace

Then use up and down to move up and down the stack frames, and print
to print expressions, including the contents of variables.

But this check is implemented in the peek() and pop() functions. Did
he mean that this should have been split up?

pop is a member function that always return a value.
Suppose I write:

s.push(0);s.push(1);s.push(&s);

Now s.pop() may be the address of s, 1, or 0 depending on the number
of times you call it. How do you make the difference between
s.pop()==0 because I pushed 0, and an empty stack?

You have to be able to differentiate between no data, and data is null.
An empty stack is not a stack that contains nulls.

 

[Bart van Ingen Schenau]

How recent? Looking at g++ 4.3 header files, the sharing seems to be
there, and it doesn't seem to be conditional based on multithreading.
Also, I don't see it mentioned in 4.4 changes, and I hope they would
do if they changed it. Can you give references?

No, as it seems that my memory is wrong.
However, also take a look to this bug report (especially the before-
last comment):
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21334

Whoa, since when? AFAIK the only complexity requirement in the C++98
standard is that std::string::swap should be a constant-time
operation.
Has this changed in C++0x? Can you give some references?

In C++03 clause 21.3/2 ([lib.basic.string]/3), it is stated that
basic_string conforms to the requirements of a reversible container,
as specified in clause 23.1.
Clause 23.1 Table 66 requires that the expression 'a.rbegin()' has
constant complexity and the result of 'reverse_iterator(end())'. A
similar requirement is stated for 'a.rend()'.

That is where I get the requirements for the constant-time operation
of std::string::begin() and relatives.

Bart v Ingen Schenau

 

[highegg]

No, as it seems that my memory is wrong.
However, also take a look to this bug report (especially the before-
last comment):
 http://gcc.gnu.org/bugzilla/show_bug.cgi?id=21334

I see. So there is a chance that the change will occur.

Whoa, since when? AFAIK the only complexity requirement in the C++98
standard is that std::string::swap should be a constant-time
operation.
Has this changed in C++0x? Can you give some references?

In C++03 clause 21.3/2 ([lib.basic.string]/3), it is stated that
basic_string conforms to the requirements of a reversible container,
as specified in clause 23.1.
Clause 23.1 Table 66 requires that the expression 'a.rbegin()' has
constant complexity and the result of 'reverse_iterator(end())'. A
similar requirement is stated for 'a.rend()'.

That is where I get the requirements for the constant-time operation
of std::string::begin() and relatives.

Bart v Ingen Schenau

Doesn't the same section explicitly say (in a note) that a reference-
counting implementation is permitted? The standard seems to contradict
itself a little, then. Or maybe it doesn't (I can imagine the non-
const operator actually being a proxy to cheat this around), but the
implementation in gcc is non-conforming?

In any case, this is bad news. We need the COW strings within Octave
(certain parts at least), because the COW semantics is just ubiquitous
there (and ubiquitous for the whole language).
A lot of places will suddenly slow down ... sigh. I guess we'll need
to wrap std::string and duplicate methods again.

thanks for you info

 

[Mark S.]

....

One question on the side:
How long did it take you guys to accumulate that much knowledge that you
can quote some clause in C++03 (whatever that is)?

Obviously it takes a certain intelligence to get there at all, but
still...this is almost like lawyer talk, just even more complicated! ;-)

 

[Bart van Ingen Schenau]

One question on the side:
How long did it take you guys to accumulate that much knowledge that you
can quote some clause in C++03 (whatever that is)?

C++03 refers to the 2003 release of the C++ language standard, the
definition of what C++ is.
Other abbreviations you might see are C++98 (the 1998 standard) and C+
+0x/C++1x (the upcoming standard).

How long it takes to be able to quote from the standard is no more
than a few minutes (the time it takes to obtain a copy). Being able to
understand what you are quoting takes from a few weeks to several
years, depending on the subject matter.

Obviously it takes a certain intelligence to get there at all, but
still...this is almost like lawyer talk, just even more complicated! ;-)

Actually, it *is* lawyer talk. Language lawyer talk to be precise.

Regards,
Bart v Ingen Schenau

 

[Juha Nieminen]

That may only be true if you don't count GCC within "essentially all",
because it uses the second style. It has the big advantage that
std::string can be efficiently passed around by values, at the cost of
making an uniqueness check on write access.

One operation which isn't even all that uncommon and which benefits a
lot from CoW strings is sorting a vector of strings. I can only imagine
how much overhead there is in sorting a vector of large non-CoW strings.

Fortunately the next standard will introduce tools to implement move
semantics, which can probably be used to alleviate said problem. (After
all, sorting does not need to copy elements, only to move them.)