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

95

Ist es möglich, einen Vektor vom Ende bis zum Anfang zu 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) {
}
Benutzer
quelle
2
In C ++ 11 können Sie eine bereichsbasierte for-Schleife mit Reverse-Adapter verwenden, siehe hier
MM
1
Wenn auf einer 32-Bit-Maschine für die zweite Lösung die Vektorgröße größer als 2.147.483.647 + 1 ist, läuft sie theoretisch über (vector :: size () ist ohne Vorzeichen), aber derzeit besteht die Möglichkeit, dass Sie diese Grenze niemals erreichen (auch nicht) Die aktuelle Vektorgrenze auf 32-Bit-Maschinen beträgt 1.073.741.823.
Stefan Rogin

Antworten:

156

Der beste Weg ist:

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

rbegin()Ich rend()wurde speziell für diesen Zweck entwickelt. (Und ja, wenn Sie a reverse_interatorerhöhen, wird es rückwärts verschoben.)

Theoretisch würde Ihre Methode (mit begin()/ end()& --i) funktionieren, da std::vectorder Iterator bidirektional ist. Denken Sie jedoch daran, dass dies end()nicht das letzte Element ist - es ist eines, das über das letzte Element hinausgeht. Sie müssten also zuerst dekrementieren, und Sie sind es erledigt, wenn Sie erreichen begin()- aber Sie müssen 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, dass das --iam Anfang ist.)

James Curran
quelle
Ich habe gerade festgestellt, --idass dies ein großes Problem verursachen wird, wenn der Container leer ist ... Bevor Sie in die do - whileSchleife gehen, ist es sinnvoll, dies zu überprüfen (my_vector.begin() != my_vector.end()).
a1ex07
1
Warum verwenden Sie eine do-whileSchleife anstelle einer whileSchleife? Dann brauchen Sie keine spezielle Prüfung für leere Vektoren.
Jamesdlin
Könnten Sie die Antwort aktualisieren, autoum sie besser lesbar zu machen?
LNJ
56

Wenn Sie C ++ 11 haben, können Sie davon Gebrauch machen auto.

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

Das gut etablierte "Muster" für die Rückwärtsiteration durch geschlossen-offene Bereiche sieht wie folgt 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 ist beispielsweise nützlich, um ein Array mithilfe eines vorzeichenlosen Index rückwärts zu indizieren

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 darauf, vorzeichenbehaftete Ganzzahltypen für die Array-Indizierung zu verwenden, da sie fälschlicherweise glauben, dass vorzeichenlose Typen für die umgekehrte Indizierung irgendwie "unbrauchbar" sind.)

Es kann zum Iterieren über ein Array unter Verwendung einer "Gleitzeiger" -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 unter Verwendung eines gewöhnlichen (nicht umgekehrten) Iterators verwendet werden

for (vector<my_class>::iterator i = my_vector.end(); i-- != my_vector.begin(); ) {
  *i; // <- process it
}
Ameise
quelle
cppreference.com sagt, der Zugriff auf das Element am Ende () "führt zu undefiniertem Verhalten", daher denke ich, dass die Schleifen um--end()
Thomas Schmid
@ThomasSchmid Diese Schleifen versuchen niemals, auf zuzugreifen end(). Obwohl sie anscheinend bei beginnen end(), stellen sie immer sicher, dass der Iterator vor dem ersten Zugriff dekrementiert wird.
AnT
Dies ist so viel schöner als rbegin / rend, weil Sie zur Laufzeit in die andere Richtung schleifen können (keine Vorlage) auto a = vector<int>{0,1,2}; bool reversed = 0; auto it = (!reversed?a.begin():a.end()); auto end = (reversed?a.begin():a.end()); while(it != end) { if(reversed)--it; cout << *it << endl; if(!reversed)++it; }
colin
@ Colin Egads! so hässlich!. Sie testen reversed vier Mal - zwei davon in einer Schleife. Natürlich ist das Testen eines Booleschen Werts sehr schnell, aber warum müssen Sie nicht arbeiten, um zu arbeiten? Zumal der einzige Zweck darin zu bestehen scheint, den Code unlesbar zu machen. Wie wäre es, wenn wir zwei separate Schleifen verwenden? if (reversed) for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it) {doStuff(*it);} else for (auto it = my_vector.begin(); it != my_vector.end(); ++it) {doStuff(*it);}
James Curran
Eigentlich hast du meinen Standpunkt verfehlt. Sie haben absolut Recht, es in zwei Teile aufzuteilen, ifaber ich wollte die Vorlage auf der Seite loswerden doStuff(). Immer noch machbar mit den beiden ifs, die Sie haben, indem Sie den ersten umgekehrt drehen.
Colin
10

