[Effective-cpp] Item 1: Uses and Abuses of vector

[Klitos Kyriacou]

Hi,

Lois Goldthwaite said:
> On Tuesday 26 October 2004 20:15, Gregory Haley wrote:
> 
> > I would like to add to the summary two bits that have been
> > overlooked up to now.
> >
> > 4. (p. 6) avoid unecessary recalculations.  This is
> > pertinent in a for loop. If the for loop has this structure:
> >
> > for (vector<int>::const_iterator it = vint.begin();
> >      it != vint.end(); ++ it)
> >
> > the value of vint.end() has to be calculated each time 
> > through the loop. On small vectors this would have no
> > appreciable effect, but for very large vectors, and I would
> > guess for vectors of fairly complicated data structures, the
> > overhead of this recalculation could be quite significant.
> > I like the advice to calculate the value of vint.end() once
> > outside the body of the loop, and use that constant value
> > for the terminal point of the loop.
> > [...]
> Certainly there is some cost for repeatedly calculating 
> vint.end(), as compared to saving the value resulting from
> a single call, but the cost shouldn't vary with the number
> of elements or whether the element type is a complicated
> data structure.

I agree about complicated data structures, but the effect of vector size
is that the call to vint.end() would happen more times, simply because
there are more elements to iterate over. But that's neither here nor
there. The important thing is the percentage of time spent calling end()
in each iteration, compared to all the other work that goes into the
loop. Normally, it is negligible. The compiler may even spot that the
value returned by vint.end() will not change, and internally optimize by
caching the value so that end() is only ever called once (and the 'call'
may be inline). But, supposing there's no optimization, then in a loop
with a trivial body like...

for (vector<int>::const_iterator it = vint.begin(); it != vint.end();
++it)
{
   ++(*it);
}

...then I guess the call to vint.end() may just be significant. But I
don't really like the usual solutions:

Solution 1, const iterator outside the loop:
const vector<int>::const_iterator end = vint.begin();
for (vector<int>::const_iterator it = vint.begin(); it != end; ++it)

Solution 2, non-const iterator inside the loop:
for (vector<int>::const_iterator it = vint.begin(), end = vint.end(); it
!= end; ++it)

I don't like solution 1 because the iterator 'end' has too large a
scope. I only want it to be accessible up to the end of the loop, not to
the end of the enclosing block. I don't like solution 2 because the
iterator is not const. The compiler would let me accidentally change its
value inside the loop. Other languages (I think Fortran is one of them)
solve this problem by having the language specification say that the
compiler calculates the step and end values just once at the start of
the loop and uses a saved copy of the values in each iteration.
Programmers need to be aware that these loop-control parameters never
change even if the variables used do change. But that's not a problem as
it's just part of the language. Not sure what C-family programmers would
think of this idea.

Klitos
[ *** LongSig auto truncated *** ]