Obtener un iterador inverso de un iterador directo sin saber el tipo de valor

Question

Estoy tratando de implementar algunos algoritmos de clasificación de estilo STL. El prototipo para std::sort ve algo como esto (de cplusplus.com):

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

La función se denomina generalmente como esto (aunque el tipo de contenedor puede variar):

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

Yo duplicado el prototipo de std::sort de mi propia función de clasificación. Para iterar a través del contenedor que se ordenará, hago lo siguiente:

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

Bastante fácil. Pero, ¿y si quiero usar un iterador inverso? Esto sería conveniente en los algoritmos que ordenan un contenedor de ambos extremos, p. cocktail sort.

¿Hay alguna manera de obtener un iterador inverso de los iteradores que se pasan como parámetros? Si supiera el tipo de contenedor con antelación, lo que podía hacer algo como esto:

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 
    } 
}  

Desafortunadamente, No saber el tipo de contenedor. Lo que realmente necesita hacer es algo como esto:

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 
    } 
} 

¿Hay alguna manera de hacer esto sin tener que pasar en iteradores inversa como parámetros adicionales (lo que resolvería el problema, sino que el prototipo de función menos intuitivo) ?

Tenga en cuenta que necesito tanto hacia adelante y iteradores inversa en mi aplicación, por lo que llama a la función de esta manera

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

no va a funcionar.

Answer 1

El STL tiene 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:

Aviso sin embargo, que cuando un iterador se invierte, la versión invertida no no apunta al mismo elemento en el rango , pero a la que lo precede. Esto es así, para organizar el elemento pasado de un rango: Un iterador que apunta a un elemento pasado en el extremo en un rango, cuando se invierte, es cambiado para señalar el último elemento (no más allá) del rango (esto sería ser el primer elemento del rango si invertido). Y si se invierte un iterador en el primer elemento en un rango, el iterador invertido apunta al elemento antes que el primer elemento (este sería el elemento pasado de el rango si está invertido).

Answer 2

Comprueba el método base() de reverse_iterator.