Template in a Template -- accessing contained type from a template type

Question

I was trying to write a templatized quicksort function. The thought in my head was that I would write a quicksort that can operate on any data structure that has a subscript operator and an order relation on the objects contained within it, so I could do things like

quicksort<deque<int> >();
quicksort<vector<string> >(); 

etc.

I started out with a function like

template<typename T>
void quicksort(T& list);

the problem I immediately ran into was coming up with a function that performs the swap operation which is necessary for sorting. I need to know if the values I'm swapping are strings, chars, ints, whatever so I can make a temporary to perform the swap!

So I need to be able to do something like this (I know this syntax is incorrect, I'm just trying to illustrate what I'm trying to do):

template<typename T, typename R>
void quicksort(T<R>& list);

so I can know what type of object is contained within T while I'm performing the swap. Clearly this means that T has to be, itself, a template class with a template argument specifying what type it contains but that's not really a big deal.

Is this possible? It seems like it should be. What is this called?

Answer 1

All of the containers have a typedef value_type that you can use to get T:

template <typename ContainerT>
void quicksort(ContainerT& container)
{
    typedef typename ContainerT::value_type ElementT;
    // etc.
}

That said, wherever possible, algorithms should be implemented using iterators, to further decouple them from specific container implementations. For example,

template <typename RandomAccessItT>
void quicksort(RandomAccessItT first, RandomAccessItT last)
{
    typedef std::iterator_traits<RandomAccessItT>::value_type ElementT;
    // etc.
}

Answer 2

If T is a proper STL container, you can get the value type with:

typename T::value_type

So, for example, if T is an std::vector<std::string>, then typename T::value_type is an std::string.

Answer 3

You can use std::swap to swap two values.

Your template function should be like this :

template < class ContainterType >
void quicksort( ContainerType &container )
{
 //  ...
}