Recently, Professor Zhou Ligong has published his painstaking work "Programming and Data Structure" for several years. The electronic version has been distributed to electronic engineers and college groups for free download. Authorized by Professor Zhou Ligong, the content of this book is serialized.

> > >> 1.1 Iterator mode

> > > 1.1.1 Iterators and Containers

When initializing an element in an array, it usually traverses the array using a for loop statement like this :

Int i, a[10];

For(i = 0; i < 10; i++)

a[i] = i;

The code loop variable i, the variable initial value 0, and then incremented to 1, 2, 3, ..., i is incremented after each program will assign the value a [i]. Many elements are stored in the array, and any one of them can be selected by specifying an array subscript. The role of i++ in the for statement is to increment the value of i by one after each iteration, so that you can access the next element in the array, thus implementing the function of traversing array elements one by one.

It can be seen that the commonly used loop structure is an iterative operation. In each iteration operation, the modification of the iterator is equivalent to modifying the flag or counter of the loop control. A container is a data structure that holds a collection of values. C has two built-in containers: arrays and structures. Although C does not provide more containers, users can write their own containers as needed, such as linked lists, hash tables, and so on.

I in the abstract, the pattern formed after the universal in design mode called iterator i (the Iterator) mode, the Iterate repeated literally means, repeatedly stated, in fact, do something repeated, the Iterator pattern for Traverse the elements in the array. The basic idea of ​​an iterator is that the iterator variable stores the location of an element of the container, so it can traverse the elements at that position. Through the methods provided by the iterator, you can continue to traverse the next element of the container.

Obviously, an iterator is an abstract design concept because there is no physical object in the programming language that directly corresponds to the concept. The Design Patterns book provides a complete description of 23 design patterns, where the iterator pattern is defined to provide a way to sequentially access individual elements of a container object while traversing a container object without exposing the object. Internal representation. The central idea is to separate the data containers and algorithms from each other and finally bind them together with a binder.

> > > 1.1.2 Iterator Interface

Why must we consider introducing the complex design pattern of Iterator? If it is an array, can it be done directly using the for loop statement for traversal processing? Why introduce the role of Iterator outside the collection? An important reason is that traversal can be separated from implementation after the introduction of Iterator.

In fact, whether it is a singly linked list or a doubly linked list, the search algorithm and the traversal algorithm are not much different, basically repeating labor. If there are bugs in the code, you need to modify all relevant code. Why is there such a situation? Mainly due to the unreasonable interface design, the biggest problem is to put the container and the algorithm together, and the implementation of the algorithm depends on the implementation of the container. Therefore, a matching algorithm must be developed for each container.

Suppose you want to implement 6 algorithms (swap, sort, maximize, minimize, traverse, find) in 2 kinds of containers (dual-linked list, dynamic array). Obviously, you need 2×6=12 interface functions to achieve the target. . As the number of algorithms increases, it is bound to cause the number of functions to increase exponentially, and the workload of repeated labor is also greater. If you design the container and algorithm separately, you only need to implement 6 algorithm functions. That is, the algorithm does not depend on the specific implementation of the container, and the algorithm does not operate directly in the container. For example, the sorting algorithm does not need to care if the elements are stored in an array or a linear table.

Before the formal introduction of iterators, it is worthwhile to analyze the bubble sorting algorithm as shown in Listing 3.49 .

Listing 3.49    Bubble sorting algorithm

1 #include

2 #include "swap.h"

3

4 void bubbleSort(int *begin, int *end)

5 {

6 int flag = 1; // flag = 1 , indicating that the contents of the pointer are not exchanged

7 int *p1 = begin; // p1 points to the first element of the array

8 int *p2 = end; // p2 points to the tail element of the array

9 int *pNext; // pNext points to the next element of the element pointed to by 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 size of the value pointed to by the pointer

17 {

18 swap(p1, pNext); // exchange the contents of 2 pointers

19 flag = 0; // flag = 0 , indicating the content exchange of 2 pointers

20 }

21 p1++; // p1 pointer back

twenty two }

23 if (flag) return; / / no exchange, indicating that it is already ordered, then return directly

24 p2--; // p2 pointer forward

25 }

26 }

27

28 int main(int argc, char *argv[])

29 {

30 int a[]={5, 3, 2, 4, 1};

31 int i = 0;

32 33 bubbleSort(a, a+4);

34 for(i = 0; i < sizeof(a) / sizeof(a[0]); i++){

35 printf("%d", a[i]);

36 }

37 return 0;

38 }

If no exchange is performed for any one traversal, then the records are ordered and the ordering is terminated. Where p1 points to the first element of the array, pNext points to the next element of the element pointed to by p1, and p2 points to the tail element of the array ( Figure 3.21 (a)). If *p1>*pNext, the content pointed to by the pointer is exchanged, p1 and pNext are moved backward ( Fig. 3.21 (b)), otherwise the content pointed by the pointer is unchanged, p1 and pNext are moved backwards, after one round of sorting, until Until p1 = p2, the largest element moves to the end of the array.

Figure 3.21 Schematic diagram of the internal loop execution process

