std::vector vs std::stack

c++ stl stack stdvector
Qix - MONICA WAS MISTREATED picture Qix - MONICA WAS MISTREATED · Sep 19, 2012 · Viewed 9.2k times · Source

What is the difference between std::vector and std::stack?

Obviously vectors can delete items within the collection (albeit much slower than list) whereas the stack is built to be a LIFO-only collection.

However, are stacks faster for end-item manipulation? Is it a linked list or dynamically re-allocated array?

I can't find much information about stacks, but if I'm picturing them correctly (they are similar to an actual thread stack; push, pop, etc. - along with that top() method) then they seem perfect for window-stacking management.

Answer

Nicol Bolas picture Nicol Bolas · Sep 19, 2012

A stack is not a container; it is a container adapter. It has a vector, deque or similar container that it stores as a member that actually holds the elements. Remember: it is declared as:

template<
    class T,
    class Container = std::deque<T>
> class stack;

All stack does is limit the user interface to this internal container. The performance characteristics of the operations are exactly whatever the underlying container's performance characteristics are.

Related questions

When vectors are allocated, do they use memory on the heap or the stack?

Are all of the following statements true? vector<Type> vect; //allocates vect on stack and each of the Type (using std::allocator) also will be on the stack vector<Type> *vect = new vector<Type>; //…

Read More
Stack-buffer based STL allocator?

I was wondering if it practicable to have an C++ standard library compliant allocator that uses a (fixed sized) buffer that lives on the stack. Somehow, it seems this question has not been ask this way yet on SO, although …

Read More
How do I iterate `std::stack` elements in a for loop?

I'm writing a FIR filter that is supposed to calculate running average of an input sequence. class RunningAverager { public: RunningAverager(uint64_t FilterOrder) { for (uint64_t i=0; i<FilterOrder; i++) { Registers.push(0); } } uint64_t GetAverage(uint64_t NewInput) { Registers.…

Read More