std::stack vs std::deque (stacked deck?)

[DevNull]

Hello everyone,
I decided to pick c++ back up after not really having used it much in
10 years.
Just as a point of refference, there was no standard C++ last time I
used regularly.

Anyways coming back, I've fallen in love with all the improvements in
the language such as the STL. Congrats to anyone who worked on it,
you did an excellent job.

To teach myself c++ again, I decided a good first project would be to
implement a scripting language against a MUD server/client system I
originally designed in C.

Thus far I've made what I feel is incredible headway, and thanks to
this newsgroup I've gotten over a number of humps.

To make a long story short, I'm a bit confused. I went head first,
and decided the std::deque would be an ideal structure for
implementing my scripting languages stack.

Now I've had a chance to look at the boost spirit library and numerous
others, and it looks like a structure called std::stack is the
preffered method of implementing alot of the things I've implemented.

But there's a problem and I can't quite get my head around it.
std::stack is a FILO object whereas std::deque at least as I'm using
it, can be FIFO or FILO. In my case, instructions go in via push_back
and get removed via pop_front making it effectively a FIFO object.
But std::stack has push and pop methods which operate only on the top
of the stack.

To me at least it seems more natural to push an object to the bottom
and pop it from the top, which means that instructions get executed in
the order they are added.

But it looks like I'm wrong here, as I said almost every example I can
find uses std::stack, can someone smarter than me (pretty much
everyone except the guy selling viagra), explain why the std::stack
implementation is considered superior so much so that I cannot find a
single example of a VM using std::deque?

Thanks in advance!

 

[robertwessel2]

Hello everyone,
I decided to pick c++ back up after not really having used it much in
10 years.
Just as a point of refference, there was no standard C++ last time I
used regularly.

Anyways coming back, I've fallen in love with all the improvements in
the language such as the STL. Congrats to anyone who worked on it,
you did an excellent job.

To teach myself c++ again, I decided a good first project would be to
implement a scripting language against a MUD server/client system I
originally designed in C.

Thus far I've made what I feel is incredible headway, and thanks to
this newsgroup I've gotten over a number of humps.

To make a long story short, I'm a bit confused. I went head first,
and decided the std::deque would be an ideal structure for
implementing my scripting languages stack.

Now I've had a chance to look at the boost spirit library and numerous
others, and it looks like a structure called std::stack is the
preffered method of implementing alot of the things I've implemented.

std::stack and std:queue are usually just specializations of
std::deque (double ended queue). They implement stacks and queues,
just like the name implies.

But there's a problem and I can't quite get my head around it.
std::stack is a FILO object whereas std::deque at least as I'm using
it, can be FIFO or FILO. In my case, instructions go in via push_back
and get removed via pop_front making it effectively a FIFO object.
But std::stack has push and pop methods which operate only on the top
of the stack.

To me at least it seems more natural to push an object to the bottom
and pop it from the top, which means that instructions get executed in
the order they are added.

If you want FIFO behavior, you want a queue. If you want LIFO (FWIW,
"FILO" is pretty rare usage), then you want a stack. If you want
both, you want a double ended queue.

std::deque support push/pop_front/back since you can work on both
ends. std::queue and std::stack only support push and pop because
there's only one end each operation applies to (the same end in the
case of a stack, opposite ends in the case of a queue). You can use a
deque as either, by using the right combination of push/pop front/back
operators, or you do both, and then a dequeue becomes more than either
a stack or a queue.

But it looks like I'm wrong here, as I said almost every example I can
find uses std::stack, can someone smarter than me (pretty much
everyone except the guy selling viagra), explain why the std::stack
implementation is considered superior so much so that I cannot find a
single example of a VM using std::deque?

Presumably because the samples want a stack (LIFO) data structure.
Also, std::stack and std::queue are a simpler to use in many cases
(although they have a number of limitations when compared to
std::deques).

 

[Victor Bazarov]

[..]
To teach myself c++ again, I decided a good first project would be to
implement a scripting language against a MUD server/client system I
originally designed in C.

Thus far I've made what I feel is incredible headway, and thanks to
this newsgroup I've gotten over a number of humps.

To make a long story short, I'm a bit confused. I went head first,
and decided the std::deque would be an ideal structure for
implementing my scripting languages stack.

Now I've had a chance to look at the boost spirit library and numerous
others, and it looks like a structure called std::stack is the
preffered method of implementing alot of the things I've implemented.

std::deque is a true container. std::stack is a container adapter.
What book are you reading that doesn't explain the difference?

But there's a problem and I can't quite get my head around it.
std::stack is a FILO object whereas std::deque at least as I'm using
it, can be FIFO or FILO. In my case, instructions go in via push_back
and get removed via pop_front making it effectively a FIFO object.
But std::stack has push and pop methods which operate only on the top
of the stack.

Well, a car can go forward or backward as the driver wants it to.
However, when towing something on a rope, going backward does not
make much sense. In that case the car only goes forward. The rope
is the additional constraint that make a bi-directional mechanism
uni-directional. A std::deque is like a car, you can use it as
a queue and push and pop from either end, or you can limit yourself
and only use one end of it (the end or the beginning). Then it
loses its bi-directionality. That's what std::stack does. It
essentially _hides_ the push_front and pop_front stuff, even if
it's available in the underlying container.

To me at least it seems more natural to push an object to the bottom
and pop it from the top, which means that instructions get executed in
the order they are added.

But that's not a stack model...

But it looks like I'm wrong here, as I said almost every example I can
find uses std::stack, can someone smarter than me (pretty much
everyone except the guy selling viagra), explain why the std::stack
implementation is considered superior so much so that I cannot find a
single example of a VM using std::deque?

