How to "pattern match" a template?

Question

Normally in templates you want to know the entire type, but in my case I need to know more, and want to "break up" the type. Take this example:

template <typename Collection<typename T> >
T get_front(Collection const& c)
{
  return c.front();
}

How can I achieve that? Note: I need it to to automatically deduce the types, not pass in something like <std::vector<int>, int>

Answer 1

Edit: A C++0x way can be found at the end.
Edit 2: I'm stupid, and a way shorter C++98/03 way than all this traits stuff can be found at the end of the answer.

If you want your function to work for any arbitary standard library container, you need to pull out some Template Guns.

---

The thing is, that the different container take a different amount of template parameters. std::vector, std::deque and std::list for example take 2: the underlying item type T and the allocator type Alloc. std::set and std::map on the other hand take 3 and 4 respectively: both have the key type K, map takes another value type V, then both take a comparator Compare type and the allocator type Alloc. You can get an overview of all container types supplied by the standard library for example here.

---

Now, for the Template Guns. We will be using a partially specialized traits metastruct to get the underlying item type. (I use class instead of typename out of pure preference.)

template<class T>
struct ContainerTraits;

// vector, deque, list and even stack and queue (2 template parameters)
template<
    template<class, class> class Container,
    class T, class Other
>
struct ContainerTraits< Container<T,Other> >{
    typedef T value_type;
};

// for set, multiset, and priority_queue (3 template parameters)
template<
    template<class, class, class> class Container,
    class T, class Other1, class Other2
>
struct ContainerTraits< Container<T,Other1,Other2> >{
    typedef T value_type;
};

// for map and multimap (4 template parameters)
template<
    template<class, class, class, class> class Container,
    class Key, class T, class Other1, class Other2
>
struct ContainerTraits< Container<Key,T,Other1,Other2> >{
    typedef Container<Key,T,Other1,Other2> ContainerT;
    // and the map returns pair<const Key,T> from the begin() function
    typedef typename ContainerT::value_type value_type;
};

Now that the preparation is done, on to the get_front function!

template<class Container>
typename ContainerTraits<Container>::value_type
get_front(Container const& c){
    // begin() is the only shared access function
    // to the first element for all standard container (except std::bitset)
    return *c.begin(); 
}

Phew! And that's it! A full example can be seen on Ideone. Of course it would be possible to refine that even further, to the point of returning the actual value that is mapped to a key in a std::map, or use container specific access functions, but I was just a bit too lazy to do that. :P

---

Edit
A way easier C++0x way is using the new trailing-return-type function syntax, of which an example can be found here on Ideone.

---

Edit 2
Well, I don't know why, but I totally didn't think of the nested typedefs when writing this answer. I'll let the verbose way stay as a reference for traits classes / pattern matching a template. This is the way to do it, it is basically the same I did with the traits classes, but ultimately less verbose.

Answer 2

You could do this if you know it's not an associative container.

template <typename Collection>
Collection::type_name get_front(Collection const& c)
{
  return c.front();
}

Answer 3

I'm assuming you want both Collection and T as template parameters. To do that simply type

template< template < typename > class Collection, typename T >
T get_front( Collection< T > const& c )
...

The construct template < typename > class Collection tells the compiler that Collection is a template itself with one parameter.

Edit: As pointed out be Xeo, vector takes two template parameters, and your templates need to reflect that, i.e.

template< template < typename, typename > class Collection, 
          typename T, typename Alloc >
T get_front( Collection< T, Alloc > const& c )
...