Recently, Professor Zhou Ligong has published his painstaking work "Programming and Data Structure" after years of effort. The electronic version is now freely available for download by electronic engineers and college groups. With Professor Zhou's authorization, the content of this book is being serialized.
> > > 1.1 Iterator Pattern
> > > 1.1.1 Iterators and Containers
When initializing an element in an array, it is common to traverse the array using 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 1 each time, allowing access to each element of the array through a[i]. This is a typical iterative process where the loop counter is updated in each iteration to move to the next element. In this way, the array elements are traversed one by one.
This kind of loop structure represents an iterative operation. In each iteration, the modification of the loop counter is equivalent to updating the flag or index that controls the loop. A container is a data structure that holds a collection of values. C provides two built-in containers: arrays and structures. Although C does not offer more complex containers, users can define their own, such as linked lists and hash tables.
In abstract terms, the pattern formed after applying the iterator concept in design patterns is called the Iterator pattern. The word "iterate" literally means to repeat something, and in practice, it refers to repeatedly performing an action. The iterator pattern allows traversal of the elements in a container without exposing its internal representation. The core idea is to separate the data containers from the algorithms and bind them together using an interface.
It is important to understand that an iterator is an abstract concept rather than a concrete object in programming languages. According to the Design Patterns book, the iterator pattern provides a way to sequentially access elements of a container without revealing its internal details. This separation helps maintain flexibility and reusability in software design.
> > > 1.1.2 Iterator Interface
Why should we consider introducing the complex design pattern of an iterator? Can't we just use a for loop to traverse an array directly? Why introduce an external iterator outside the collection? One key reason is that the iterator enables the separation of traversal logic from implementation.
Whether it’s a singly linked list or a doubly linked list, the search and traversal algorithms are quite similar, often leading to redundant code. If there are bugs, fixing them requires modifying all relevant parts. This issue arises due to poor interface design, where the container and algorithm are tightly coupled. As a result, a specific algorithm must be developed for each type of container.
Imagine you want to implement six algorithms—swap, sort, maximize, minimize, traverse, and find—in two types of containers: a doubly linked list and a dynamic array. You would need 2×6=12 interface functions to achieve this. As the number of algorithms increases, the number of functions grows exponentially, making maintenance more challenging. By separating the container and the algorithm, you only need to implement six algorithm functions, reducing redundancy and improving modularity.
Before formally introducing iterators, let’s analyze the bubble sorting algorithm shown in Listing 3.49.
Listing 3.49 Bubble Sorting Algorithm
1 #include <stdio.h>
2 #include "swap.h"
3
4 void bubbleSort(int *begin, int *end)
5 {
6 int flag = 1; // flag = 1 indicates no swap
7 int *p1 = begin; // p1 points to the first element
8 int *p2 = end; // p2 points to the last element
9 int *pNext; // pNext points to the next element of p1
10
11 while(p2 != begin){
12 p1 = begin;
13 flag = 1;
14 while(p1 != p2){
15 pNext = p1+1;
16 if(*p1 > *pNext) //Compare the values pointed to by the pointers
17 {
18 swap(p1, pNext); //Swap the contents of the two pointers
19 flag = 0; // flag = 0 indicates a swap occurred
20 }
21 p1++; // Move p1 forward
22 }
23 if (flag) return; // No swaps, already sorted
24 p2--; // Move p2 backward
25 }
26 }
27
28 int main(int argc, char *argv[])
29 {
30 int a[]={5, 3, 2, 4, 1};
31 int i = 0;
32 bubbleSort(a, a+4);
33 for(i = 0; i < sizeof(a) / sizeof(a[0]); i++){
34 printf("%d", a[i]);
35 }
36 return 0;
37 }
If no swaps occur during a pass, the array is already sorted, and the sorting ends. Here, p1 points to the first element, pNext to the next, and p2 to the last. If *p1 > *pNext, the contents are swapped, and both pointers move forward. Otherwise, they move forward without swapping. After one pass, the largest element moves to the end of the array.
As shown in Figure 3.21, the core of the bubble sort algorithm lies in pointer operations. These include comparing values, swapping, and moving the pointers forward or backward. When dealing with void* to support any data type, the algorithm doesn’t know the actual data type, but the caller does. Therefore, the comparison and swap functions are passed as callbacks.
The modified bubble sort function prototype is as follows:
Void iter_sort (void *begin, void *end, compare_t compare, swap_t swap);
Here, 'compare' is used to compare the values pointed to by two pointers, and 'swap' exchanges the contents. The function prototypes are defined as:
typedef int (*compare_t) (void *p1, void *p2);
typedef void (*swap_t) (void *p1, void *p2);
However, moving the pointer using ++ or -- is not possible when the data type is unknown. Instead, the pointer can be adjusted by adding or subtracting the size of the data type. But this approach only works for arrays. For other containers like linked lists, the same logic doesn't apply.
To address this, the pointer can be abstracted into an iterator that provides different implementations for various containers. The algorithm only needs to interact with the iterator interface. This makes the traversal mechanism consistent across all container types, hiding their internal details.
The declaration of the iterator interface is detailed in Listing 3.50.
Listing 3.50 Declaration of the Iterator Interface
1 typedef void *iterator_t; //Define the iterator type
2 typedef void (*iterator_next_t)(iterator_t *p_iter);
3 typedef void (*iterator_prev_t)(iterator_t *p_iter);
4
5 //Iterator interface (IF), implemented by specific containers like linked lists or arrays
6 typedef struct _iterator_if{
7 iterator_next_t pfn_next; //Iterator next function, equivalent to p1++
8 iterator_prev_t pfn_prev; //Iterator previous function, equivalent to p2--
9 }iterator_if_t;
The content pointed to by p_iter depends on the container. Whether it's a linked list or another container, the meaning of pfn_next remains the same. The pfn_prev function adjusts the iterator to point to the previous element.
At this point, we also need methods to get or set values via the interface. These are typically called getters and setters. For example, in a doubly linked list, the dlist_iterator_if_get() function returns a structure pointer. See Listing 3.51 for details.
Listing 3.51 Get the Iterator Interface of a Doubly Linked List (1)
1 static void __dlist_iterator_next(iterator_t *p_iter) //Move the iterator to the next element
2 {
3 *p_iter = ((dlist_node_t *)*p_iter)->p_next;
4 }
5
6 static void __dlist_iterator_prev(iterator_t *p_iter) //Move the iterator to the previous element
7 {
8 *p_iter = ((dlist_node_t *)*p_iter)->p_prev;
9 }
10
11 iterator_if_t *dlist_iterator_if_get (void)
12 {
13 static iterator_if_t iterator_if;
14 iterator_if.pfn_next = __dlist_iterator_next;
15 iterator_if.pfn_prev = __dlist_iterator_prev;
16 return &iterator_if;
17 }
The call form is as follows:
iterator_if_t *p_if = dlist_iterator_if_get(); //Get the iterator interface of the linked list
It's important to note that if 'static' is omitted, 'iterator_if' becomes a local variable, which will go out of scope after the function exits, making it invalid to return its address. Here, we assign the structure members directly to avoid cross-module issues. See Listing 3.52 for details.
Listing 3.52 Obtain a Doubly Linked List Iterator Interface (2)
1 void dlist_iterator_if_get(iterator_if_t *p_if)
2 {
3 p_if->pfn_next = __dlist_iterator_next;
4 p_if->pfn_prev = __dlist_iterator_prev;
5 }
The call form is as follows:
iterator_if_t iterator_if;
dlist_iterator_if_get(&iterator_if);
Since the iterator_if_t structure contains only two function pointers, accessing them involves setting and calling, as shown in Listing 3.53.
Listing 3.53 Iterator Interface (iterator.h)
1 #pragma once;
2
3 typedef void *iterator_t;
4 typedef void(*iterator_next_t)(iterator_t *p_iter);
5 typedef void(*iterator_prev_t)(iterator_t *p_iter);
6
7 typedef struct _iterator_if{
8 iterator_next_t pfn_next; //Call the next function, equivalent to p1++
9 iterator_prev_t pfn_prev; //Call the previous function, equivalent to p2--
10 }iterator_if_t;
11
12 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev);
13 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter); //Iterator next function, equivalent to ++
14 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter); //Iterator previous function, equivalent to --
The specific implementation of these functions is detailed in Listing 3.54.
Listing 3.54 Implementation of Iterator Interface
1 #include "iterator.h"
2
3 void iterator_if_init(iterator_if_t *p_if, iterator_next_t pfn_next, iterator_prev_t pfn_prev)
4 {
5 p_if->pfn_next = pfn_next;
6 p_if->pfn_prev = pfn_prev;
7 }
8
9 void iterator_next(iterator_if_t *p_if, iterator_t *p_iter)
10 {
11 p_if->pfn_next(p_iter);
12 }
13
14 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter)
15 {
16 p_if->pfn_prev(p_iter);
17 }
Now, you can directly call iterator_if_init() to implement dlist_iterator_if_get(), as shown in Listing 3.55.
Listing 3.55 Obtain a Doubly Linked List Iterator Interface (3)
1 void dlist_iterator_if_get(iterator_if_t *p_if)
2 {
3 iterator_if_init(p_if, __dlist_iterator_next, __dlist_iterator_prev);
4 }
Smart Terminals,Smart Pos Terminal,Smart Pos Machine,Smartpay Terminal
Guangzhou Winson Information Technology Co., Ltd. , https://www.barcodescanner-2d.com