Hi, I'm implementing an undo feature into a program to store prior changes to an image, although I have my own ideas on how to do this, I heard that I should use a 'stack', so i'm wondering what exactly is a stack in c++? Thanks

Ah ok, yeah I love vectors :)

Is there much of a difference between using c++'s stack and vector?

I've only ever used vector previously.

You can implement a stack using a vector. It has the usual benefits/drawbacks of using a vector (a push_back() might cause every object in the vector to be copied).

By default, std::stack uses a deque, not a vector, and it's best to leave it that way unless you have a thorough understanding of the considerations to using vector vs deque.

Quote:Original post by johnnyBravo
Is there much of a difference between using c++'s stack and vector?

The main difference is the interface - and the fact that you get to choose which container implements the behavior.

Equivilants:std::vector        std::stackpush_back()        push()pop_back()         pop()back()             top()size()/empty()     size()/empty()everything else    n/a

Documentation

not sure, but a stack should be better performant than a vector.
Its smaller API enables more highly optimised implementation.

Whether this is true for the actual implementation you're using is of course implementation dependent!

Quote:Original post by jwenting
not sure, but a stack should be better performant than a vector.
Its smaller API enables more highly optimised implementation.

Whether this is true for the actual implementation you're using is of course implementation dependent!

A std::stack in C++ is a wrapper around another container (deque by default). That isn't implementation dependent.

Quote:Original post by jwenting
not sure, but a stack should be better performant than a vector.

All std::stack does is adapt another container (as provided via second template argument, defaulting to std::deque). std::stack< int , std::vector< int > > will obviously not outperform std::vector< int >, as the former is implemented using the later. Cases where std::stack< int > (std::deque implementation) outperform std::vector will be due to std::deque outperforming std::vector in that situation, and have nothing to do with std::vector itself.

Quote:Its smaller API enables more highly optimised implementation.

Smaller API has no direct correlation to speed. If an API requires certain restrictions which prevent certain optimization techinques from being utilized, which would indeed be used, then that argument holds merit. Since all the restrictions of the implementing container still hold, and there are very few optimizations one could layer atop*, using std::stack<T,C<T> > will be very very very very unlikely to cause a performance gain over directly using C<T> (where C is a templatized container class).

* "very very very very few" as in only 1 that I can think of, atop std::list (why the heck would you using a list for a stack?). If the implementaiton of std::list::size is O(N), allowing for std::list::splice(begin, end) to be O(1), the elimination of the later method from the visible interface would allow a std::stack to store the size of the list, causing std::stack::size to be O(1) instead of O(N) in that circumstance.

The main purpouse of std::stack is to clarify intent and how you plan to use the container, not optimization.