Iteration over std::vector: unsigned vs signed index variable?

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

Actually, the best way to iterate over a vector (or any container, for that matter) is to use that container's iterator:

for( vector<int>::iterator itr = poly.begin(); itr != poly.end(); ++itr )

sum += *itr;

All containers (vector, lists, deque, etc) include iterators, and the means to traverse them; there's also a means to reverse iterate. They all have the concept of begin() and end().

That aside, let's talk about unsigned and what it means. All of the integer data types (int, short, long, etc) in C/C++ consist of bytes storage, the amount of storage based on the specific type and the specific operating system (32-bit vs 64-bit). Let's look at the smallest integer type -- char. (Yeah, it can be used to store numeric values; even though you do assignments char ch = 'a';, the underlaying code would show 'a' as the value 97 -- the ASCII value of 'a').

A char is one byte long, 8-bits. "bits" are binary digits, a device that can be either 0 or 1. If you were to look at 'a' (97) in binary, you would get 0110-0001. Drawing that, you get the below:

+---+---+---+---+---+---+---+---+

| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 |

+---+---+---+---+---+---+---+---+

All zeros would be zero (of course) and all ones is 255. (The way to calculate is by doing 2^N - 1, where N is the number of bits. So 2⁸ = 256, take away 1 is 255).

Now a computer only deals with 1s and 0s, and don't have a concept of negative numbers. The way to overcome this problem was to use one of the above bits as a flag -- the sign bit. This flag is used to indicate whether or not the value is positive or negative, and it is in this example the left most bit (a conversation about big and little endians is for a whole other time). Doing so, however, reduces the number of bits available to hold the numeric value. Reserving the sign bit allows for a range of -128 to 127, whereas the range without the sign bit is 0 to 255.

This is the diference between signed (the default) and unsigned - that sign bit. The range an integer type can hold is based on it, and is defined in limits.h.

When to use signed vs unsigned? That's simple answer -- will your value ever be negative? If no, then use unsigned. For your code example, the number of items in the vector is never negative, so size() returns an unsigned value (best if you use size_t for the type).

One last thing to know -- a signed value can 'overflow' into negative number. This overflow is when sign bit gets flipped by accident consider 127:

+---+---+---+---+---+---+---+---+

| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

+---+---+---+---+---+---+---+---+

If you add one to this value, it overlows to this: (add 1+1 you get 2; in base 2 (binary), that's 10, so carry the one)

+---+---+---+---+---+---+---+---+

| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

+---+---+---+---+---+---+---+---+

The sign bit has been flipped, and all of sudden I have a negative number! (-128, in this case).