Iteración sobre std :: vector: variable de índice sin signo vs con signo

470

¿Cuál es la forma correcta de iterar sobre un vector en C ++?

Considere estos dos fragmentos de código, este funciona bien:

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

y éste:

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

que genera warning: comparison between signed and unsigned integer expressions.

Soy nuevo en el mundo de C ++, por lo que la unsignedvariable me parece un poco aterradora y sé que las unsignedvariables pueden ser peligrosas si no se usan correctamente, entonces, ¿es esto correcto?

Yuval Adam
fuente
10
El sin signo es correcto porque polygon.size () es de tipo unsigned. Sin signo significa positivo siempre o 0. Eso es todo lo que significa. Entonces, si el uso de la variable siempre es solo para conteos, entonces sin signo es la opción correcta.
Adam Bruss
3
@AdamBruss .size()no es del tipo unsignedaka unsigned int. Es de tipo std::size_t.
underscore_d
1
@underscore_d size_t es un alias para unsigned.
Adam Bruss
2
@AdamBruss No. std::size_tes una definición de tipo definida por la implementación. Ver el estándar. std::size_tpuede ser equivalente a unsigneden su implementación actual, pero eso no es relevante. Fingir que puede resultar en código no portátil y comportamiento indefinido.
underscore_d
2
@LF ... claro, lo cual es probablemente std::size_ten la práctica. ¿Crees que ya hemos cubierto todo en este torrente de comentarios durante más de 6 años?
underscore_d

Respuestas:

817

Para iterar hacia atrás, vea esta respuesta .

Iterar hacia delante es casi idéntico. Simplemente cambie los iteradores / decremento de intercambio por incremento. Deberías preferir iteradores. Algunas personas le dicen que use std::size_tcomo tipo de variable de índice. Sin embargo, eso no es portátil. Siempre use el size_typetypedef del contenedor (Si bien podría salirse con la suya solo con una conversión en el caso de iteración hacia adelante, en realidad podría salir mal en el caso de iteración hacia atrás cuando se usa std::size_t, en caso de que std::size_tsea ​​más ancho de lo que es el typedef size_type) :


Usando std :: vector

Usando iteradores

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

Lo importante es que siempre use el formulario de incremento de prefijo para los iteradores cuyas definiciones no conoce. Eso asegurará que su código se ejecute lo más genérico posible.

Usando Range C ++ 11

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

Usando índices

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

Usar matrices

Usando iteradores

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

Usando Range C ++ 11

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

Usando índices

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

Sin sizeofembargo, lea en la respuesta iterativa hacia atrás a qué problema puede dar lugar el enfoque.

Johannes Schaub - litb
fuente
tipo de punteros de tamaño: el uso de difference_type podría ser más portátil. pruebe iterator_traits <element_type *> :: difference_type. esto es un bocado de una declaración, pero es más portátil ...
wilhelmtell
wilhelmtell, ¿para qué debo usar difference_type? sizeof está definido para devolver size_t :) no te entiendo. Si tuviera que restar los punteros entre sí, diferencia_tipo sería la elección correcta.
Johannes Schaub - litb
La iteración sobre matrices utilizando la técnica que ha mencionado en esta publicación no funcionará si la iteración se realiza en una función en una matriz que se pasa a esa función. Porque sizeof array solo devolverá el puntero sizeof.
systemsfault
1
@Nils, estoy de acuerdo en que usar contadores de bucle sin firmar es una mala idea. pero debido a que la biblioteca estándar usa tipos enteros sin signo para el índice y el tamaño, prefiero los tipos de índice sin signo para la biblioteca estándar. en consecuencia, otras bibliotecas solo usan tipos con signo, como Qt lib.
Johannes Schaub - litb
32
Actualización para C ++ 11: rango basado para bucle. for (auto p : polygon){sum += p;}
Siyuan Ren el
170

