CODEWITHSUNDEEP
c++stack
Nivetha
Nivetha

Reputation: 708

Stack STL with two datatypes as parameters

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;
}

What I failed to understand is, why are we mentioning stack<int, vector<int>> i.e. two data types rather than just stack<vector<int>>?

Upvotes: 4

Views: 2335

Answers (5)

CashCow
CashCow

Reputation: 31445

The reason you cannot put stack<vector<T> > to mean a stack of T using vector as the underlying class is simply because it has a different meaning, which would be a stack of vectors of T. You would expect it to mean that wouldn't you? A vector is a valid value-type for stack, you can push a vector onto the stack then pop it back... So there is no reason why the standard would (partially) specialize this particular template parameter.

Upvotes: 1

Sebastian Mach
Sebastian Mach

Reputation: 39109

The important point is that stack is not a container, but a container adapter.

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

See also What are Containers/Adapters? C++ .

For why they are not containers, check out Container Adapters do not support iterators , which exemplifies that e.g. stack does not provide iterators.

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

template <typename T, template <typename, typename> class Seq >
struct stack {};

#include <vector>

int main () {
    stack<int, std::vector> s;
}

?"

Quick answer: This would largely reduce the capability of the adapter class.

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

Upvotes: 2

Kerrek SB
Kerrek SB

Reputation: 477408

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

There's nothing stopping you from designing your own template differently, e.g. like 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:

  1. It's not minimal and simple. If I just want a stack of ints, I have to think of a container myself and I can't just say my_stack<int>.

  2. It puts constraints on the container, namely that it expose a member type value_type. I can't say my_stack<my_insane_container<int>>.

Now, you could overcome the second complaint by something 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've just made it even more insane: The container now needs to 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 sensible.

Upvotes: 1

Anton Guryanov
Anton Guryanov

Reputation: 12467

Stack is not an STL container, but an adapter, which is one of programming patterns. In short, it means, that stack is used to wrap a container (vector or deque) to "replace" its public methods (create new public methods and hide existing). You can read more about adapter here http://en.wikipedia.org/wiki/Adapter_pattern

Upvotes: 0

John Humphreys
John Humphreys

Reputation: 39314

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

Creating a stack with two data type parameters to the template as so stack<T, Sequence> stack;

is done because the first type parameter is the type of element the stack holds, and the second type parameter is the container type used to implement the stack.

Using different container types gives you different memory allocations, benefits and drawbacks in terms of speed, etc. It's just giving you as the consumer more flexibility in terms of the type of implementation you wish to use.

From that link:

Stack is a container adaptor, meaning that it is implemented on top of some underlying container type. By default that underlying type is deque, but a different type may be selected explicitly.

Upvotes: 3

Related Questions