STL stack with two data types as parameters

Question

This program is taken from cplusplus.com

#include <iostream> #include <vector> #include <deque> #include <stack> using namespace std; int main () { deque<int> mydeque (3,100); // deque with 3 elements vector<int> myvector (2,200); // vector with 2 elements stack<int> first; // empty stack stack<int> second (mydeque); // stack initialized to copy of deque stack<int,vector<int> > third; // empty stack using vector stack<int,vector<int> > fourth (myvector); cout << "size of first: " << (int) first.size() << endl; cout << "size of second: " << (int) second.size() << endl; cout << "size of third: " << (int) third.size() << endl; cout << "size of fourth: " << (int) fourth.size() << endl; return 0; } 

I did not understand why we mention stack<int, vector<int>> that is, two data types, not just stack<vector<int>> ?

Answer 1

Check out: http://www.sgi.com/tech/stl/stack.html

Creating a stack with two data type parameters in a template this way stack<T, Sequence> stack;

performed because the parameter of the first type is the type of the element that is stored on the stack, and the second type is the type of container used to implement the stack.

Using different types of containers gives you different memory allocations, advantages and disadvantages in terms of speed, etc. It just gives you more flexibility in terms of the type of implementation you want to use.

From this link:

A stack is a container adapter, which means that it is implemented on top of some basic type of container. By default, this base type is deque, but a different type can be selected.

Answer 2

The important point is that stack not a container and the container adapter .

In C ++, container adapters are additional interfaces for these containers. The standard containers used by adapters work well in the general case, but sometimes you can use a different underlying data structure.

See also. What are containers / adapters? C ++ .

For what they are not containers, check Container adapters do not support iterators , which illustrates this, for example. stack does not provide iterators.

---

Bonus knowledge: a template programmer may ask: "Why is the second parameter not a template template parameter, for example

 template <typename T, template <typename, typename> class Seq > struct stack {}; #include <vector> int main () { stack<int, std::vector> s; } 

? "

Quick answer: this will greatly reduce the capabilities of the adapter class.

• the adapter class will have to decide on the dispenser used by the container (the full signature of vector is std::vector<T, Alloc=...> ), so adapter users could not outline it.
• not all valid containers have the same number and types of template arguments

Answer 3

This is how standard library container templates are designed: the first argument of the template is the type of data contained (or the first two for associative containers).

Nothing prevents you from developing your own template in different ways, for example. as you suggest:

 template <typename Backend> class my_stack { public: typedef Backend container_type; typedef typename container_type::value_type value_type; private: container_type container; // ... }; 

However, this design has two drawbacks:

• It is not minimal and simple. If I need an int s stack, I have to think about the container myself, and I can't just say my_stack<int> .

• It sets restrictions on the container, namely that it exposes the element type value_type . I can not say my_stack<my_insane_container<int>> .

Now you can overcome the second complaint like this:

 template <typename> class my_crazy_stack; template <template <typename ...> class Tmpl, typename T, typename ...Args> class my_cazy_stack<Tmpl<T, Args...>> { public: typedef Tmpl<T, Args...> container_type; typedef T value_type; // ... }; 

But now you just made it even crazier: the container should now be a template (i.e., bye bye class my_specialized_int_container ), and it needs to take its value type as the first element (i.e., bye bye stack of stacks).

So, in short, the standard library design is pretty reasonable.

Answer 4

The reason you cannot put stack<vector<T> > in the value of the T stack using the vector as the base class is simply because it has a different value, which will be the T vector stack. You expect this to mean that wouldn’t it? A vector is a valid type of value for the stack, you can push the vector onto the stack and then rotate it back ... Therefore, there is no reason why the standard (partially) specializes in this particular template parameter.

Answer 5

The stack is not an STL container, but an adapter, which is one of the programming patterns. In short, this means that the stack is used to package the container ( vector or deque ) in order to “replace” its public methods (create new public methods and hide existing ones). You can learn more about the adapter here http://en.wikipedia.org/wiki/Adapter_pattern