THE MAGAZINE FOR COMPUTER APPLICATIONS
Circuit Cellar Online offers articles illustrating creative solutions
and unique applications through complete projects, practical
tutorials, and useful design techniques.

WHAT'S YOUR ENGINEERING QUOTIENT?

Problem 2—What is the best way to traverse elements linearly in an array?

element_type a[num_of_elements];
for (unsigned index = 0; index 
 < num_of_elements; ++index) {
access a[index]
}

Any good programmer would point out the inefficiency of indexing: it involves multiplication. However, indexing only requires multiplication if the size of the array element is not a power of two times the basic word size of the processor. In most cases, indexing is efficient, and many processors support indexing in hardware. But indexing can be an expensive operation for 8-bit processors with no multiply instructions. Most optimizing computers can offer to optimize the previous code to the following.

for (element_type *ptr = a, unsigned index = 0; 
 index < num_of_elements; ++index, ++ptr) {
access *ptr
}

Incrementing a pointer by a constant is much quicker compared to a multiplication. However, in C++, using the vector template, a programmer can use the following code:

vector a(num_of_elements);
for (vector::iterator i = a.begin(); 
 i != a.end(); ++i) {
access *i
}

At first glance, this code is no better than the C code. However, there are advantages offered by the vector template class. First of all, note that the limit is no longer "num_of_elements". This is because a vector keeps track of its own limit (as a.end()). Secondly, the iterator is implemented efficiently as a pointer. Perhaps the most important advantage of using an iterator is the commonality of iterators of all container template classes. Simply based on the commonality of an iterator type, the C++ STL (standard template library) provides algorithms to perform sorting, searching and other tasks regardless of the container type.

4-00