Iterators

One operation that "collection" ADTs such as lists, sets, etc. have to support is iteration - walking through each element of the the collection. Lets extend the int_stack ADT with a mechanism for implementing iteration.

One way is to simply perform the iteration. Thus


	for( i = len_int_stack(stack)-1; i >= 0; i-- ) {
	   int el = val_int_stack(stack, i);
	   /* do stuff */
	}

This is unacceptable. It completely exposes the details of the implementation. If, for instance, we were to change the implementation of int_stack from a resized array to a linked list, we would have to modify code spread out across the entire program.

Another approach is to use a second iterator type. Iterator types support an API that includes init_, is_more_, next_ and get_ functions. Thus, assume we defined a type called int_stack_iter. Using that, we could write an iterator loop as:


	for( init_int_stack_iter(I);
		is_more_int_stack_iter(I);
		next_int_stack_iter(I) ) {
	  int el = get_int_stack_iter(I);
	  /* do stuff with el */
	}

In general, I find this approach too convoluted. Also, for more complicated data-structures, the performance overhead of using a separate iterator data structure can become large.

Instead, I prefer to use macros. I define FOR_INT_STACK() and END_INT_STACK() macros that I use as:


	FOR_INT_STACK(stack, el)
	  /* do stuff with el */
	END_INT_STACK

The definition of the macro, in the case of int_stack at least, is straight-forward.


	#define FOR_INT_STACK(_stack, _val) \
	  { \
	    struct cell_int_stack * _st = _stack; \
	    int	_i; \
	    for( _i = len_int_stack(_st)-1; _i >= 0; _i-- ) { \
	      int	_val = val_int_stack(_st, _i);

	#define END_INT_STACK \
	    } \
	  }

Now, if we were to change the implementation of int_stack so that it used a linked list, we would need only to change the definition of the macro.


	#define FOR_INT_STACK(_stack, _val) \
	  { \
	    struct cell_int_stack * _st = _stack; \
	    struct cell_int_stack * _p; \
	    struct cell_int_stack * _q; \
	    for( _p = list_int_stack(_st); _p; _p = _q) { \
	      _q = next_cell_int_stack(_st); \
	      { \
	        int _val = val_cell_int_stack(_st);

	#define END_INT_STACK \
	      } \
	    } \
	  }

Some rules I follow when writing iterators:

Actually this is not really the implementation that I would recommend. What I would do is in the public header add the declaration of FOR_INT_STACK as:


	/* int_stack.h */
	#define FOR_INT_STACK(_stack, _i)	X_FOR_INT_STACK(_stack, _i)
	#define END_INT_STACK			X_END_INT_STACK

I would then define X_FOR_INT_STACK as above in the private header. This keeps the implementation details out of the public header, and puts them in the private header, which is where they belong.


Next Prev Main Top Feedback