Ab c ++ 20 können Sie eine std::ranges::reverse_viewund eine bereichsbasierte for-Schleife verwenden:

#include<ranges>
#include<vector>
#include<iostream>

using namespace std::ranges;

std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for(auto& i :  views::reverse(vec)) {
    std::cout << i << ",";
}

Oder auch

for(auto& i :  vec | views::reverse)

Leider implementiert zum Zeitpunkt des Schreibens (Januar 2020) kein großer Compiler die Bereichsbibliothek, aber Sie können auf Eric Nieblers Bereiche-v3 zurückgreifen :

#include <iostream>
#include <vector>
#include "range/v3/all.hpp"

int main() {

    using namespace ranges;

    std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(auto& i :  views::reverse(vec)) {
        std::cout << i << ",";
    }

    return 0;
}
florestan
quelle
9

Benutzeriteratoren rend() / rbegin():

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

a1ex07
quelle
5
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 auch 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 backwardswie 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 können Sie dies tun:

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

was ich ziemlich hübsch finde.

Yakk - Adam Nevraumont
quelle
4

Verwenden Sie umgekehrte Iteratoren und eine Schleife von rbegin()bisrend()

Steve Townsend
quelle
1

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

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 ein rbegin () und ein 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))
    ;
Mordachai
quelle
0

Ich mag den Rückwärtsiterator 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 diesen verwenden:

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

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

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

Wenn Sie The Boost Library verwenden können, gibt es den Boost.Range , der den reverseBereichsadapter bereitstellt , indem er Folgendes enthält :

#include <boost/range/adaptor/reversed.hpp>

In Kombination mit der Range- forSchleife eines C ++ 11 können Sie dann einfach Folgendes schreiben:

for (auto& elem: boost::adaptors::reverse(my_vector)) {
   // ...
}

Da dieser Code kürzer ist als der, der das Iteratorpaar verwendet, ist er möglicherweise besser lesbar und weniger fehleranfällig, da weniger Details zu beachten sind.

眠 り ネ ロ ク
quelle
-1

Verwenden Sie diesen Code

//print the vector element in reverse order by normal iterator.
cout <<"print the vector element in reverse order by normal iterator." <<endl;
vector<string>::iterator iter=vec.end();
--iter;
while (iter != vec.begin())
{
    cout << *iter  << " "; 
    --iter;
}
Amit Kumar
quelle
-2

Da ich die neue Syntax von Alien Mars überhaupt nicht einführen möchte und einfach auf vorhandenen Grundelementen aufbauen möchte, scheinen die folgenden Ausschnitte zu funktionieren:

#include <vector>
#include <iostream>

int main (int argc,char *argv[])
{
    std::vector<int> arr{1,2,3,4,5};
    std::vector<int>::iterator it;

    for (it = arr.begin(); it != arr.end(); it++) {
        std::cout << *it << " ";
    }

    std::cout << "\n************\n";

    for (it = arr.end() - 1; it != arr.begin()-1;it--) {
        std::cout << *it << " ";
    }

    return 0;
}
trueadjustr
quelle