Professor Zhou Ligong talks about iterator pattern design

Professor Zhou Ligong has recently published his long-awaited work, "Programming and Data Structure," after years of effort. The electronic version is now freely available for download by electronic engineers and college students. With Professor Zhou's authorization, the content of this book is being serialized here.

1.1 Iterator Pattern

1.1.1 Iterators and Containers

When initializing an element in an array, it is common to use a for loop like this:

int i, a[10];
for (i = 0; i < 10; i++)
a[i] = i;

The loop variable i starts at 0 and increments by one each iteration, allowing access to each element in the array sequentially. This process enables the traversal of all elements in the array. In essence, the loop structure represents an iterative operation where the increment of the iterator—like i++—allows access to the next element in the sequence.

A container is a data structure that holds a collection of values. In C, the built-in containers are arrays and structures. Although C does not provide more complex containers, users can implement their own, such as linked lists or hash tables.

In design patterns, the iterator pattern abstracts the concept of traversal. An iterator is a mechanism that allows you to access elements of a container without exposing its internal representation. It stores the current position within the container and provides methods to move to the next or previous element. This abstraction makes it possible to traverse different types of containers using a consistent interface.

The iterator pattern separates the algorithm from the container implementation, making code more modular and reusable. This separation is particularly useful when dealing with multiple data structures, as it avoids the need to rewrite algorithms for each specific container type.

1.1.2 Iterator Interface

Why introduce the iterator design pattern? Why not simply use a for loop for array traversal? One key reason is that the iterator allows the separation of traversal logic from the container implementation. This separation makes the code cleaner and more maintainable.

For example, whether it’s a singly linked list or a doubly linked list, the search and traversal algorithms are similar. If there’s a bug in the code, it must be fixed in every relevant place. This repetition leads to inefficiency and potential errors. By separating the container and the algorithm, we reduce redundancy and improve code quality.

Suppose you want to implement six algorithms (swap, sort, maximize, minimize, traverse, find) on two container types (doubly linked list, dynamic array). Without iterators, you would need 12 separate functions. With iterators, you only need to implement six algorithm functions, which can then be used across any container type.

To illustrate, let’s look at the bubble sort algorithm in Listing 3.49. This algorithm uses pointers to traverse and compare elements, swapping them if necessary. The core operations include comparing values, exchanging data, and moving the pointer forward or backward.

When working with void pointers to support multiple data types, the algorithm must rely on callback functions for comparison and swapping. This approach ensures flexibility while maintaining type safety.

Based on these observations, it becomes clear that the iterator pattern abstracts the pointer movement, allowing the same algorithm to be used across different container implementations. This abstraction makes the code more general and reusable.

The iterator interface is defined in Listing 3.50. It includes function pointers for moving the iterator forward and backward. These functions are implemented differently depending on the container type, such as arrays or linked lists.

For instance, in a doubly linked list, the iterator_next function moves the iterator to the next node, while iterator_prev moves it to the previous node. These functions are encapsulated within the iterator interface, allowing the algorithm to interact with the container through a unified API.

By using the iterator interface, developers can write generic algorithms that work with various container types without needing to know their internal details. This design promotes modularity, reusability, and maintainability in software development.