CODEWITHSUNDEEP
c++data-structuresstl
John Humphreys
John Humphreys

Reputation: 39224

Stack with maximum size that overwrites C++

If I were making something like an undo stack, and I wanted to only support 30 undo operations, it would be nice to have a stack that had a maximum depth of 30.

You obviously wouldn't want the stack to restrict additions at this point, you would just want it to discard the bottom-most element when a 31st was added.

I'm aware I can mimic this kind of functionality with a list, but I was wondering if there's a way to make it happen with STL or if there are other pre-implemented options for this?

Upvotes: 0

Views: 163

Answers (5)

Seth Carnegie
Seth Carnegie

Reputation: 75130

I would use a circularly-linked list (or just a buffer that you use circularly) with 30 nodes (or elements). You would start of the top and bottom pointers at the same node, and advance the top whenever you added an element and regress it when you remove one. if you add so many elements that you reach the bottom (you have gone all the way around the loop) then you advance the top and the bottom pointer so that they don't cross each other, and overwrite the one that was under the bottom pointer (where the top pointer now points).

Another way to do it is to allocate an array (or wrap around a vector) instead of dynamically allocating memory, and modulusing your indices by 30 when you want to advance an index.

Either way, you never have to allocate or deallocate memory except at the beginning and you can handle overflowing really well. You can read the specifics at the Wikipedia page about circular buffers.

Upvotes: 6

Lucretiel
Lucretiel

Reputation: 3324

If you're willing to work outside the STL, boost has a container called circular_buffer that would be perfect for your needs: http://www.boost.org/doc/libs/1_49_0/libs/circular_buffer/doc/circular_buffer.html#briefexample

Upvotes: 1

user1236886
user1236886

Reputation: 46

I don't know if you want to do this but it seems to me like you want a circular buffer. It isn't STL afaik but it will do exactly what you want. Have a look at http://en.wikipedia.org/wiki/Circular_buffer

Upvotes: 0

Pablo
Pablo

Reputation: 8644

An std::deque or an std::list both work. You can use them as a stack by using push_back/pop_back and expire old elements with pop_front

Upvotes: 1

Mark Ransom
Mark Ransom

Reputation: 308081

I would use a std::deque and delete an element when the size gets over the limit. Of course a list would work just as well, as you have observed.

There's not a standard container to do this.

Upvotes: 1

Related Questions