Gabarit dans un gabarit - accéder au type contenu à partir d'un type de gabarit

Question

J'essayais d'écrire une fonction de tri rapide. La pensée dans ma tête était que je voulais écrire un quicksort qui peut fonctionner sur une structure de données qui a un opérateur d'indexation et une relation d'ordre sur les objets qu'il contient, pour que je puisse faire des choses comme

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

etc.

J'ai commencé avec une fonction comme

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

le problème je me suis immédiatement tombé était à venir avec une fonction qui effectue l'opération d'échange qui est nécessaire pour le tri. J'ai besoin de savoir si les valeurs que je suis en train d'échanger sont des chaînes, des caractères, des ints, peu importe ce que je peux faire pour faire un échange temporaire!

donc je dois être capable de faire quelque chose comme ça (je sais que cette syntaxe est incorrecte, je suis juste essayer d'illustrer ce que je suis en train de faire):

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

donc je peux savoir quel type d'objet est contenu dans T pendant que j'effectue le swap. Cela signifie clairement que T doit être lui-même une classe modèle avec un argument template spécifiant quel type il contient, mais ce n'est pas vraiment grave.

Est-ce possible? Il semble que ça devrait être. Comment s'appelle-t-il?

Answer 1

Tous les conteneurs ont un typedef value_type que vous pouvez utiliser pour obtenir T:

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

Cela dit, chaque fois que possible, les algorithmes doivent être mis en œuvre à l'aide itérateurs, les découpler encore des mises en œuvre de conteneurs spécifiques. Par exemple,

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

Answer 2

Si T est un récipient approprié STL, vous pouvez obtenir le type de valeur avec:

typename T::value_type

Ainsi, par exemple, si T est un std::vector<std::string>, alors typename T::value_type est un std::string.

Answer 3

Vous pouvez utiliser std :: swap pour échanger deux valeurs.

Votre fonction de modèle devrait ressembler à ceci:

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