c++ - Template template parameters

Question

It seems understanding template template parameters will kill me :(, Let me explain what misconception I made in my mind which confuses me:

template<class T>
class B {}; // A templated class

Here is other code:

template<template<class X> class Z = B> // The problem is in this line for me
class BB{};

Note the line in the parameter list of templated class BB, which is:

template<class X> class Z = B

Now, what stops C++ to think that Z is not another templated class Z?

I.e.,

template<class X> class Z {
}

rather than thinking class Z is a templated parameter itself.

Answer 1

Mankarse has answered your question, but I thought I'd chime in anyway.

Template template parameters are just like normal template type parameters, except that they match templates instead of concrete types:

// Simple template class
template <typename Type>
class Foo
{
    Type m_member;
};

// Template template class
template <template <typename Type> class TemplateType>
class Bar
{
    TemplateType<int> m_ints;
};

If it helps, you can kind of think of them as like function pointers. Normal functions just accept arguments like normal templates just accept types. However, some functions accept function pointers which accept arguments, just like template template types accept templates that accept types:

void foo(int x)
{
    cout << x << endl;
}

void bar(void (*f)(int))
{
    f(1);
    f(2);
}

To answer your question in the comments: template template template parameters are not possible. However, the reason they are not possible is just because the standardisation committee decided that template templates were enough, probably to make lives easier for the compiler implementors. That being said, there's nothing stopping the committee from deciding that they are possible, then things like this would be valid C++:

template <template <template <typename> class> class TemplateTemplateType>
class Baz
{
    TemplateTemplateType<Foo> m_foos;
};

typedef Baz<Bar> Example;
// Example would then have Bar<Foo> m_foos;
// which would have Foo<int> m_ints;

Again, you can see parallels in function pointers.

                      types <=> values
                  templates <=> functions of values
         template templates <=> functions of functions of values
template template templates <=> functions of functions of functions of values

The analogous function to Baz would be:

void baz(void (*g)(void (*f)(int)))
{
    g(foo);
}

Where would you use a template template template?

It's pretty far-fetched but I can think of one example: a really generic graph searching library.

Two common algorithms in graph searching are the depth-first search (DFS) and the breadth-first search (BFS). The implementation of the two algorithms is identical except in one regard: DFS uses a stack of nodes whereas BFS uses a queue. Ideally, we'd just write the algorithm once, with the stack/queue as an argument. Also, we'd want to specify the implementation container of the stack or queue, so that we could do something like:

search<Stack, Vector>( myGraph ); // DFS
search<Queue, Deque>( myGraph ); // BFS

But what is a Stack or a Queue? Well, just like in the STL a stack or a queue can be implemented with any kind of container: vectors, deques, lists etc. and could also be stacks of any element type, so our stacks or queues would have the interface:

Stack<Vector, int> // stack of ints, using a vector implementation
Queue<Deque, bool> // queue of bools, using a deque implementation

But Vector and Deque themselves are template types!

So finally, our Stack would be a template template like:

template <template <typename> class Storage, typename Element>
struct Stack
{
    void push(const Element& e) { m_storage.push_back(e); }
    void pop() { m_storage.pop_back(); }
    Storage<Element> m_storage;
};

And our search algorithm would then have to be a template template template!

template <template <template <typename> class, typename> class DataStructure,
          template <typename> class Storage,
          typename Graph>
void search(const Graph& g)
{
    DataStructure<Storage, typename Graph::Node> data;
    // do algorithm
}

That would be pretty intense, but hopefully you get the idea.

Remember: template template templates are not legal C++, so this whole graph search thing won't actually compile. It's just a "what if?" :)