Itération sur std :: vector: variable d'index non signé vs signé

470

Quelle est la bonne façon d'itérer sur un vecteur en C ++?

Considérez ces deux fragments de code, celui-ci fonctionne très bien:

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

et celui-là:

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

qui génère warning: comparison between signed and unsigned integer expressions.

Je suis nouveau dans le monde du C ++, donc la unsignedvariable me semble un peu effrayante et je sais que les unsignedvariables peuvent être dangereuses si elles ne sont pas utilisées correctement, alors - est-ce correct?

Yuval Adam
la source
10
Celui non signé est correct car polygon.size () est de type unsigned. Non signé signifie toujours positif ou 0. C'est tout ce que cela signifie. Donc, si l'utilisation de la variable est toujours uniquement pour les nombres, alors non signé est le bon choix.
Adam Bruss
3
@AdamBruss .size()n'est pas de type unsignedaka unsigned int. C'est de type std::size_t.
underscore_d
1
@underscore_d size_t est un alias pour non signé.
Adam Bruss
2
@AdamBruss No. std::size_test un typedef défini par _implementation. Voir la norme. std::size_tpeut être équivalent à unsignedvotre implémentation actuelle, mais ce n'est pas pertinent. Le faire semblant peut entraîner un code non portable et un comportement indéfini.
underscore_d
2
@LF ... bien sûr, ce qui est probablement std::size_ten pratique. Pensez-vous que nous avons tout couvert encore dans ce flux de commentaires décousus sur 6 ans?
underscore_d

Réponses:

817

Pour itérer en arrière, voir cette réponse .

L'itération vers l'avant est presque identique. Il suffit de changer les itérateurs / décrément de swap par incrément. Vous devriez préférer les itérateurs. Certaines personnes vous disent d'utiliser std::size_tle type de variable d'index. Cependant, ce n'est pas portable. Utilisez toujours le size_typetypedef du conteneur (Bien que vous puissiez vous en sortir avec seulement une conversion dans le cas d'itération vers l'avant, il pourrait en fait se tromper complètement dans le cas d'itération vers l'arrière lors de l'utilisation std::size_t, au cas où std::size_test plus large que ce qui est le typedef de size_type) :


Utilisation de std :: vector

Utilisation d'itérateurs

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

L'important est de toujours utiliser le formulaire d'incrémentation de préfixe pour les itérateurs dont vous ne connaissez pas les définitions. Cela garantira que votre code est aussi générique que possible.

Utilisation de Range C ++ 11

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

Utiliser des indices

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

Utilisation de tableaux

Utilisation d'itérateurs

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

Utilisation de Range C ++ 11

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

Utiliser des indices

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

Lisez la réponse itérative à l'envers à quel problème l' sizeofapproche peut céder, cependant.

Johannes Schaub - litb
la source
taille des pointeurs: l'utilisation de difference_type pourrait être plus portable. essayez iterator_traits <element_type *> :: difference_type. c'est une bouchée d'une déclaration, mais c'est plus portable ...
wilhelmtell
wilhelmtell, pour quoi dois-je utiliser difference_type? sizeof est défini pour renvoyer size_t :) je ne vous comprends pas. si je devais soustraire les pointeurs les uns des autres, difference_type serait le bon choix.
Johannes Schaub - litb
l'itération sur des tableaux utilisant la technique que vous avez mentionnée dans ce post ne fonctionnera pas si l'itération est effectuée dans une fonction sur un tableau passé à cette fonction. Parce que sizeof array ne renverra que le pointeur sizeof.
systemsfault
1
@Nils, je suis d'accord que l'utilisation de compteurs de boucles non signés est une mauvaise idée. mais parce que la bibliothèque standard utilise des types entiers non signés pour l'index et la taille, je préfère les types d'index non signés pour la bibliothèque standard. d'autres bibliothèques n'utilisent par conséquent que des types signés, comme la librairie Qt.
Johannes Schaub - litb
32
Mise à jour pour C ++ 11: plage basée sur la boucle. for (auto p : polygon){sum += p;}
Siyuan Ren
170