Pasaron cuatro años, Google me dio esta respuesta. Con el estándar C ++ 11 (también conocido como C ++ 0x ), existe una nueva forma agradable de hacerlo (al precio de romper la compatibilidad con versiones anteriores): la nueva autopalabra clave. Le ahorra la molestia de tener que especificar explícitamente el tipo de iterador a usar (repitiendo el tipo de vector nuevamente), cuando es obvio (para el compilador), qué tipo usar. Con vser tu vector, puedes hacer algo como esto:

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

C ++ 11 va más allá y le brinda una sintaxis especial para iterar sobre colecciones como vectores. Elimina la necesidad de escribir cosas que siempre son iguales:

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

Para verlo en un programa de trabajo, cree un archivo 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;
}

Al escribir esto, cuando compila esto con g ++ , normalmente necesita configurarlo para que funcione con el nuevo estándar dando una bandera adicional:

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

Ahora puedes ejecutar el ejemplo:

$ ./auto
17
12
23
42

Tenga en cuenta que las instrucciones para compilar y ejecutar son específicas del compilador gnu c ++ en Linux , el programa debe ser independiente de la plataforma (y el compilador).

kratenko
fuente
77
C ++ 11 te dafor (auto& val: vec)
Flexo
@flexo Gracias, no sé cómo podría olvidar eso. No estoy haciendo suficiente C ++, supongo. No podía creer que haya algo tan práctico (en realidad, pensaba que era la sintaxis de JavaScript). Cambié la respuesta para incluir eso.
kratenko
Tu respuesta es muy buena. Es desagradable que la versión predeterminada de g ++ en varios devkits del sistema operativo sea inferior a 4.3, lo que hace que no funcione.
Ratata Tata
¿Necesita inicializar el vector con std::vector<int> v = std::vector<int>();, o podría simplemente haber usado en su std::vector<int> v;lugar?
Bill Cheatham
@BillCheatham Bueno, lo probé sin inicializar y funcionó, así que parece que funciona sin él.
kratenko
44

En el caso específico de su ejemplo, usaría los algoritmos STL para lograr esto.

#include <numeric> 

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

Para un caso más general, pero aún bastante simple, elegiría:

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

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

Con respecto a la respuesta de Johannes Schaub:

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

Eso puede funcionar con algunos compiladores pero no con gcc. El problema aquí es la pregunta si std :: vector :: iterator es un tipo, una variable (miembro) o una función (método). Recibimos el siguiente error con 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 solución está usando la palabra clave 'typename' como se dice:

