Abrufen eines Rückwärts-Iterators aus einem Vorwärts-Iterator ohne Kenntnis des Werttyps

Question

Ich versuche, einige STL-ähnliche Sortieralgorithmen zu implementieren. Der Prototyp für std::sort sieht etwa so aus (aus cplusplus.de ):

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

Die Funktion wird im Allgemeinen wie folgt aufgerufen (obwohl der Containertyp variieren kann):

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

Ich duplizierte den Prototyp von std::sort für meine eigene Sortierfunktion. Um den zu sortierenden Container zu durchlaufen, gehe ich wie folgt vor:

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

Ganz einfach. Aber was ist, wenn ich einen umgekehrten Iterator verwenden möchte? Das wäre praktisch bei Algorithmen, die einen Container von beiden Enden her sortieren, z. B. Cocktailsorte .

Gibt es eine Möglichkeit, einen umgekehrten Iterator aus den Iteratoren zu erhalten, die als Parameter übergeben werden? Wenn ich den Containertyp im Voraus kennen würde, könnte ich so etwas tun:

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

Leider habe ich nicht den Containertyp kennen. Was ich wirklich tun müssen, ist so etwas wie dieses:

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

Gibt es eine Möglichkeit, dies zu tun, ohne dass in umgekehrten Iteratoren als zusätzliche Parameter übergeben (was das Problem lösen würde, aber machen die Funktion Prototyp weniger intuitiv)?

Beachten Sie, dass ich beides benötige y Umgekehrte Iteratoren in meiner Implementierung, so dass der Aufruf der Funktion auf diese Weise

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

wird nicht funktionieren.

Answer 1

Die STL hat 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 site wichtiger Hinweis :

Beachten Sie jedoch, dass, wenn ein Iterator umgedreht wird, die umgekehrte Version nicht auf das gleiche Element im Bereich, sondern auf das vorangehende Element. Dies ist so, um für das das letzte Element eines Bereichs zu finden: Ein Iterator, der auf ein Element am Ende des Bereichs zeigt Element in einem Bereich zeigt, ist, wenn er umgekehrt wird, so geändert, dass er auf das letzte Element (nicht darüber hinaus) des Bereichs zeigt (dies wäre das erste Element des Bereichs sein, wenn umgedreht). Und wenn ein Iterator auf das ersten Element in einem Bereich umgedreht wird, zeigt der umgekehrte Iterator auf das Element vor dem ersten Element (dies wäre das Element hinter dem Ende des Bereichs des Bereichs, wenn er umgekehrt wird).

Answer 2

Sehen Sie sich die base()-Methode von reverse_iterator an.