wake-up-neo.net

Iteration des C++ - Vektors vom Ende bis zum Anfang

Kann man einen Vektor vom Ende bis zum Anfang iterieren?

for (vector<my_class>::iterator i = my_vector.end();
        i != my_vector.begin(); /* ?! */ ) {
}

Oder ist das nur mit so etwas möglich:

for (int i = my_vector.size() - 1; i >= 0; --i) {
}
55
user

Nun, der beste Weg ist:

for (vector<my_class>::reverse_iterator i = my_vector.rbegin(); 
        i != my_vector.rend(); ++i ) { 
} 

rbegin ()/rend () wurde speziell für diesen Zweck entwickelt. (Und ja, ein Inkrementieren eines reverse_interator verschiebt es rückwärts)

Theoretisch würde Ihre Methode (mit begin/end & --i) funktionieren, wobei der Iterator von vector bidirektional ist. Denken Sie jedoch daran, dass end () nicht das letzte Element ist, sondern ein Element jenseits des letzten Elements dekrementieren Sie zuerst, und Sie sind fertig, wenn Sie begin () erreichen. Sie müssen jedoch noch Ihre Verarbeitung durchführen. 

vector<my_class>::iterator i = my_vector.end();
while (i != my_vector.begin())
{
     --i;
    /*do stuff */ ) 

} 

UPDATE: Ich war anscheinend zu aggressiv beim Umschreiben der for () - Schleife in eine while-Schleife. (Der wichtige Teil ist der --i ist am Anfang.)

106
James Curran

Wenn Sie C++11 haben, können Sie auto verwenden.

for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it)
{
}
30
Akavall

Das gut etablierte "Muster" für Reverse-Iteration durch geschlossene offene Bereiche sieht folgendermaßen aus

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator-- != begin; ) {
  // Process `*iterator`
}

oder, wenn Sie es vorziehen, 

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator != begin; ) {
  --iterator;
  // Process `*iterator`
}

Dieses Muster kann zum Beispiel für die Rückwärtsindexierung eines Arrays mit einem vorzeichenlosen Index verwendet werden

int array[N];
...
// Iterate over [0, N) range in reverse
for (unsigned i = N; i-- != 0; ) {
  array[i]; // <- process it
}

(Personen, die mit diesem Muster nicht vertraut sind, bestehen häufig auf der Verwendung von Ganzzahl-Typen signed für die Array-Indexierung, insbesondere weil sie fälschlicherweise glauben, dass nicht signierte Typen die Rückwärts-Indexierung verhindern.

Es kann zum Durchlaufen eines Arrays mit einer "gleitenden Zeiger" -Technik verwendet werden

// Iterate over [array, array + N) range in reverse
for (int *p = array + N; p-- != array; ) {
  *p; // <- process it
}

oder es kann für die umgekehrte Iteration über einen Vektor verwendet werden, wobei ein gewöhnlicher (nicht umgekehrter) Iterator verwendet wird

for (vector<my_class>::iterator i = my_vector.end(); i-- != my_vector.begin(); ) {
  *i; // <- process it
}
18
AnT

Benutzer rend() / rbegin() Iteratoren:

for (vector<myclass>::reverse_iterator it = myvector.rbegin(); it != myvector.rend(); it++)

9
a1ex07
template<class It>
std::reverse_iterator<It> reversed( It it ) {
  return std::reverse_iterator<It>(std::forward<It>(it));
}

Dann:

for( auto rit = reversed(data.end()); rit != reversed(data.begin()); ++rit ) {
  std::cout << *rit;

Alternativ können Sie in C++ 14 einfach Folgendes tun:

for( auto rit = std::rbegin(data); rit != std::rend(data); ++rit ) {
  std::cout << *rit;

In C++ 03/11 haben die meisten Standardcontainer auch eine .rbegin()- und .rend()-Methode.

Schließlich können Sie den Bereichsadapter backwards wie folgt schreiben:

namespace adl_aux {
  using std::begin; using std::end;
  template<class C>
  decltype( begin( std::declval<C>() ) ) adl_begin( C&& c ) {
    return begin(std::forward<C>(c));
  }
  template<class C>
  decltype( end( std::declval<C>() ) ) adl_end( C&& c ) {
    return end(std::forward<C>(c));
  }
}

template<class It>
struct simple_range {
  It b_, e_;
  simple_range():b_(),e_(){}
  It begin() const { return b_; }
  It end() const { return e_; }
  simple_range( It b, It e ):b_(b), e_(e) {}

  template<class OtherRange>
  simple_range( OtherRange&& o ):
    simple_range(adl_aux::adl_begin(o), adl_aux::adl_end(o))
  {}

  // explicit defaults:
  simple_range( simple_range const& o ) = default;
  simple_range( simple_range && o ) = default;
  simple_range& operator=( simple_range const& o ) = default;
  simple_range& operator=( simple_range && o ) = default;
};
template<class C>
simple_range< decltype( reversed( adl_aux::adl_begin( std::declval<C&>() ) ) ) >
backwards( C&& c ) {
  return { reversed( adl_aux::adl_end(c) ), reversed( adl_aux::adl_begin(c) ) };
}

und jetzt kannst du das tun:

for (auto&& x : backwards(ctnr))
  std::cout << x;

das finde ich ziemlich hübsch.

Verwenden Sie umgekehrte Iteratoren und eine Schleife von rbegin() zu rend()

4
Steve Townsend

Ich mag den Rückwärts-Iterator am Ende von Yakk - Adam Nevraumonts Antwort, aber es schien kompliziert für das, was ich brauchte, also schrieb ich Folgendes:

template <class T>
class backwards {
    T& _obj;
public:
    backwards(T &obj) : _obj(obj) {}
    auto begin() {return _obj.rbegin();}
    auto end() {return _obj.rend();}
};

Ich kann einen normalen Iterator wie folgt nehmen:

for (auto &elem : vec) {
    // ... my useful code
}

und ändern Sie es, um in umgekehrter Reihenfolge zu iterieren:

for (auto &elem : backwards(vec)) {
    // ... my useful code
}
0
John Stephen

Hier ist eine supereinfache Implementierung, die die Verwendung von für jedes Konstrukt ermöglicht und sich nur auf die C++ 14-Standardbibliothek stützt:

namespace Details {

    // simple storage of a begin and end iterator
    template<class T>
    struct iterator_range
    {
        T beginning, ending;
        iterator_range(T beginning, T ending) : beginning(beginning), ending(ending) {}

        T begin() const { return beginning; }
        T end() const { return ending; }
    };

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// usage:
//  for (auto e : backwards(collection))
template<class T>
auto backwards(T & collection)
{
    using namespace std;
    return Details::iterator_range(rbegin(collection), rend(collection));
}

Dies funktioniert mit Dingen, die rbegin () und rend () liefern, sowie mit statischen Arrays.

std::vector<int> collection{ 5, 9, 15, 22 };
for (auto e : backwards(collection))
    ;

long values[] = { 3, 6, 9, 12 };
for (auto e : backwards(values))
    ;
0
Mordachai