Iterators

Iterators

An iterator is an object (like a pointer) that points to an element inside the container.

We can use iterators to move through the contents of the container. They can be seen as something similar to a pointer pointing to some location and, using them, we can access content at that particular location.

Iterators are key to using STL effectively.

One kind of iterator is an ordinary C++ pointer.  We were using a C++ pointer iterator in the code:

char s[] = "Example of generic find algorithm";
int len = strlen(s);
const char *foundChar = find(&s[0], &s[len], 'g');
std::cout << "Found character: " << *foundChar << std::endl
	        << "Next character: " << *(foundChar+1) << std::endl;

There are other kinds of iterators, but they are required to behave in a way similar to pointers.

For example, the operator * dereferences the iterator to the value to which it refers.

We were using other kinds of iterator in the code:

std::vector<char> v = make< std::vector<char> >
("Example of generic find algorithm");

std::vector<char>::iterator foundChar 
			= find(v.begin(), v.end(), 'g');
			
std::cout << "Found character: " << *foundChar << std::endl
	        << "Next character: " << *(foundChar+1) << std::endl;

Example using accumulate()

Here’s an example of using an Iterator with the Generic Algorithm accumulate()

accumulate() returns the result of accumulating all the values in the specified range.

//
//  main.cpp
//  STL Iterators
//
//  Created by Bryan Higgs on 10/21/24.
//

#include <iostream>
#include <vector>   // For vector
#include <numeric>  // For accumulate()

int main(int argc, const char * argv[])
{
  int values[] = {2, 3, 5, 7, 11};
  int len = sizeof(values)/sizeof(values[0]);
  
  // Initialize vector using pointer iterator
  std::vector<int> v(&values[0], &values[len]);

  int sum = accumulate(v.begin(), v.end(), 0);

  std::cout << "Result: " << sum << std::endl;

  return 0;
}

Result: 28
Program ended with exit code: 0

Iterator Categories

There are several categories of iterators:

• Input Iterators
• Output Iterators
• Forward Iterators
• Bidirectional Iterators
• Random Access Iterators

These iterator categories form a hierarchy
(Note: this is not an inheritance hierarchy.):

C++ iterator categories define the capabilities of an iterator, influencing the operations you can perform with it.

Here’s a breakdown of the categories and their associated operations:

Iterator Categories (in increasing order of power):

• Output Iterator:
  • Can only be incremented (++).
  • Can be assigned to (*it = value).
  • Used for writing data to a sequence.
• Input Iterator:
  • Can only be incremented (++).
  • Can be dereferenced to read the value (*it).
  • Can be compared for equality (==, !=).
  • Used for reading data from a sequence.
• Forward Iterator:
  • Combines the capabilities of input and output iterators.
  • Can be dereferenced to read and write (*it).
  • Can be compared for equality (==, !=).
  • Can be used in algorithms that require multiple passes over a sequence.
• Bidirectional Iterator:
  • Inherits all the capabilities of a forward iterator.
  • Can also be decremented (--).
  • Used for traversing a sequence in both directions.
• Random Access Iterator:
  • Inherits all the capabilities of a bidirectional iterator.
  • Can be used with arithmetic operators (+, -, +=, -=) to move a fixed number of positions.
  • Can be used with subscript operator ([]) for random access to elements.
  • Can be compared with relational operators (<, >, <=, >=).
  • Used for efficient access to any element in a sequence.

As you can see, Random Access iterators are the most powerful and flexible of all the iterators.

Iterator Bounds

The idiom typically used with pointers is:

int array[] = { ... };
int len = sizeof(array)/sizeof(array[0]);
for ( int *p = &array[0]; p < &array[len]; p++	)
{
	// ...
}

Note, that the p < &array[len] means “one past the end”/

Similarly, with generalized iterators, end() means “one past the end”:

std::vector<int> v;
//...
for (std::vector<int>::iterator i = v.begin(); i < v.end(); i++)
{
	// ...
}

Generalizing accumulate()

The earlier accumulate() function is not as general as it might be.  It assumes that there is a + operator defined on the type T, because of its use in the expression:

init = init + *first;

The version of accumulate() we have already seen is:

accumulate(beg, end, init)

which returns the sum of all the values in the input range { beg : end }.

The summation starts with the initial value specified by init.

There is another version of accumulate() which provides a more generalized form:

accumulate(beg, end, init, BinaryOp)

The first version of accumulate applies the + operator for the element type; the second version applies the specified binary operation.

We can use this second form of accumulate() like this:

//
//  main.cpp
//  STL accumulate
//
//  Created by Bryan Higgs on 10/23/24.
//

#include <iostream>
#include <vector>  // For vector
#include <numeric>  // For accumulate()

// The binary operation for multiply
int mult(int x, int y)
{
  return x * y;
}

int main(int argc, const char * argv[])
{
  int values[] = {2, 3, 5, 7, 11};
  size_t len = sizeof(values)/sizeof(values[0]);
  
  // Initialize vector using pointer iterator
  std::vector<int> v(&values[0], &values[len]);
  
  int product = accumulate(v.begin(), v.end(), 1, mult);
  std::cout << "Result: " << product << std::endl;
  
  return 0;
}

Result: 2310
Program ended with exit code: 0