typename std::vector<T*>::iterator it = v.begin();
for( ; it != v.end(); ++it) {
...
Polat Tuzla
fuente
2
Debe explicar que esto solo se aplica cuando se Ttrata de un argumento de plantilla y, por lo tanto, la expresión std::vector<T*>::iteratores un nombre dependiente. Para que un nombre dependiente se analice como un tipo, debe estar precedido por la typenamepalabra clave, como lo indica el diagnóstico.
Restablece a Mónica el
17

Una llamada a vector<T>::size()devuelve un valor de tipo std::vector<T>::size_type, no int, unsigned int u otro.

También, en general, la iteración sobre un contenedor en C ++ se realiza mediante iteradores , como este.

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

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

Donde T es el tipo de datos que almacena en el vector.

O el uso de los diferentes algoritmos de iteración ( std::transform, std::copy, std::fill, std::for_eachetc.).

Jasper Bekkers
fuente
Los iteradores son generalmente una buena idea, aunque dudo que sea necesario almacenar "fin" en una variable separada y todo se puede hacer dentro de una declaración for (;;).
Saulius Žemaitaitis el
1
Sé que begin () y end () son tiempo constante amortizado, pero generalmente encuentro que esto es más legible que agrupar todo en una línea.
Jasper Bekkers
3
Puede dividir el for en líneas separadas para mejorar la legibilidad. Declarar iteradores fuera del ciclo significa que necesita un nombre de iterador diferente para cada ciclo sobre contenedores de diferentes tipos.
Jay Conrod
Soy consciente de todas las diferencias, y básicamente se trata de preferencias personales; generalmente es así como termino haciendo las cosas.
Jasper Bekkers
2
@pihentagy Supongo que sería configurarlo en la primera sección del ciclo for. p.ej. for (auto i = polygon.begin (), end = polygon.end (); i! = end; i ++)
Jasper Bekkers
11

Uso size_t:

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

Citando Wikipedia :

Los archivos de encabezado stdlib.h y stddef.h definen un tipo de datos llamado size_tque se utiliza para representar el tamaño de un objeto. Las funciones de biblioteca que toman tamaños esperan que sean de tipo size_t, y el operador sizeof se evalúa como size_t.

El tipo real de size_tdepende de la plataforma; Un error común es asumir que size_tes lo mismo que unsigned int, lo que puede conducir a errores de programación, particularmente a medida que las arquitecturas de 64 bits se vuelven más frecuentes.

Igor Oks
fuente
size_t OK para vector, ya que debe almacenar todos los objetos en una matriz (también un objeto), ¡pero una lista std :: puede contener más de elementos size_t!
MSalters
1
size_t normalmente es suficiente para enumerar todos los bytes en el espacio de direcciones de un proceso. Si bien puedo ver cómo este puede no ser el caso en algunas arquitecturas exóticas, prefiero no preocuparme por eso.
AFAIK se recomienda en #include <cstddef>lugar de <stddef.h>o, peor aún, la totalidad [c]stdliby el uso en std::size_tlugar de la versión no calificada, y lo mismo para cualquier otra situación en la que pueda elegir entre <cheader>y <header.h>.
underscore_d
7

Un poco de historia:

Para representar si un número es negativo o no, la computadora utiliza un bit de "signo". intes un tipo de datos con signo, lo que significa que puede contener valores positivos y negativos (alrededor de -2 mil millones a 2 mil millones). Unsignedsolo puede almacenar números positivos (y dado que no desperdicia un poco en los metadatos, puede almacenar más: de 0 a aproximadamente 4 mil millones).

std::vector::size()devuelve un unsigned, porque ¿cómo podría un vector tener longitud negativa?

La advertencia le dice que el operando derecho de su declaración de desigualdad puede contener más datos que el izquierdo.

Esencialmente, si tiene un vector con más de 2 mil millones de entradas y usa un número entero para indexar, encontrará problemas de desbordamiento (el int volverá a los 2 mil millones negativos).

ecoffey
fuente
6

Usualmente uso BOOST_FOREACH:

#include <boost/foreach.hpp>

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

Funciona en contenedores STL, matrices, cadenas de estilo C, etc.

Martin Cote
fuente
2
Buena respuesta a alguna otra pregunta (¿cómo debería recorrer un vector?), Pero completamente no es en absoluto lo que el PO estaba pidiendo (¿cuál es el significado de la advertencia sobre una variable sin signo?)
abelenky
3
Bueno, preguntó cuál era la forma correcta de iterar sobre un vector. Entonces parece lo suficientemente relevante. La advertencia es solo por qué no está contento con su solución actual.
jalf
5

Para completar, la sintaxis de C ++ 11 habilita una versión más para los iteradores ( ref ):

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

Que también es cómodo para la iteración inversa

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

En C ++ 11

Usaría algoritmos generales como for_eachevitar evitar buscar el tipo correcto de iterador y expresión lambda para evitar funciones / objetos con nombre adicionales.

El breve ejemplo "bonito" para su caso particular (suponiendo que el polígono es un vector de enteros):

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

probado en: http://ideone.com/i6Ethd

No olvide incluir: algoritmo y, por supuesto, vector :)

