Iterators in C

Consider this article a companion piece to my article on containers: https://dev.to/noah11012/containers-in-c-34pi

What is the impetus for using iterators in C? We only have to look toward to C++ for the answer. Using an algorithm like std::find() does not operate on the container itself. Instead, using a layer of abstraction called iterators. This allows the standard algorithms to operate on any standard container indirectly through the iterators it provides. To access these container provided iterators, we use the methods begin() and end() or cbegin() and cend() for the const versions.

begin() points to the very first element in the container while end() points to one past the last element. Almost acting like the null terminator in a C String.

The algorithms provided by the standard can operate on custom types so as long it implements an iterator that has the common methods of a typical iterator. There are also different types of iterators: Input and Output are two of them. Input is used for reading an element then incrementing to the next element. Output is similar except it writes values to a container.

Let's say for this discussion we will be working with vectors or arrays that can resize themselves when necessary. We also have a binary search algorithm, find() that takes a beginning iterator and an end and a value to search for. To not complicate things we will only add the ability to search for integers.

We will have the following struct:

typedef struct
{
    int *values;
    int  curr_index;
} Iterator;

And some functions:

void iter_new(Iterator *iter);
void iter_advance(Iterator *iter);
void iter_jump(Iterator *iter, int pos);
void iter_read(Iterator *iter, int *out_value);
void iter_write(Iterator *iter, int value);

We will not worry about the implementation details of these functions to not clutter the discussion of the importance of iterators.

This type of iterator we have made is called a random access iterator. What this means is we can jump anywhere we want in the container's elements instead of sequentially reading each element in progression.

This is helpful since binary algorithms jump to the middle of the array to see if the element is there.