Ottenere un iteratore inverso da un iteratore diretto senza conoscere il tipo di valore

Question

Sto tentando di implementare alcuni algoritmi di ordinamento in stile STL. Il prototipo per std::sort simile a questa (da cplusplus.com):

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

La funzione viene generalmente chiamato come questo (anche se il tipo di contenitore può variare):

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

ho duplicato il prototipo di std::sort per la mia funzione di smistamento Per scorrere il contenitore da ordinare, faccio quanto segue:

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

Abbastanza facile. Ma cosa succede se voglio usare un iteratore inverso? Ciò sarebbe conveniente negli algoritmi che ordinano un contenitore da entrambe le estremità, ad es. cocktail sort.

C'è un modo per ottenere un iteratore inverso dagli iteratori passati come parametri? Se avessi saputo il tipo di contenitore in anticipo, avrei potuto fare qualcosa di simile:

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

Purtroppo, io non lo fanno conoscere il tipo di contenitore. Quello che ho veramente bisogno di fare è qualcosa di simile:

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

C'è qualche modo per farlo senza dover passare in iteratori inverso, come parametri aggiuntivi (che avrebbe risolto il problema, ma fare il prototipo di funzione meno intuitivo) ?

Nota che ho bisogno sia in avanti e iteratori inversa nella mia realizzazione, in modo da chiamare la funzione in questo modo

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

non funzionerà.

Answer 1

Lo STL ha 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:

Avviso tuttavia che quando un iteratore si inverte, la versione invertita non non punta allo stesso elemento nella gamma , ma a quello che lo precede. Per organizzare l'elemento passato-fine di un intervallo: Un iteratore che punta a un elemento escluso in un intervallo, una volta invertito, è modificato in modo che punti all'ultimo elemento (non oltre) dell'intervallo (questo sarebbe essere il primo elemento dell'intervallo se invertito). E se un iteratore per il primo elemento di un intervallo è invertito, l'iteratore invertito punta all'elemento prima del primo elemento (questo sarebbe l'elemento passato-end di l'intervallo se invertito).

Answer 2

Verificare il metodo base() di reverse_iterator.