Obtenir un itérateur inversé à partir d'un itérateur avant sans connaître le type de valeur

Question

J'essaie d'implémenter certains algorithmes de tri de style STL. Le prototype de std::sort ressemble à quelque chose comme ça (de cplusplus.com):

template <class RandomAccessIterator> 
void sort (RandomAccessIterator first, RandomAccessIterator last); 

La fonction est généralement appelée comme celui-ci (bien que le type de récipient peut varier):

std::vector<int> myVec; 
// Populate myVec 
std::sort(myVec.begin(), myVec.end()); 

Je dupliqué le prototype de std::sort pour ma propre fonction de tri. Pour itérer à travers le récipient à trier, je fais ce qui suit:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    RandomAccessIterator iter; 
    for (iter = first; iter != last; ++iter) { 
    // Do stuff 
    } 
} 

assez facile. Mais que se passe-t-il si je veux utiliser un itérateur inverse? Cela serait pratique dans des algorithmes qui trient un conteneur à partir des deux extrémités, par ex. cocktail sort.

Y a-t-il un moyen d'obtenir un itérateur inverse des itérateurs qui sont transmis en tant que paramètres? Si je savais que le type de conteneur à l'avance, je pouvais faire quelque chose comme ceci:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    std::vector<int>::reverse_iterator riter(last); 
    std::vector<int>::reverse_iterator rend(first); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
}  

Malheureusement, je ne le font pas connaître le type de conteneur. Ce que je vraiment besoin de faire quelque chose comme ceci:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) { 
    RandomAccessIterator riter = reverse_iterator(last); 
    RandomAccessIterator rend = reverse_iterator(begin); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
} 

Est-il possible de le faire sans avoir à passer itérateurs inverse en tant que paramètres supplémentaires (ce qui résoudrait le problème, mais faire le prototype de fonction moins intuitive) ?

Notez que j'ai besoin avant les deux et itérateurs inverse dans ma mise en œuvre, afin d'appeler la fonction de cette façon

std::vector<int> myVec; 
// Populate myVec 
mySort(myVec.rbegin(), myVec.rend()); 

ne fonctionnera pas.

Answer 1

La STL a std::reverse_iterator<Iterator>:

template <class RandomAccessIterator> 
void mySort(RandomAccessIterator first, RandomAccessIterator last) 
{ 
    typedef std::reverse_iterator<RandomAccessIterator> RIter; 
    RIter riter(last); 
    RIter rend(first); 
    for (; riter != rend; ++riter) { 
    // Do stuff 
    } 
} 

Un important note:

Avis cependant que lorsqu'un itérateur est inversée, la version inversée ne pas pointer vers le même élément dans la gamme mais à celui qui le précède. Il est ainsi, pour organiser l'élément passé-fin d'une plage: Un itérateur pointant vers un élément passé-fin dans une plage, lorsqu'il est inversé, est changé pour pointer vers le dernier élément (pas passé) de la plage (cela serait être le premier élément de la plage si inversé). Et si un itérateur du premier élément d'une plage est inversé, l'itérateur inversé pointe vers l'élément avant le premier élément (cet serait l'élément passé-fin de la plage si inversée).

Answer 2

Vérifiez la méthode base() de reverse_iterator.