Iteration über std :: vector: vorzeichenlose oder vorzeichenbehaftete Indexvariable

470

Was ist die richtige Methode zum Iterieren über einen Vektor in C ++?

Betrachten Sie diese beiden Codefragmente, dieses funktioniert gut:

for (unsigned i=0; i < polygon.size(); i++) {
    sum += polygon[i];
}

und das hier:

for (int i=0; i < polygon.size(); i++) {
    sum += polygon[i];
}

was erzeugt warning: comparison between signed and unsigned integer expressions.

Ich bin neu in der Welt von C ++, daher unsignedsieht die Variable für mich etwas beängstigend aus und ich weiß, dass unsignedVariablen gefährlich sein können, wenn sie nicht richtig verwendet werden. Ist das also richtig?

Yuval Adam
quelle
10
Das vorzeichenlose ist korrekt, da polygon.size () vom Typ ohne Vorzeichen ist. Ohne Vorzeichen bedeutet immer positiv oder 0. Das ist alles, was es bedeutet. Wenn die Variable also immer nur für Zählungen verwendet wird, ist unsigned die richtige Wahl.
Adam Bruss
3
@AdamBruss .size()ist nicht vom Typ unsignedaka unsigned int. Es ist vom Typ std::size_t.
underscore_d
1
@underscore_d size_t ist ein Alias ​​für unsigned.
Adam Bruss
2
@AdamBruss No. std::size_tist ein _implementierungsdefinierter Typedef. Siehe den Standard. std::size_tDies entspricht möglicherweise unsignedIhrer aktuellen Implementierung, ist jedoch nicht relevant. Das Vorgeben, dies zu tun, kann zu nicht portierbarem Code und undefiniertem Verhalten führen.
underscore_d
2
@LF ... sicher, was wahrscheinlich std::size_tin der Praxis ist. Denken Sie, wir haben in diesem weitläufigen Strom von Kommentaren über 6 Jahre alles bisher behandelt?
underscore_d

Antworten:

817

Informationen zum Rückwärtslaufen finden Sie in dieser Antwort .

Vorwärts iterieren ist fast identisch. Ändern Sie einfach die Iteratoren / Swap-Dekremente schrittweise. Sie sollten Iteratoren bevorzugen. Einige Leute sagen Ihnen, dass Sie std::size_tals Indexvariablentyp verwenden sollen. Dies ist jedoch nicht tragbar. Verwenden size_typeSie immer das typedef des Containers (Während Sie im vorwärts iterierenden Fall nur mit einer Konvertierung davonkommen könnten, könnte es im rückwärts iterierenden Fall bei der Verwendung tatsächlich ganz schief gehen std::size_t, falls std::size_tes breiter ist als das typedef von size_type). ::


Verwenden von std :: vector

Iteratoren verwenden

for(std::vector<T>::iterator it = v.begin(); it != v.end(); ++it) {
    /* std::cout << *it; ... */
}

Wichtig ist, dass Sie immer das Präfix-Inkrement-Formular für Iteratoren verwenden, deren Definitionen Sie nicht kennen. Dadurch wird sichergestellt, dass Ihr Code so allgemein wie möglich ausgeführt wird.

Verwenden von Range C ++ 11

