Итераторы

Рассмотрим случай, когда структура данных (массив указателей, список, дерево) включают в себя переменные одного типа, но сам тип может меняться в каждом конкретном экземпляре структуры данных (например, массивы указателей на int, double, strust man ). Очевидно, что алгоритмы поиска, сортировки, включения, исключения и т.д. будут совпадать с точностью до операции над этими переменными. Например, для сортировки массивов указателей на целые переменные и строки могут использоваться идентичные алгоритмы, различающиеся только операцией сравнения двух переменных соответствующих типов (операция "&#62" и функция strcmp ). Если эту операцию реализовать отдельной функцией, а указатель на нее передавать в качестве параметра, то мы получим универсальную функцию сортировки массивов указателей на переменные любого типа данных, то есть итератор.

формальный параметр-указатель

Типичными итераторами являются:

-итератор обхода (foreach), выполняющий для каждой переменной в структуре данных указанную функцию;

-итератор поиска (firstthat), выполняющий для каждой переменной в структуре данных функцию проверки и возвращающий указатель на первую переменную, которая удовлетворяет условию, проверяемому в функции;

-итераторы сортировки, двоичного поиска, включения и исключения элементов в упорядоченную структуру данных.

Ниже приводятся примеры итераторов для массива указателей и списка. Чтобы список мог содержать переменные произвольного типа, они представлены отдельными переменными, указатели на которые типа void* занесены в элементы списка.

//------------------------------------------------------bk56-02.cpp

//----- Элемент списка ------------------------------------

struct list
{
list *next; // Указатель на следующий

void *pdata; // Указатель на данные

} *PH; // Пример заголовка списка

//----- Итератор: для каждого элемента списка ------------

void ForEach(list *pv, void (*pf)(void*) )
{
for (; pv !=NULL; pv = pv-&#62next)
(*pf)(pv-&#62pdata);
}
//----- Итератор: поиск первого в списке по условию ------

void *FirstThat(list *pv, int (*pf)(void*))
{
for (; pv !=NULL; pv = pv-&#62next)
if ((*pf)(pv-&#62pdata)) return pv -&#62pdata;
return NULL;
}
//----- Примеры использования итератора ------------------

//----- Функция вывода целой переменной

void print(void *p)
{ cout &#60&#60 *(int*)p; }
//----- Функция проверки целой переменной на значение &#62 0

int positiv(void *p)
{ return *(int*)p &#62 0; }

//----- Вызов итераторов для списка, содержащего указатели

// на целые переменные

void main()
{ int *pp;
ForEach(PH,print);
if ((pp = (int*)FirstThat(PH,positiv)) !=NULL)
cout &#60&#60 *pp;
}
//----- Итератор сортировки для массива указателей

void Sort(void **pp, int (*pf)(void*,void*))
{
int i,k; // сортировка по алгоритму "пузырька"

do
for (k=0,i=1; pp[i] !=NULL; i++)
if ( (*pf)(pp[i-1],pp[i]) ==0) // вызов функции сравнения

{
void *q;
k++; q = pp[i-1]; pp[i-1] = pp[i]; pp[i] = q;
}
while(k);
}
// Пример вызова итератора сортировки для массива

// указателей на целые переменные

// Функция сравнения дает "тройной" результат

// 0 - равны;

// -1 - первый меньше второго;

// 1 - первый больше второго.

int compare _int(void *p1, void *p2)
{
if (* (int*)p1 == * (int*)p2) return 0;
if (* (int*)p1 &#60 * (int*)p2) return -1;
return 1;
}
void main()
{ int a1=5, a2=6, a3=3, a4=2;
int *PP[] = {&#38a1, &#38a2, &#38a3, &#38a4, NULL};
Sort(PP,compare);
}

Из приведенных примеров просматривается общая схема итератора:

-структура данных, обрабатываемая итератором, содержит в своих элементах указатели на переменные произвольного (неизвестного для итератора) типа void* ;

-итератор получает в качестве параметров указатель на структуру данных и указатель на функцию обработки входящих в структуру данных переменных;

-итератор выполняет алгоритм обработки структуры данных в соответствии со своим назначением: foreach - обходит все переменные, firstthat - обходит и проверяет все переменные, итератор сортировки -сортирует переменные (или соответствующие элементы структуры данных, например, списка);

-в процессе работы с каждой переменной итераторы foreach и firstthat вызывают функцию, переданную по указателю с параметром -указателем на переменную, которую нужно обработать или проверить. Итераторы сортировки, ускоренного поиска и тому подобное вызывают функцию по указателю с целью сравнения двух переменных, указатели на которые берутся из структуры данных и становятся параметрами функции сравнения.

Содержание раздела