Quatre ans se sont écoulés, Google m'a donné cette réponse. Avec le standard C ++ 11 (alias C ++ 0x ), il existe en fait une nouvelle façon agréable de le faire (au prix de briser la compatibilité descendante): le nouveau automot-clé. Cela vous évite d'avoir à spécifier explicitement le type d'itérateur à utiliser (en répétant à nouveau le type de vecteur), quand il est évident (pour le compilateur), quel type utiliser. En vétant votre vector, vous pouvez faire quelque chose comme ceci:

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

C ++ 11 va encore plus loin et vous donne une syntaxe spéciale pour itérer sur des collections comme des vecteurs. Il supprime la nécessité d'écrire des choses qui sont toujours les mêmes:

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

Pour le voir dans un programme de travail, créez un fichier 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;
}

Au moment d'écrire ceci, lorsque vous le compilez avec g ++ , vous devez normalement le configurer pour qu'il fonctionne avec la nouvelle norme en donnant un indicateur supplémentaire:

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

Vous pouvez maintenant exécuter l'exemple:

$ ./auto
17
12
23
42

Veuillez noter que les instructions sur la compilation et l'exécution sont spécifiques au compilateur gnu c ++ sous Linux , le programme doit être indépendant de la plateforme (et du compilateur).

kratenko
la source
7
C ++ 11 vous donnefor (auto& val: vec)
Flexo
@flexo Merci, je ne sais pas comment je pourrais oublier ça. Je ne fais pas assez de C ++, je suppose. Je ne pouvais pas croire qu'il y ait quelque chose de pratique (pensait que c'était la syntaxe JavaScript, en fait). J'ai changé la réponse pour l'inclure.
kratenko
Votre réponse est très agréable. Il est désagréable que la version par défaut de g ++ dans divers devkits de système d'exploitation soit inférieure à 4.3, ce qui ne fonctionne pas.
Ratata Tata
Avez-vous besoin d'initialiser le vecteur avec std::vector<int> v = std::vector<int>();, ou auriez-vous pu simplement l'utiliser à la std::vector<int> v;place?
Bill Cheatham
@BillCheatham Eh bien - je viens de l'essayer sans l'initialisation, et cela a fonctionné, il semble donc que cela fonctionne sans.
kratenko
44

Dans le cas spécifique de votre exemple, j'utiliserais les algorithmes STL pour accomplir cela.

#include <numeric> 

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

Pour un cas plus général, mais toujours assez simple, je choisirais:

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

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

Concernant la réponse de Johannes Schaub:

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

Cela peut fonctionner avec certains compilateurs mais pas avec gcc. Le problème ici est la question de savoir si std :: vector :: iterator est un type, une variable (membre) ou une fonction (méthode). Nous obtenons l'erreur suivante avec 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

La solution utilise le mot-clé 'typename' comme indiqué:

