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

[Lois Goldthwaite]

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. (though, physician 'heal thyself' would be appropriate here, since I
> always turn to the less efficient manner in my own code -- since my fingers
> almost automatically key the code in :) .

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.

Vectors hold a contiguous range of data elements, so the calculation takes 
constant time:

 end_it = begin_it + ( size_of_one_element * number_of_elements_in_vector)


You may be thinking about lists, where size() is allowed to take linear time 
as the list grows. But even lists (and all the rest of the standard 
containers) have constant complexity for the end() function.

Lois