for(auto const& value: a) {
     /* std::cout << value; ... */

Indizes verwenden

for(std::vector<int>::size_type i = 0; i != v.size(); i++) {
    /* std::cout << v[i]; ... */
}

Arrays verwenden

Iteratoren verwenden

for(element_type* it = a; it != (a + (sizeof a / sizeof *a)); it++) {
    /* std::cout << *it; ... */
}

Verwenden von Range C ++ 11

for(auto const& value: a) {
     /* std::cout << value; ... */

Indizes verwenden

for(std::size_t i = 0; i != (sizeof a / sizeof *a); i++) {
    /* std::cout << a[i]; ... */
}

Lesen Sie in der rückwärts iterierenden Antwort, zu welchem ​​Problem der sizeofAnsatz führen kann.

Johannes Schaub - litb
quelle
Größe Zeigertyp: Die Verwendung von different_type ist möglicherweise portabler. Versuchen Sie iterator_traits <element_type *> :: different_type. Dies ist ein Schluck einer Erklärung, aber es ist tragbarer ...
Wilhelmtell
wilhelmtell, wofür soll ich different_type verwenden? sizeof ist definiert, um size_t zurückzugeben :) Ich verstehe dich nicht. Wenn ich Zeiger voneinander subtrahieren würde, wäre different_type die richtige Wahl.
Johannes Schaub - litb
Die Iteration über Arrays mit der in diesem Beitrag erwähnten Technik funktioniert nicht, wenn die Iteration in einer Funktion für ein an diese Funktion übergebenes Array ausgeführt wird. Weil sizeof array nur den sizeof-Zeiger zurückgibt.
Systemfehler
1
@Nils Ich stimme zu, dass die Verwendung von vorzeichenlosen Schleifenzählern eine schlechte Idee ist. Da die Standardbibliothek jedoch vorzeichenlose Ganzzahltypen für Index und Größe verwendet, bevorzuge ich vorzeichenlose Indextypen für die Standardbibliothek. andere Bibliotheken verwenden daher nur signierte Typen wie die Qt lib.
Johannes Schaub - litb
32
Update für C ++ 11: Bereich basierend auf Schleife. for (auto p : polygon){sum += p;}
Siyuan Ren
170

Vier Jahre vergingen, Google gab mir diese Antwort. Mit dem Standard- C ++ 11 (auch bekannt als C ++ 0x ) gibt es tatsächlich eine neue angenehme Möglichkeit (zum Preis der Unterbrechung der Abwärtskompatibilität): das neue autoSchlüsselwort. Dies erspart Ihnen die Mühe, den Typ des zu verwendenden Iterators explizit angeben zu müssen (wobei der Vektortyp erneut wiederholt wird), wenn (für den Compiler) klar ist, welcher Typ verwendet werden soll. Mit vIhrem sein vector, können Sie etwas tun , wie folgt:

for ( auto i = v.begin(); i != v.end(); i++ ) {
    std::cout << *i << std::endl;
}

C ++ 11 geht noch weiter und bietet Ihnen eine spezielle Syntax zum Durchlaufen von Sammlungen wie Vektoren. Es beseitigt die Notwendigkeit, Dinge zu schreiben, die immer gleich sind:

for ( auto &i : v ) {
    std::cout << i << std::endl;
}

Erstellen Sie eine Datei, um sie in einem Arbeitsprogramm anzuzeigen auto.cpp:

#include <vector>
#include <iostream>

int main(void) {
    std::vector<int> v = std::vector<int>();
    v.push_back(17);
    v.push_back(12);
    v.push_back(23);
    v.push_back(42);
    for ( auto &i : v ) {
        std::cout << i << std::endl;
    }
    return 0;
}

Wenn Sie dies mit g ++ kompilieren , müssen Sie es normalerweise so einstellen, dass es mit dem neuen Standard funktioniert, indem Sie ein zusätzliches Flag angeben:

g++ -std=c++0x -o auto auto.cpp

Jetzt können Sie das Beispiel ausführen:

$ ./auto
17
12
23
42

Bitte beachten Sie, dass die Anweisungen zum Kompilieren und Ausführen spezifisch für den gnu c ++ - Compiler unter Linux sind. Das Programm sollte plattform- (und compiler-) unabhängig sein.

kratenko
quelle
7
C ++ 11 gibt Ihnenfor (auto& val: vec)
Flexo
@flexo Danke, ich weiß nicht, wie ich das vergessen könnte. Ich denke, ich mache nicht genug C ++. Ich konnte nicht glauben, dass es etwas so Praktisches gibt (dachte eigentlich, das wäre JavaScript-Syntax). Ich habe die Antwort dahingehend geändert.
Kratenko
Ihre Antwort ist sehr nett. Es ist unangenehm, dass die Standardversion von g ++ in verschiedenen Betriebssystem-Devkits unter 4.3 liegt, was dazu führt, dass es nicht funktioniert.
Ratata Tata
Müssen Sie den Vektor mit initialisieren std::vector<int> v = std::vector<int>();oder hätten Sie ihn std::vector<int> v;stattdessen einfach verwenden können ?
Bill Cheatham
@ BillCheatham Nun - ich habe es gerade ohne Initialisierung ausprobiert und es hat funktioniert, also scheint es ohne zu funktionieren.
Kratenko
44

In dem speziellen Fall in Ihrem Beispiel würde ich die STL-Algorithmen verwenden, um dies zu erreichen.

#include <numeric> 

sum = std::accumulate( polygon.begin(), polygon.end(), 0 );

Für einen allgemeineren, aber immer noch recht einfachen Fall würde ich gehen mit:

#include <boost/lambda/lambda.hpp>
#include <boost/lambda/bind.hpp>

using namespace boost::lambda;
std::for_each( polygon.begin(), polygon.end(), sum += _1 );
paxos1977
quelle
38

Zur Antwort von Johannes Schaub:

for(std::vector<T*>::iterator it = v.begin(); it != v.end(); ++it) { 
...
}

Das mag mit einigen Compilern funktionieren, aber nicht mit gcc. Das Problem hierbei ist die Frage, ob std :: vector :: iterator ein Typ, eine Variable (Mitglied) oder eine Funktion (Methode) ist. Wir bekommen den folgenden Fehler mit gcc:

In member function void MyClass<T>::myMethod()’:
error: expected `;' before ‘it’
error: ‘it’ was not declared in this scope
In member function ‘void MyClass<T>::sort() [with T = MyClass]’:
instantiated from ‘void MyClass<T>::run() [with T = MyClass]’
instantiated from here
dependent-name ‘std::vector<T*,std::allocator<T*> >::iterator’ is parsed as a non-type, but instantiation yields a type
note: say ‘typename std::vector<T*,std::allocator<T*> >::iterator’ if a type is meant

Die Lösung verwendet das Schlüsselwort 'Typname' wie folgt:

typename std::vector<T*>::iterator it = v.begin();
for( ; it != v.end(); ++it) {
...
Polat Tuzla
quelle
2
Sie sollten erläutern, dass dies nur gilt, wenn Tes sich um ein Vorlagenargument handelt und der Ausdruck std::vector<T*>::iteratordaher ein abhängiger Name ist. Damit ein abhängiger Name als Typ analysiert werden kann, muss ihm das typenameSchlüsselwort vorangestellt werden , wie in der Diagnose angegeben.
Stellen Sie Monica
17

Ein Aufruf von vector<T>::size()gibt einen Wert vom Typ zurück std::vector<T>::size_type, nicht int, unsigned int oder anderweitig.

Im Allgemeinen wird die Iteration über einen Container in C ++ mithilfe solcher Iteratoren durchgeführt .

std::vector<T>::iterator i = polygon.begin();
std::vector<T>::iterator end = polygon.end();

for(; i != end; i++){
    sum += *i;
}

Wobei T der Datentyp ist, den Sie im Vektor speichern.

Oder die verschiedenen Iterationsalgorithmen mit ( std::transform, std::copy, std::fill, std::for_eachet cetera).

Jasper Bekkers
quelle
Iteratoren sind im Allgemeinen eine gute Idee, obwohl ich bezweifle, dass "end" in einer separaten Variablen gespeichert werden muss und alles in einer for (;;) - Anweisung erfolgen kann.
Saulius Žemaitaitis
1
Ich weiß, dass begin () und end () konstante Zeit amortisiert sind, aber ich finde dies im Allgemeinen besser lesbar, als alles in eine Zeile zu packen.
Jasper Bekkers
3
Sie können das for in separate Zeilen aufteilen, um die Lesbarkeit zu verbessern. Wenn Sie Iteratoren außerhalb der Schleife deklarieren, benötigen Sie für jede Schleife über Container unterschiedlichen Typs einen anderen Iteratornamen.
Jay Conrod
Ich bin mir aller Unterschiede bewusst, und worauf es im Grunde ankommt, sind persönliche Vorlieben. So mache ich im Allgemeinen Dinge.
Jasper Bekkers
2
@pihentagy Ich denke, das wäre, es im ersten Abschnitt der for-Schleife zu setzen. z.B. für (auto i = polygon.begin (), end = polygon.end (); i! = end; i ++)
Jasper Bekkers
11

Verwendung size_t:

for (size_t i=0; i < polygon.size(); i++)

Wikipedia zitieren :

Die Header-Dateien stdlib.h und stddef.h definieren einen Datentyp namens, size_tder zur Darstellung der Größe eines Objekts verwendet wird. Bibliotheksfunktionen, die Größen annehmen, erwarten, dass sie vom Typ sind size_t, und der Operator sizeof wertet aus size_t.

Der tatsächliche Typ von size_tist plattformabhängig; Ein häufiger Fehler ist die Annahme size_t, dass es sich um int ohne Vorzeichen handelt, was zu Programmierfehlern führen kann, insbesondere wenn 64-Bit-Architekturen häufiger eingesetzt werden.

Igor Oks
quelle
size_t OK für Vektor, da alle Objekte in einem Array gespeichert werden müssen (selbst auch ein Objekt), eine std :: -Liste jedoch möglicherweise mehr als size_t-Elemente enthält!
MSalters
1
size_t reicht normalerweise aus, um alle Bytes im Adressraum eines Prozesses aufzulisten. Während ich sehen kann, dass dies bei einigen exotischen Architekturen möglicherweise nicht der Fall ist, möchte ich mir lieber keine Sorgen machen.
AFAIK ist es empfehlenswert , um #include <cstddef>statt <stddef.h>oder, schlimmer noch, die Gesamtheit [c]stdlibund die Verwendung std::size_tnicht die uneingeschränkte Version - und gleiche gilt für jede andere Situation , wo Sie haben die Wahl zwischen <cheader>und <header.h>.
underscore_d
7

Ein bisschen Geschichte:

Verwenden Sie ein Vorzeichenbit, um darzustellen, ob eine Zahl negativ ist oder nicht. intist ein vorzeichenbehafteter Datentyp, der positive und negative Werte enthalten kann (etwa -2 bis 2 Milliarden). Unsignedkann nur positive Zahlen speichern (und da es kein bisschen an Metadaten verschwendet, kann es mehr speichern: 0 bis ungefähr 4 Milliarden).

std::vector::size()gibt ein zurück unsigned, denn wie könnte ein Vektor eine negative Länge haben?

Die Warnung sagt Ihnen, dass der rechte Operand Ihrer Ungleichheitsanweisung mehr Daten enthalten kann als der linke.

Wenn Sie einen Vektor mit mehr als 2 Milliarden Einträgen haben und eine Ganzzahl zum Indizieren verwenden, treten im Wesentlichen Überlaufprobleme auf (der int wird auf negative 2 Milliarden zurückgesetzt).

ecoffey
quelle
6

Normalerweise benutze ich BOOST_FOREACH:

#include <boost/foreach.hpp>

BOOST_FOREACH( vector_type::value_type& value, v ) {
    // do something with 'value'
}

Es funktioniert mit STL-Containern, Arrays, Strings im C-Stil usw.

Martin Cote
quelle
2
Gute Antwort auf eine andere Frage (wie soll ich einen Vektor iterieren?), Aber überhaupt nicht, was das OP gefragt hat (was bedeutet die Warnung vor einer vorzeichenlosen Variablen?)
abelenky
3
Nun, er fragte, wie man einen Vektor richtig iteriert. Scheint also relevant genug. Die Warnung ist nur, warum er mit seiner aktuellen Lösung nicht zufrieden ist.
Jalf
5

Um vollständig zu sein, aktiviert die C ++ 11-Syntax nur eine andere Version für Iteratoren ( ref ):

for(auto it=std::begin(polygon); it!=std::end(polygon); ++it) {
  // do something with *it
}

Das ist auch bequem für die umgekehrte Iteration

for(auto it=std::end(polygon)-1; it!=std::begin(polygon)-1; --it) {
  // do something with *it
}
Jan Turoň
quelle
5

In C ++ 11

Ich würde allgemeine Algorithmen verwenden for_each, um die Suche nach dem richtigen Typ von Iterator und Lambda-Ausdruck zu vermeiden, um zusätzliche benannte Funktionen / Objekte zu vermeiden.

Das kurze "hübsche" Beispiel für Ihren speziellen Fall (vorausgesetzt, Polygon ist ein Vektor von ganzen Zahlen):

for_each(polygon.begin(), polygon.end(), [&sum](int i){ sum += i; });

getestet auf: http://ideone.com/i6Ethd

Vergessen Sie nicht, Folgendes anzugeben : Algorithmus und natürlich Vektor :)

Microsoft hat tatsächlich auch ein schönes Beispiel dafür:
Quelle: http://msdn.microsoft.com/en-us/library/dd293608.aspx

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() 
{
   // Create a vector object that contains 10 elements.
   vector<int> v;
   for (int i = 1; i < 10; ++i) {
      v.push_back(i);
   }

   // Count the number of even numbers in the vector by 
   // using the for_each function and a lambda.
   int evenCount = 0;
   for_each(v.begin(), v.end(), [&evenCount] (int n) {
      cout << n;
      if (n % 2 == 0) {
         cout << " is even " << endl;
         ++evenCount;
      } else {
         cout << " is odd " << endl;
      }
   });

   // Print the count of even numbers to the console.
   cout << "There are " << evenCount 
        << " even numbers in the vector." << endl;
}
jave.web
quelle
4
for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it; 
Mehrdad Afshari
quelle
2
Für Vektoren ist dies in Ordnung, aber im Allgemeinen ist es besser, ++ als ++ zu verwenden, falls der Iterator selbst nicht trivial ist.
Steve Jessop
Persönlich bin ich es gewohnt, ++ i zu verwenden, aber ich denke, die meisten Leute bevorzugen den i ++ - Stil (das Standard-VS-Code-Snippet für "for" ist i ++). Nur ein Gedanke
Mehrdad Afshari
@MehrdadAfshari Wen interessiert es, was "die meisten Leute" tun? "Die meisten Leute" liegen in vielen Dingen falsch. Post-Inc / Decrement, bei dem der Vorwert niemals verwendet wird, ist zumindest theoretisch falsch und ineffizient - unabhängig davon, wie oft er überall blind in unterdurchschnittlichem Beispielcode verwendet wird. Sie sollten schlechte Praktiken nicht fördern, nur um Menschen, die es noch nicht besser wissen, die Dinge vertrauter erscheinen zu lassen.
underscore_d
2

Der erste ist typrichtig und im engeren Sinne korrekt. (Wenn Sie darüber nachdenken, kann die Größe niemals kleiner als Null sein.) Diese Warnung scheint mir jedoch einer der guten Kandidaten zu sein, um ignoriert zu werden.

Charlie Martin
quelle
2
Ich denke, es ist ein schrecklicher Kandidat, ignoriert zu werden - es ist einfach zu beheben, und hin und wieder treten echte Fehler auf, wenn Fehler beim unangemessenen Vergleichen von signierten / nicht signierten Werten auftreten. Wenn in diesem Fall beispielsweise die Größe größer als INT_MAX ist, wird die Schleife niemals beendet.
Steve Jessop
... oder vielleicht endet es sofort. Einer der Beiden. Hängt davon ab, ob der vorzeichenbehaftete Wert zum Vergleich in vorzeichenlos oder der vorzeichenlos in vorzeichenbehaftet konvertiert wird. Auf einer 64-Bit-Plattform mit einem 32-Bit-Int würde das Int jedoch wie win64 auf size_t hochgestuft, und die Schleife endet nie.
Steve Jessop
@SteveJessop: Man kann nicht mit Sicherheit sagen, dass die Schleife niemals endet. Bei der Iteration wann verursacht i == INT_MAXdann i++undefiniertes Verhalten. An diesem Punkt kann alles passieren.
Ben Voigt
@ BenVoigt: wahr, und bietet immer noch keinen Grund, die Warnung zu ignorieren :-)
Steve Jessop
2

Überlegen Sie, ob Sie überhaupt iterieren müssen

Der <algorithm>Standard-Header bietet uns dafür folgende Möglichkeiten:

using std::begin;  // allows argument-dependent lookup even
using std::end;    // if the container type is unknown here
auto sum = std::accumulate(begin(polygon), end(polygon), 0);

Andere Funktionen in der Algorithmusbibliothek führen allgemeine Aufgaben aus. Stellen Sie sicher, dass Sie wissen, was verfügbar ist, wenn Sie sich Mühe sparen möchten.

Toby Speight
quelle
1

Dunkles, aber wichtiges Detail: Wenn Sie wie folgt "for (auto it)" sagen, erhalten Sie eine Kopie des Objekts, nicht das eigentliche Element:

struct Xs{int i} x;
x.i = 0;
vector <Xs> v;
v.push_back(x);
for(auto it : v)
    it.i = 1;         // doesn't change the element v[0]

Um die Elemente des Vektors zu ändern, müssen Sie den Iterator als Referenz definieren:

for(auto &it : v)
Pierre
quelle
1

Wenn Ihr Compiler dies unterstützt, können Sie einen Bereich verwenden, der auf basiert, um auf die Vektorelemente zuzugreifen:

vector<float> vertices{ 1.0, 2.0, 3.0 };

for(float vertex: vertices){
    std::cout << vertex << " ";
}

Drucke: 1 2 3. Beachten Sie, dass Sie diese Technik nicht zum Ändern der Elemente des Vektors verwenden können.

Brett L.
quelle
0

Die beiden Codesegmente funktionieren gleich. Die vorzeichenlose int "-Route ist jedoch korrekt. Die Verwendung von vorzeichenlosen int-Typen funktioniert besser mit dem Vektor in der von Ihnen verwendeten Instanz. Wenn Sie die Elementfunktion size () für einen Vektor aufrufen, wird ein vorzeichenloser ganzzahliger Wert zurückgegeben, sodass Sie die Variable vergleichen möchten "i" auf einen Wert seines eigenen Typs.

Wenn Sie sich immer noch nicht sicher sind, wie "unsigned int" in Ihrem Code aussieht, versuchen Sie es mit "uint". Dies ist im Grunde eine verkürzte Version von "unsigned int" und es funktioniert genauso. Sie müssen auch keine anderen Header einfügen, um es zu verwenden.


quelle
Eine vorzeichenlose Ganzzahl für size () ist in C ++ nicht unbedingt gleich "unsigned int". In diesem Fall ist "unsigned integer" häufig eine 64-Bit-Ganzzahl ohne Vorzeichen, während "unsigned int" normalerweise 32 Bit beträgt.
Medran
0

Fügen Sie dies hinzu, da ich es in keiner Antwort erwähnt finden konnte: Für die indexbasierte Iteration können wir verwenden, decltype(vec_name.size())welche zu bewerten wärestd::vector<T>::size_type

Beispiel

for(decltype(v.size()) i{ 0 }; i < v.size(); i++) {
    /* std::cout << v[i]; ... */
}
Bharat S.
quelle