When the largest element is moved to the end of the array, the inner loop is exited. After p2 advances, the program jumps to the program list 3.49(15), p1 points to the first element of the array again, and pNext points to the next element of the element pointed to by p1 (Fig. 3.22(a)). At this time, the difference between Figure 3.22(a) and Figure 3.21(a) is that p2 points to a[3]. After a round of looping, until p1 = p2, the integer 4 is moved to the position where a[3] is located, and the remaining sorting is shown in Figure 3.22. When p1 and p2 coincide at the position of the first element of the array, it indicates the end of sorting (Fig. 3.22(d)).

Figure 3.22 Schematic diagram of the external loop execution process

It can be seen that the core of the bubble sorting algorithm is the operation of the pointer. The main behaviors are as follows:

● Compare the size of the value pointed to by the pointer;

● exchange the contents pointed to by the pointer;

● The pointer moves backwards, that is, the pointer points to the next element;

● The pointer moves forward, that is, the pointer points to the previous element.

Since the bubble type is used as an example of int type data, the user knows how to compare the data and how to exchange the pointer to the content, as well as the forward and backward movement of the pointer. When using void * that supports any type of data, although the algorithm program does not know what type of data is passed in, the caller knows, so when the sorting algorithm function is called, the parameter can be passed by the user through the callback function. The modified bubble sort function prototype is as follows:

Void iter_sort (void *begin, void *end, compare_t compare, swap_t swap);

Where compare is used to compare the size of the value pointed to by the two pointers , the compare_t type is defined as follows :

Typedef int (*compare_t) (void *p1, void *p2);

The swap function is used to exchange the contents pointed to by two pointers. The swap_t type is defined as follows:

Typedef void (*swap_t) (void *p1, void *p2);

Obviously it is not possible to move the pointer through ++ or -- because I don't know what type of data is being passed in. If you know that the data occupies 4 bytes, you can move the pointer by adding 4 or minus 4 to the value of the pointer. Although pointer movement can be achieved in this way, data is always required to be stored as an array. Once you leave this particular container, you cannot determine the behavior of the pointer. If the algorithm is used in conjunction with a linked list , it is clear that p1++ and p2-- in the code are not suitable for linked lists .

Based on this, "it's possible to abstract the pointer so that it has different implementations for different containers, and the algorithm only cares about its pointer interface." Obviously, the container needs to provide the corresponding interface function to implement the pointer forward and backward movement. Usually such a pointer is called an "iterator". In a sense, the iterator as an interface to the algorithm is a generalized pointer, and the pointer satisfies the requirements of all iterators. The advantage is that for any kind of container, the elements in the container can be traversed in the same way without exposing the internal details of the container. 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 represented interface, implemented by a particular container, such as linked lists, arrays, etc.)

6 typedef struct _iterator_if{

7 iterator_next_t pfn_next; / / iterator post shift function , equivalent to p1 + +

8 iterator_prev_t pfn_prev; / / iterator forward function , equivalent to p2--

9 }iterator_if_t;

Among them, the content pointed to by p_iter is determined by the container, which can point to the node or to the data. Whether it is a linked list or a pfn_next function implemented by other containers, the meaning is the same, and other functions are the same. If the iterator is understood to be a pointer variable to the data, the pfn_ next function causes the iterator to point to the next data in the container, and the pfn_prev function causes the iterator to point to the previous data in the container .

At this point, you should write some methods for getting or setting values ​​for the interface. The method used to read a variable is often called a "getter," and the method used to write a variable is often called a "setter." Let's take a doubly linked list as an example. Use the structure pointer as the return value of dlist_iterator_if_get(). See Listing 3.51 for details .

Listing 3.51    Get the iterator interface of the doubly linked list (1)

1 static void __dlist_iterator_next(iterator_t *p_iter) // Let the iterator point to the next data in the container

2 {

3 *p_iter = ((dlist_node_t *)*p_iter) -> p_next;

4 }

5

6 static void __dlist_iterator_prev(iterator_t *p_iter) // Let the iterator point to the previous data of the container

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; / / return structure variable address & iterator_if

17 }

The form of its call is as follows:

Iterator_if_t *p_if = dlist_iterator_if_get(); // Get the iterator interface of the linked list, ie p_if = &iterator_if

Note that if static is omitted, iterator_if becomes a local variable. Since it will fail after the function has finished executing, it is meaningless to return its address. Here we use the direct access to the structure member to assign the value of the iterator_if_t type structure. Obviously, this method should be avoided as much as possible between different modules. Instead, the corresponding interface is provided. See Listing 3.52 for details .

Listing 3.52 to 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 form of its call is as follows:

Iterator_if_t iterator_if;

Dlist_iterator_if_get(&iterator_if);

Since there are only two function pointers in the structure of the iterator_if_t type, access to the function pointer contains only settings and calls, 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 iterator back to the function pointer, equivalent to p1 + +

9 iterator_prev_t pfn_prev; / / call the iterator forward function pointer, 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 backward function, equivalent to ++

14 void iterator_prev(iterator_if_t *p_if, iterator_t *p_iter); // iterator forward 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 call iterator_if_init() directly to implement dlist_iterator_if_get(), as shown in Listing 3.55 .

Listing 3.55 to 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 }