typename std::vector<T*>::iterator it = v.begin();
for( ; it != v.end(); ++it) {
...
Polat Tuzla
la source
2
Vous devez préciser que cela ne s'applique que lorsque Test un argument de modèle, et donc l'expression std::vector<T*>::iteratorest un nom dépendant. Pour qu'un nom dépendant soit analysé en tant que type, il doit être ajouté par le typenamemot - clé, comme l'indique le diagnostic.
Rétablir Monica le
17

Un appel à vector<T>::size()renvoie une valeur de typestd::vector<T>::size_type , not int, unsigned int ou autre.

De manière générale, l'itération sur un conteneur en C ++ se fait à l'aide d' itérateurs , comme celui-ci.

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

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

Où T est le type de données que vous stockez dans le vecteur.

Ou en utilisant les différents algorithmes d'itération ( std::transform, std::copy, std::fill, std::for_eachetc.).

Jasper Bekkers
la source
Les itérateurs sont généralement une bonne idée, bien que je doute qu'il y ait un besoin de stocker "end" dans une variable séparée et tout cela peut être fait dans une instruction for (;;).
Saulius Žemaitaitis le
1
Je sais que begin () et end () sont amortis en temps constant, mais je trouve généralement que cela est plus lisible que de tout entasser sur une seule ligne.
Jasper Bekkers du
3
Vous pouvez diviser le for en lignes distinctes pour améliorer la lisibilité. La déclaration d'itérateurs en dehors de la boucle signifie que vous avez besoin d'un nom d'itérateur différent pour chaque boucle sur des conteneurs de différents types.
Jay Conrod du
Je suis conscient de toutes les différences, et ce qui se résume essentiellement à une préférence personnelle; c'est généralement ainsi que je finis par faire les choses.
Jasper Bekkers
2
@pihentagy Je suppose que ce serait de le définir dans la première section de la boucle for. par exemple. for (auto i = polygon.begin (), end = polygon.end (); i! = end; i ++)
Jasper Bekkers
11

Utilisation size_t:

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

Citant Wikipédia :

Les fichiers d'en-tête stdlib.h et stddef.h définissent un type de données appelé size_tqui est utilisé pour représenter la taille d'un objet. Les fonctions de bibliothèque qui prennent des tailles s'attendent à ce qu'elles soient de type size_t, et l'opérateur sizeof est évalué size_t.

Le type réel de size_tdépend de la plate-forme; une erreur courante consiste à supposer qu'elle size_test identique à un entier non signé, ce qui peut entraîner des erreurs de programmation, en particulier lorsque les architectures 64 bits deviennent plus courantes.

Igor Oks
la source
size_t OK pour le vecteur, car il doit stocker tous les objets dans un tableau (lui-même un objet aussi) mais une liste std :: peut contenir plus que des éléments size_t!
MSalters
1
size_t est normalement suffisant pour énumérer tous les octets dans l'espace d'adressage d'un processus. Bien que je puisse voir comment cela peut ne pas être le cas sur certaines architectures exotiques, je préfère ne pas m'en inquiéter.
AFAIK, il est recommandé de #include <cstddef>plutôt que <stddef.h>ou, pire, l'intégralité de [c]stdlibet d'utiliser std::size_tplutôt que la version non qualifiée - et même pour toute autre situation où vous avez le choix entre <cheader>et <header.h>.
underscore_d
7

Un peu d'histoire:

Pour représenter si un nombre est négatif ou non, utilisez un bit «signe». intest un type de données signé, ce qui signifie qu'il peut contenir des valeurs positives et négatives (environ -2 à 2 milliards). Unsignedne peut stocker que des nombres positifs (et comme cela ne gaspille pas un peu de métadonnées, il peut en stocker plus: 0 à environ 4 milliards).

std::vector::size()renvoie un unsigned, car comment un vecteur peut-il avoir une longueur négative?

L'avertissement vous indique que l'opérande droit de votre déclaration d'inégalité peut contenir plus de données que la gauche.

Essentiellement, si vous avez un vecteur avec plus de 2 milliards d'entrées et que vous utilisez un entier pour vous indexer, vous rencontrerez des problèmes de débordement (l'int se terminera par 2 milliards négatifs).

ecoffey
la source
6

J'utilise habituellement BOOST_FOREACH:

#include <boost/foreach.hpp>

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

Il fonctionne sur les conteneurs STL, les tableaux, les chaînes de style C, etc.

Martin Cote
la source
2
Bonne réponse à une autre question (comment dois-je itérer un vecteur?), Mais complètement pas du tout ce que le PO demandait (quelle est la signification de l'avertissement concernant une variable non signée?)
abelenky
3
Eh bien, il a demandé quelle était la bonne façon d'itérer sur un vecteur. Cela semble donc suffisamment pertinent. L'avertissement est juste pourquoi il n'est pas satisfait de sa solution actuelle.
jalf
5

Pour être complète, la syntaxe C ++ 11 n'autorise qu'une seule autre version pour les itérateurs ( ref ):

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

Ce qui est également confortable pour une itération inverse

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

En C ++ 11

J'utiliserais des algorithmes généraux comme for_each pour éviter de chercher le bon type d'itérateur et d'expression lambda pour éviter des fonctions / objets nommés supplémentaires.

Le petit exemple "joli" pour votre cas particulier (en supposant que le polygone est un vecteur d'entiers):

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

testé sur: http://ideone.com/i6Ethd

N'oubliez pas d' inclure: algorithme et, bien sûr, vecteur :)

Microsoft a en fait également un bel exemple à ce sujet:
source: 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
la source
4
for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it; 
Mehrdad Afshari
la source
2
Pour le vecteur, c'est bien, mais génériquement, il vaut mieux utiliser ++ plutôt que ++, au cas où l'itérateur lui-même n'est pas trivial.
Steve Jessop
Personnellement, j'ai l'habitude d'utiliser ++ i, mais je pense que la plupart des gens préfèrent le style i ++ (l'extrait de code VS par défaut pour "for" est i ++). Juste une pensée
Mehrdad Afshari
@MehrdadAfshari Qui se soucie de ce que "la plupart des gens" font? "la plupart des gens" se trompent sur beaucoup de choses. Post-inc / décrément où la valeur pré n'est jamais utilisée est erronée et inefficace, au moins en théorie - quelle que soit la fréquence à laquelle elle est utilisée aveuglément partout dans le code exemple inférieur à la normale. Vous ne devriez pas encourager les mauvaises pratiques simplement pour rendre les choses plus familières aux personnes qui ne connaissent pas encore mieux.
underscore_d
2

