4.2.2 Forward Iterators

Forward iterators have to satisfy the following requirements:

Forward Iterator Requirements:

• constructor
• assignment operator
• equality/inequality operator
• dereference operator
• pre/post increment operator

The difference to the input and output iterators is that for two forward iterators r and s, r==s implies ++r==++s. A difference to the output iterators is that operator* is also valid on the left side of the assignment operator (t = *a is valid) and that the number of assignments to a forward iterator is not restricted.

So, multi-pass one-directional algorithms can be implemented on containers that allow the use of forward iterators (look at Table 5). As an example for a single-pass one-directional algorithm find_linear is presented. It iterates through the elements of a container and returns the iterator position where a value provided to find_linear is found, otherwise the past-the-end iterator is returned. The overhead of find_linear is statistically n/2.

template<class ForwardIterator, class T>
ForwardIterator find_linear (ForwardIterator first,
                             ForwardIterator last, T&value) { 

   while (first != last) if (*first++ == value) return first;
   return last;
}

vector<int> v (3, 1);
v.push_back (7);	// vector v: 1 1 1 7

vector<int>::iterator i = find_linear (v.begin(), v.end(), 7);
if (i != v.end() ) cout << *i; else cout << "not found";

Output: 7

Continue with section 4.2.3

Back to index