Iterator Loop vs index loop [duplicate]

Question

Possible Duplicate:
Why use iterators instead of array indices?

I'm reviewing my knowledge on C++ and I've stumbled upon iterators. One thing I want to know is what makes them so special and I want to know why this:

using namespace std;  vector<int> myIntVector; vector<int>::iterator myIntVectorIterator;  // Add some elements to myIntVector myIntVector.push_back(1); myIntVector.push_back(4); myIntVector.push_back(8);  for(myIntVectorIterator = myIntVector.begin();          myIntVectorIterator != myIntVector.end();         myIntVectorIterator++) {     cout<<*myIntVectorIterator<<" ";     //Should output 1 4 8 } 

is better than this:

using namespace std;  vector<int> myIntVector; // Add some elements to myIntVector myIntVector.push_back(1); myIntVector.push_back(4); myIntVector.push_back(8);  for(int y=0; y<myIntVector.size(); y++) {     cout<<myIntVector[y]<<" ";     //Should output 1 4 8 } 

And yes I know that I shouldn't be using the std namespace. I just took this example off of the cprogramming website. So can you please tell me why the latter is worse? What's the big difference?

Answer 1

The special thing about iterators is that they provide the glue between algorithms and containers. For generic code, the recommendation would be to use a combination of STL algorithms (e.g. find, sort, remove, copy) etc. that carries out the computation that you have in mind on your data structure (vector, list, map etc.), and to supply that algorithm with iterators into your container.

Your particular example could be written as a combination of the for_each algorithm and the vector container (see option 3) below), but it's only one out of four distinct ways to iterate over a std::vector:

1) index-based iteration

for (std::size_t i = 0; i != v.size(); ++i) {     // access element as v[i]      // any code including continue, break, return } 

Advantages: familiar to anyone familiar with C-style code, can loop using different strides (e.g. i += 2).

Disadvantages: only for sequential random access containers (vector, array, deque), doesn't work for list, forward_list or the associative containers. Also the loop control is a little verbose (init, check, increment). People need to be aware of the 0-based indexing in C++.

2) iterator-based iteration

for (auto it = v.begin(); it != v.end(); ++it) {     // if the current index is needed:     auto i = std::distance(v.begin(), it);       // access element as *it      // any code including continue, break, return } 

Advantages: more generic, works for all containers (even the new unordered associative containers, can also use different strides (e.g. std::advance(it, 2));

Disadvantages: need extra work to get the index of the current element (could be O(N) for list or forward_list). Again, the loop control is a little verbose (init, check, increment).

3) STL for_each algorithm + lambda

std::for_each(v.begin(), v.end(), [](T const& elem) {      // if the current index is needed:      auto i = &elem - &v[0];       // cannot continue, break or return out of the loop }); 

Advantages: same as 2) plus small reduction in loop control (no check and increment), this can greatly reduce your bug rate (wrong init, check or increment, off-by-one errors).

Disadvantages: same as explicit iterator-loop plus restricted possibilities for flow control in the loop (cannot use continue, break or return) and no option for different strides (unless you use an iterator adapter that overloads operator++).

4) range-for loop

for (auto& elem: v) {      // if the current index is needed:      auto i = &elem - &v[0];      // any code including continue, break, return } 

Advantages: very compact loop control, direct access to the current element.

Disadvantages: extra statement to get the index. Cannot use different strides.

What to use?

For your particular example of iterating over std::vector: if you really need the index (e.g. access the previous or next element, printing/logging the index inside the loop etc.) or you need a stride different than 1, then I would go for the explicitly indexed-loop, otherwise I'd go for the range-for loop.

For generic algorithms on generic containers I'd go for the explicit iterator loop unless the code contained no flow control inside the loop and needed stride 1, in which case I'd go for the STL for_each + a lambda.

Answer 2

With a vector iterators do no offer any real advantage. The syntax is uglier, longer to type and harder to read.

Iterating over a vector using iterators is not faster and is not safer (actually if the vector is possibly resized during the iteration using iterators will put you in big troubles).

The idea of having a generic loop that works when you will change later the container type is also mostly nonsense in real cases. Unfortunately the dark side of a strictly typed language without serious typing inference (a bit better now with C++11, however) is that you need to say what is the type of everything at each step. If you change your mind later you will still need to go around and change everything. Moreover different containers have very different trade-offs and changing container type is not something that happens that often.

The only case in which iteration should be kept if possible generic is when writing template code, but that (I hope for you) is not the most frequent case.

The only problem present in your explicit index loop is that size returns an unsigned value (a design bug of C++) and comparison between signed and unsigned is dangerous and surprising, so better avoided. If you use a decent compiler with warnings enabled there should be a diagnostic on that.

Note that the solution is not to use an unsiged as the index, because arithmetic between unsigned values is also apparently illogical (it's modulo arithmetic, and x-1 may be bigger than x). You instead should cast the size to an integer before using it. It may make some sense to use unsigned sizes and indexes (paying a LOT of attention to every expression you write) only if you're working on a 16 bit C++ implementation (16 bit was the reason for having unsigned values in sizes).

As a typical mistake that unsigned size may introduce consider:

void drawPolyline(const std::vector<P2d>& points) {     for (int i=0; i<points.size()-1; i++)         drawLine(points[i], points[i+1]); } 

Here the bug is present because if you pass an empty points vector the value points.size()-1 will be a huge positive number, making you looping into a segfault. A working solution could be

for (int i=1; i<points.size(); i++)     drawLine(points[i - 1], points[i]); 

but I personally prefer to always remove unsinged-ness with int(v.size()).

PS: If you really don't want to think by to yourself to the implications and simply want an expert to tell you then consider that a quite a few world recognized C++ experts agree and expressed opinions on that unsigned values are a bad idea except for bit manipulations.

Discovering the ugliness of using iterators in the case of iterating up to second-last is left as an exercise for the reader.