Le premier est de type correct et correct au sens strict. (Si vous y pensez, la taille ne peut jamais être inférieure à zéro.) Cependant, cet avertissement me semble être l'un des bons candidats pour être ignoré.

Charlie Martin
la source
2
Je pense que c'est un terrible candidat à ignorer - il est facile à corriger, et de temps en temps de véritables bogues se produisent en raison d'erreurs de comparaison inappropriée des valeurs signées / non signées. Par exemple dans ce cas, si la taille est supérieure à INT_MAX, la boucle ne se termine jamais.
Steve Jessop
... ou peut-être qu'il se termine immédiatement. Un des deux. Dépend si la valeur signée est convertie en non signé pour comparaison, ou si non signé est converti en signé. Sur une plate-forme 64 bits avec un int 32 bits, cependant, comme win64, l'int serait promu en taille_t, et la boucle ne se termine jamais.
Steve Jessop
@SteveJessop: Vous ne pouvez pas dire avec certitude que la boucle ne se termine jamais. À l'itération quand i == INT_MAX, i++provoque alors un comportement indéfini. À ce stade, tout peut arriver.
Ben Voigt
@BenVoigt: vrai, et ne fournit toujours pas de raisons d'ignorer l'avertissement :-)
Steve Jessop
2

Déterminez si vous devez répéter

L'en <algorithm>-tête standard nous fournit des installations pour cela:

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);

D'autres fonctions de la bibliothèque d'algorithmes effectuent des tâches courantes - assurez-vous de savoir ce qui est disponible si vous voulez vous épargner des efforts.

Toby Speight
la source
1

Détail obscur mais important: si vous dites "pour (auto it)" comme suit, vous obtenez une copie de l'objet, pas l'élément réel:

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]

Pour modifier les éléments du vecteur, vous devez définir l'itérateur comme référence:

for(auto &it : v)
Pierre
la source
1

Si votre compilateur le prend en charge, vous pouvez utiliser une plage basée sur pour accéder aux éléments vectoriels:

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

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

Impressions: 1 2 3. Notez que vous ne pouvez pas utiliser cette technique pour modifier les éléments du vecteur.

Brett L
la source
0

Les deux segments de code fonctionnent de la même manière. Cependant, la route unsigned int "est correcte. L'utilisation de types unsigned int fonctionnera mieux avec le vecteur dans l'instance que vous l'avez utilisée. L'appel de la fonction membre size () sur un vecteur renvoie une valeur entière non signée, vous voulez donc comparer la variable "i" à une valeur de son propre type.

De plus, si vous êtes encore un peu inquiet de l'apparence de "unsigned int" dans votre code, essayez "uint". Il s'agit essentiellement d'une version abrégée de "unsigned int" et cela fonctionne exactement de la même manière. Vous n'avez pas non plus besoin d'inclure d'autres en-têtes pour l'utiliser.


la source
Un entier non signé pour size () n'est pas nécessairement égal à «entier non signé» en termes C ++, souvent «entier non signé» dans ce cas est un entier non signé de 64 bits tandis que «entier non signé» est généralement de 32 bits.
Medran
0

Ajoutant cela car je ne l'ai pas trouvé mentionné dans aucune réponse: pour l'itération basée sur un index, nous pouvons utiliser decltype(vec_name.size()) ce qui évalueraitstd::vector<T>::size_type

Exemple

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