Шаблон в шаблоне - доступ к вложенному типу из типа шаблона

Question

Я пытался написать шаблонную функцию быстрой сортировки. В моей голове была мысль, что я напишу быструю сортировку, которая может работать с любой структурой данных, в которой есть оператор индекса и отношение порядка для объектов, содержащихся в нем, поэтому я мог бы делать такие вещи, как

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

и т.д.

Я начал с такой функции, как

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

проблема, с которой я сразу столкнулся, заключалась в том, чтобы найти функцию, которая выполняет операцию подкачки, необходимую для сортировки. Мне нужно знать, являются ли значения, которые я обмениваю, строками, символами, целыми числами, чем угодно, чтобы я мог сделать временный обмен для выполнения свопинга!

Так что мне нужно иметь возможность сделать что-то подобное (я знаю, что этот синтаксис неправильный, я просто пытаюсь проиллюстрировать, что я пытаюсь сделать):

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

чтобы я мог знать, какой тип объекта содержится в T, пока я выполняю обмен. Ясно, что это означает, что T сам по себе должен быть классом шаблона с аргументом шаблона, указывающим, какой тип он содержит, но на самом деле это не имеет большого значения.

Возможно ли это? Кажется, так и должно быть. Как это называется?

Answer 1

Все контейнеры имеют typedef value_type, который вы можете использовать для получения T:

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

Тем не менее, по возможности, алгоритмы должны быть реализованы с использованием итераторов, чтобы дополнительно отделить их от конкретных реализаций контейнера. Например,

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

Answer 2

Если T является правильным контейнером STL, вы можете получить тип значения с помощью:

typename T::value_type

Так, например, если T является std::vector<std::string>, то typename T::value_type является std::string.

Answer 3

Вы можете использовать std :: swap для замены двух значений.

Ваша функция шаблона должна быть такой:

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