Microsoft también tiene un buen ejemplo de esto:
fuente: 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
fuente
4
for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it; 
Mehrdad Afshari
fuente
2
Para el vector esto está bien, pero genéricamente es mejor usar ++ en lugar de ++, en caso de que el iterador en sí no sea trivial.
Steve Jessop el
Personalmente, estoy acostumbrado a usar ++ i, pero creo que la mayoría de las personas prefieren el estilo i ++ (el fragmento de código VS predeterminado para "for" es i ++). Solo un pensamiento
Mehrdad Afshari
@MehrdadAfshari ¿A quién le importa lo que hace "la mayoría de la gente"? "La mayoría de la gente" está equivocada acerca de muchas cosas. Post-inc / decrement donde el valor pre nunca se usa es incorrecto e ineficiente, al menos en teoría, independientemente de la frecuencia con la que se usa ciegamente en código de ejemplo por debajo del par en todas partes. No debe alentar las malas prácticas solo para hacer que las cosas parezcan más familiares para las personas que aún no conocen mejor.
underscore_d
2

El primero es el tipo correcto y correcto en un sentido estricto. (Si lo piensa, el tamaño nunca puede ser inferior a cero). Sin embargo, esa advertencia me parece uno de los buenos candidatos para ser ignorado.

Charlie Martin
fuente
2
Creo que es un candidato terrible para ser ignorado: es fácil de solucionar y, de vez en cuando, se producen errores genuinos debido a errores que comparan valores firmados / no firmados de manera inapropiada. Por ejemplo, en este caso, si el tamaño es mayor que INT_MAX, el ciclo nunca termina.
Steve Jessop el
... o tal vez termina de inmediato. Uno de los dos. Depende de si el valor firmado se convierte en sin signo para la comparación, o si el valor sin signo se convierte en firmado. Sin embargo, en una plataforma de 64 bits con un int de 32 bits, como win64, el int se promocionaría a size_t, y el ciclo nunca termina.
Steve Jessop el
@SteveJessop: No se puede decir con certeza que el ciclo nunca termina. En la iteración cuando i == INT_MAX, luego i++causa un comportamiento indefinido. En este punto, puede pasar cualquier cosa.
Ben Voigt
@BenVoigt: cierto, y aún no proporciona motivos para ignorar la advertencia :-)
Steve Jessop
2

Considere si necesita iterar

El <algorithm>encabezado estándar nos proporciona facilidades para esto:

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

Otras funciones en la biblioteca de algoritmos realizan tareas comunes: asegúrese de saber qué hay disponible si desea ahorrar esfuerzo.

Toby Speight
fuente
1

Detalle oscuro pero importante: si dice "for (auto it)" de la siguiente manera, obtendrá una copia del objeto, no del elemento real:

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]

Para modificar los elementos del vector, debe definir el iterador como referencia:

for(auto &it : v)
Pierre
fuente
1

Si su compilador lo admite, puede usar un rango basado para acceder a los elementos vectoriales:

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

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

Impresiones: 1 2 3. Tenga en cuenta que no puede usar esta técnica para cambiar los elementos del vector.

Brett L
fuente
0

Los dos segmentos de código funcionan igual. Sin embargo, la ruta unsigned int "es correcta. El uso de los tipos unsigned int funcionará mejor con el vector en la instancia en que lo usó. Llamar a la función de miembro size () en un vector devuelve un valor entero sin signo, por lo que desea comparar la variable "i" a un valor de su propio tipo.

Además, si todavía está un poco incómodo acerca de cómo se ve "unsigned int" en su código, pruebe con "uint". Esta es básicamente una versión abreviada de "unsigned int" y funciona exactamente igual. Tampoco necesita incluir otros encabezados para usarlo.


fuente
El entero sin signo para size () no necesariamente equivale a "unsigned int" en términos de C ++, a menudo 'entero sin signo' en este caso es un entero sin signo de 64 bits, mientras que 'unsigned int' suele ser de 32 bits.
Medran
0

Agregando esto ya que no pude encontrarlo mencionado en ninguna respuesta: para la iteración basada en índices, podemos usar el decltype(vec_name.size())que evaluaríastd::vector<T>::size_type

Ejemplo

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