Информатика и технология программирования


Итераторы


Рассмотрим случай, когда структура данных (массив указателей, список, дерево) включают в себя переменные одного типа, но сам тип может меняться в каждом конкретном экземпляре структуры данных (например, массивы указателей на 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);
}
//----- Итератор: поиск первого в списке по условию ------




Начало  Назад  Вперед



Книжный магазин