Nothing is superior to anything. You can organize your std::stack to
use std::deque as the underlying container. Get a decent book and
read a bit about those things.

V

 

[kwikius]

Well, a car can go forward or backward as the driver wants it to.
However, when towing something on a rope, going backward does not
make much sense.

Hmm. I prefer the following analogy. Suppose you have a guy sitting at
a table. Now you keep feeding this guy stuff.

Important warning: BTW Its useful when performing this experiment to
use food which can be identified after it has passed through the guys
guts. For this sweetcorn is quite suitable, peas, beetroot, that sort
of thing. If you dont do this you could be wasting a lot of time
sifting the results...

Now the experiment works because its not possible for the guy to keep
eating for ever. At some point stuff has to come out..

From which end it comes out first you can tell if the guy is acting

like a queue or a stack.

regards
Andy Little

 

[DevNull]

Hmm. I prefer the following analogy. Suppose you have a guy sitting at
a table. Now you keep feeding this guy stuff.

Important warning: BTW Its useful when performing this experiment to
use food which can be identified after it has passed through the guys
guts. For this sweetcorn is quite suitable, peas, beetroot, that sort
of thing. If you dont do this you could be wasting a lot of time
sifting the results...

Now the experiment works because its not possible for the guy to keep
eating for ever. At some point stuff has to come out..


like a queue or a stack.

regards
Andy Little

The analogies are getting a bit silly. I guess in a nutshell I'm
asking a theory question that I haven't seen covered anywhere, in any
of the docs I've read.
Why is a stack implementation LIFO used instead of FIFO which appears
on the surface to make more sense.

So I created a simple test problem, using a normal source file, and
general scoping rules I wrote a simple parser.

Turns out both implementations are acceptable in a simplistic VM at
first. However, a LIFO stack gives you scoping for free!

Look at how this simple script code breaks down.

a = 1;
b = 2;
c = a + b;
print("A + B + C =", a+b+c);

Now if you have a LIFO stack, you get VM code that looks like this
(assuming exec is called automatically)

push(assign, a, 1);
pop();
push(assign, b, 1);
pop();
push(add, a,b,result);
pop();
push(assign,c,result);
pop();
push(add,a,b,result);
pop();
push(add,c,result,result);
pop();
push(funcPrint, "A + B + C ",result);
pop();


Now lets look at this example in a FIFO stack.
push(assign,a,1);
push(assign,b,2);
push(add,a,b,result);
push(assign,c,result);
push(add,a,b,result);
push(add,c,result,result);
push(funcPrint,"A + B + C",result);
pop();
pop();
pop();
pop();
pop();
pop();
pop();

As you can see scoping becomes much harder in a FIFO stack since we
have to keep pushing the result to the bottom and continue execution.
Compare this to a LIFO where scope becomes essentially an automatic
function.

Anyways I think I've managed to answer my own question on this, thanks
for the info and setting me straight on std::stack being LIFO.

When it comes down to it though I wonder if there is/was any
performance gains to using stack vs a deque in a LIFO manner, or if
it's just syntactic sugar.

Regards,

 

[=?iso-8859-1?q?Kirit_S=E6lensminde?=]

But it looks like I'm wrong here, as I said almost every example I can
find uses std::stack, can someone smarter than me (pretty much
everyone except the guy selling viagra), explain why the std::stack
implementation is considered superior so much so that I cannot find a
single example of a VM using std::deque?

Sounds like you are storing the code that is being executed in the
deque, i.e. using it as an internal representation of the program
code. This is fine, sort of... (see below). The stack is used to store
program state which is a slightly different thing.

Sounds like you have the two different things a little confused?

You don't say what the characteristics are of the scripting language,
but if it features local variables, function calls or anything like
that then a stack is the structure used to determine what values these
name have in scope at that time (this gets potentially a lot more
complex if your language has closures).

The reason why I say the deque is sort of OK for storing the program
is that it is awkward to use with any language that offers complex
control flow (or even any control flow, like if statements, loops and
function calls). You'll find a more complex structure will be easier
to work with in that case. Using it as an intermediate to queue the
next instructions (e.g. if you have some sort of operation
interleaving going on to simulate multiple threads in the script
language) is probably a good choice.


K

 

[robertwessel2]

The analogies are getting a bit silly. I guess in a nutshell I'm
asking a theory question that I haven't seen covered anywhere, in any
of the docs I've read.
Why is a stack implementation LIFO used instead of FIFO which appears
on the surface to make more sense.

I think you're confused. A stack *is* LIFO by definition. That's
what a stack is. If a data structure is not LIFO, it's not a stack.
A queue, again by definition, is FIFO. Questioning why a stack has
been implemented LIFO rather than FIFO is flatly nonsensical.

There are many applications for both stacks and queues, but they're
not usually interchangeable. A double ended queue is a generalization
of both queues and stacks.

 

[kwikius]

The analogies are getting a bit silly.

Well.. since comp.lang.c++ isnt moderated, and comp.lang.c++.moderated
takes itself way too serious, I like to try to raise the tone with
some bawdy humour from time to time

Obviously though... I failed this time :-(

So I created a simple test problem, using a normal source file, and
general scoping rules I wrote a simple parser.

<...>

Looks fun

When it comes down to it though I wonder if there is/was any
performance gains to using stack vs a deque in a LIFO manner, or if
it's just syntactic sugar.

Basically yes. Except you can theoretically replace the default
container template param with e.g your own "model" of stack etc
without changing the source code.

In which case you would then only need to provide the operations
defined for stack, without having to provide the whole interface for
more versatile containers. Thats the theory, though I generally just
stick with what I'm given...

regards
Andy Little