Iteration over vector in C++

Question

What is the correct way of iterating over a vector in C++?

Consider these two code fragments, this one works fine:

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

and this one:

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

which generates warning: comparison between signed and unsigned integer expressions.

I'm new in the world of C++, so the unsigned variable looks a bit frightening to me and I know unsigned variables can be dangerous if not used correctly, so - is this correct?

Answer 1

Your polygon.size() returns an unsigned. The compiler complains when you comapre it with int i.

Answer 2

Use size_t :

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

Quoting Wikipedia:

The stdlib.h and stddef.h header files define a datatype called size_t which is used to represent the size of an object. Library functions that take sizes expect them to be of type size_t, and the sizeof operator evaluates to size_t.

The actual type of size_t is platform-dependent; a common mistake is to assume size_t is the same as unsigned int, which can lead to programming errors, particularly as 64-bit architectures become more prevalent.

Answer 3

A call to vector<T>::size() returns a value of type std::vector<T>::size_type, not int, unsigned int or otherwise.

Also generally iteration over a container in C++ is done using iterators, like this.

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

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

Where T is the type of data you store in the vector.

Or using the different iteration algorithms (std::transform, std::copy, std::fill, std::for_each et cetera).

Answer 4

for (vector<int>::iterator it = polygon.begin(); it != polygon.end(); it++)
    sum += *it;

Answer 5

A bit of history:

To represent whether a number is negative or not computer use a 'sign' bit. int is a signed data type meaning it can hold positive and negative values (about -2billion to 2billion). Unsigned can only store positive numbers (and since it doesn't waste a bit on metadata it can store more: 0 to about 4billion).

std::vectore::size() returns a unsigned, for how could a vector have negative length?

The warning is telling you that the right operand of your inequality statement can hold more data then the left.

Essentially if you have a vector with more then 2 billion entries and you use a integer to index into you'll hit overflow problems (the int will wrap back around to negative 2 billion).

Answer 6

The first is type correct, and correct in some strict sense. (If you think about is, size can never be less than zero.) That warning strikes me as one of the good candidates for being ignored, though.

Answer 7

Iterating Backwards

See this answer.

Iterating Forwards

This is almost identical. Just change the iterators / swap decrement by increment. You should prefer iterators. Some people tell you to use std::size_t as the index variable type. However, that is not portable. Always use the size_type typedef of the container (While you could get away with only a conversion in the forward iterating case, it could actually go wrong all the way in the backward iterating case when using std::size_t, in case std::size_t is wider than what is the typedef of size_type):

Using std::vector

Using iterators

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

Important is, always use the prefix increment form for iterators whose definitions you don't know. That will ensure your code runs as generic as possible.

Using indices

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

Using arrays

Using iterators

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

Using indices

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

Read in the backward iterating answer what problem the sizeof approach can yield to, though.

Answer 8

I usually use BOOST_FOREACH:

#include <boost/foreach.hpp>

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

It works on STL containers, arrays, C-style strings, etc.

Answer 9

In the specific case in your example, I'd use the STL algorithms to accomplish this.

#include <numeric> 

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

For a more general, but still fairly simple case, I'd go with:

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

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

Answer 10

Regarding Johannes Schaub's answer:

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

That may work with some compilers but not with gcc. The problem here is the question if std::vector::iterator is a type, a variable (member) or a function (method). We get the following error with 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

The solution is using the keyword 'typename' as told:

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