C++ templates template (double template?)

Question

I want to build a Stack class so the user will be able to choose which container he wants to use for the implementation of the Stack. For example, List/Vector.

Partial code:

stack.h

#ifndef STACK_H_
#define STACK_H_

template <typename T, template<typename T> class ContainerType>
class Stack{
    ContainerType<T> container;
public:
    Stack() : container(ContainerType<T>()){}

};

#endif /* STACK_H_ */

test.cpp

#include "stack.h"
#include <vector>

int main(){   
    Stack<int, std::vector<int> > stack;
    return 0;
}

Well, it doesn't compile. I get the next errors on line:

Stack<int, std::vector<int> > stack;

Errors:

expected a class template, got `std::vector<int, std::allocator<int> >' test.cpp

invalid type in declaration before ';' token test.cpp

type/value mismatch at argument 2 in template parameter 
list for `template<class T, template<class T> class ContainerType> 
class Stack' test.cpp

‪

Answer 1

First, it would be std::vector, and nothing else, because vector resides in the std namespace and you are asking for a template template parameter, while std::vector<int> is not a template anymore. Next, a std::vector actually takes two template parameters, one for the type and the other for the allocator:

template <
    typename T,
    template<typename, typename> class ContainerType,
    typename Alloc = std::allocator<T>
>
class Stack{
  ContainerType<T, Alloc> container;
  // ...
};

// usage:
Stack<int, std::vector> s;

Now, this only enables containers with two template parameters as the underlying type, so you're better off with what the standard does: take it as a normal type:

template <typename T, typename ContainerType>
class Stack{
  ContainerType container;
  // ...
};

// usage:
Stack<int, std::vector<int> > s;

To ensure that the underlying type has the same T, you can do a fake "static assert", or if you have a C++0x enabled compiler, you can do an actual static assert:

#include <tr1/type_traits> // C++03 us std::tr1::is_same
//#include <type_traits> // C++0x, use std::is_same

template <typename T, typename ContainerType>
class Stack{
  typedef typename ContainerType::value_type underlying_value_type;
  typedef char ERROR_different_value_type[
               std::tr1::is_same<T, underlying_value_type>::value ? 1 : -1
                                         ]
  ContainerType container;
  // ...
};

This works because if T is different from the used container's T, it will be a typedef char ERROR_different_vale_type[-1], and an array of negative size can't possibly exist, which causes a compiler error. :) Now, with C++0x you can just static_assert that:

#include <tr1/type_traits> // C++03
//#include <type_traits> // C++0x

template <typename T, typename ContainerType>
class Stack{
  typedef typename ContainerType::value_type underlying_value_type;
  static_assert(std::tr1::is_same<T, underlying_value_type>::value,
    "Error: The type of the stack must be the same as the type of the container");
  ContainerType container;
  // ...
};

For convenience, you can now specify a default template argument for the common case:

template <typename T, typename ContainerType = std::vector<T>>
class Stack{
  ContainerType container;
  // ...
};

// usage:
Stack<int> s;

And at this point you can just use std::stack which does exactly this (though it uses std::deque as the underlying type). :)

Answer 2

The simplest way is not to use template template parameter, because of the issue with the arity of the containers.

Instead, simply pass the full container type, and just that. Then extract the value_type (standard STL inner typedef) to get the value.

template <typename Container>
class Stack
{
public:
  typedef typename Container::value_type value_type;

private:
  Container _container;
}; // class Stack<Container>

You can then, simply, use it as Stack< std::vector<int> > and it'll contain ints.

Answer 3

As vector belongs to the std namespace, you have to qualify it. But other than that, as ContainerType is a template template parameter you need to pass a template and not a final type:

Stack<int, std::vector > stack;