Нередко данные представляют последовательные структуры, например, связанные списки, хеш-таблицы, деревья, очереди, стеки и т.д. При переборе объектов подобных структур может быть нежелательным предоставление прямого доступа к данным внешнему кода, например, если мы хотим скрыть извне какие-то критичные данные. Кроме того, структура данных может в будущем может измениться, что потребует изменить внешний код, который использует изменившуюся структуру данных. И для решения этих проблем для перебора данных определяют специальную абстракцию - итераторы.
Внешний код создает объект итератора, который указывает на определенный элемент в наборе данных (обычно на первый элемент, но необязательно). Функция итератора принимает объект итератора извлекает элемент, на который указывает итератор, и перемещает итератор на следующий элемент в наборе. Таким образом, при последовательном многократном вызове функции итератора мы можем перебрать все объекты в наборе.
В общем случае итератор требует наличие как минимум трех функций
// создание итератора ITERATOR* createIterator(); // Получаем текущий элемент итератора и сдвигаем итератор на следующий элемент // Если элементов в наборе больше нет, то возвращается NULL void* getNext(ITERATOR* iterator); // Удаляем итератор void destroyIterator(ITERATOR* iterator);
Внешний код создает итератор, вызывает функцию итератора для последовательного получения элементов и после окончания работы удаляет итератор:
void* element;
ITERATOR* it = createIterator(); // создаем итератор
while(element = getNext(it)) // в цикле получаем текущий элемент итератора
{
// некоторые действия с итератором
}
destroyIterator(it); // удаляем итератор
В данном случае мы опять же можем не возвращать весь элемент из набора данных, а лишь те его компоненты, к которым внешний код может иметь доступ. И даже если в будущем структура данных изменится, например, со связного списка на массив или наоборот, то итератор скроет все эти изменения от внешнего кода. Мы лишь изменяем код итератора для получения элемента набора. Внешний же код, который использует итератор, остается прежним.
Подобный паттерн используется в частности при работе с файлами. Так, встроенная библиотечная функция getline()
проходит по всем строкам в файле и сдвигает позицию итератора в указателе FILE.
Рассмотрим следующую задачу. Сначала определим в файле account.h следующий API:
// создание итератора struct ITERATOR* createIterator(void); // Получаем данные char* getUserName(struct ITERATOR*); // Удаляем итератор void destroyIterator(struct ITERATOR*); // создание списка void createAccountList(void); // удаление списка void deleteAccountList(void);
Функция createIterator создает итератор, который будет представлять структуру ITERATOR, и возвращает указатель на него. Функция destroyIterator удаляет итератор и освобождает его память. Для получения данных из итератора API предоставляет функцию getUserName, которая будет возвращать строку. Чтобы иметь некоторые для работы также определена функция createAccountList, которая создает список, а для удаления данных - функция deleteAccountList.
В файле account.c определим реализацию итератора:
#include <stdio.h>
#include <stdlib.h>
#include "account.h"
// структура данных
struct ACCOUNT
{
char* login;
char* password;
struct ACCOUNT* next;
};
// структура итератора
struct ITERATOR
{
char* data;
struct ACCOUNT* element;
};
// список объектов - указатель на первый элемент
static struct ACCOUNT* accountList;
struct ITERATOR* createIterator()
{
struct ITERATOR* iterator = malloc(sizeof(struct ITERATOR));
iterator->element = accountList;
return iterator;
}
void destroyIterator(struct ITERATOR* iterator)
{
free(iterator);
}
char* getUserName(struct ITERATOR* iterator)
{
if(iterator->element)
{
iterator->data=iterator->element->login; // устанавливем данные итератора
iterator->element = iterator->element->next; // сдвигаем итератор на следующий элемент списка
return iterator->data;
}
return NULL;
}
// создаем список с начальными данными
void createAccountList()
{
struct ACCOUNT* tom = malloc(sizeof(struct ACCOUNT));
tom->login ="Tomas";
tom->password = "qwerty";
accountList = tom;
struct ACCOUNT* bob = malloc(sizeof(struct ACCOUNT));
bob->login ="Bob";
bob->password = "12345";
tom->next = bob;
struct ACCOUNT* tim = malloc(sizeof(struct ACCOUNT));
tim->login ="Tim";
tim->password = "45678";
bob->next = tim;
tim->next = 0;
}
// создаем список с начальными данными
void deleteAccountList()
{
while(accountList)
{
free(accountList);
accountList = accountList->next;
}
}
Здесь сами данные представлены структурой ACCOUNT. Допустим, она представляет учетную запись и хранит имя и пароль пользователя. И поскольку эта структура также представляет элемент связанного списка учетных записей, то она также определяет поле next, которое ссылается на следующую структуру ACCOUNT:
struct ACCOUNT
{
char* login;
char* password;
struct ACCOUNT* next;
};
Для перебора списка структур ACCOUNT определена структура ITERATOR
struct ITERATOR
{
char* data;
struct ACCOUNT* element;
};
В поле data структура будет хранить собственно данные, которые будут возвращаться пользователю. В нашем случае данные ACCOUNT состоят из двух частей - имени и пароля. Однако, допустим, мы не хотим, чтобы к паролю был доступ, поэтому будем возвращать только имя пользователя через данное поле data.
Другое поле - element представляет текущий элемент в наборе объектов ACCOUNT, на который указывает итератор.
После определения структур определяем указатель на структуру ACCOUNT, который будет представлять первый элемент списка (и по сути весь список по цепочке):
static struct ACCOUNT* accountList;
Далее идет определение функции создания итератора:
struct ITERATOR* createIterator()
{
struct ITERATOR* iterator = malloc(sizeof(struct ITERATOR));
iterator->element = accountList;
return iterator;
}
Здесь выделяется память под структуру ITERATOR и устанавливается текущий элемент - первый элемент списка.
Также определена функция удаления итератора, которая просто освобождает его память:
void destroyIterator(struct ITERATOR* iterator)
{
free(iterator);
}
Для перемещения итератора по списку определена функция getUserName:
char* getUserName(struct ITERATOR* iterator)
{
if(iterator->element)
{
iterator->data=iterator->element->login; // устанавливем данные итератора
iterator->element = iterator->element->next; // сдвигаем итератор на следующий элемент списка
return iterator->data;
}
return NULL;
}
В данном случае если текущий элемент интератора не равен NULL (если он равен NULL, то это символизирует конец списка), то в поле data итератора получаем логин пользователя - это те данные, которые возвращаются из функции. И затем сдвигаем итератор на следующий элемент списка.
Таким образом, при вызове функции getUserName внешний код получит логин из текущей учетной записи, а итератор сдвигается к следующей учетной записи в списке.
Для тестирования итератора в основной файле программы - файле app.c определим следующий код:
#include <stdio.h>
#include "account.h"
int main(void)
{
createAccountList(); // создаем данные
char* username;
struct ITERATOR* iterator = createIterator(); // создаем итератор
while((username = getUserName(iterator))) // проходим итератором по списку учетных записей
{
printf("%s\n", username);
}
destroyIterator(iterator); // удаляем итератор
deleteAccountList(); // удаляем данные
}
Вначале создаем список, чтобы у нас были типовые данные для теста, и итератор. Затем в цикле последовательно проходим итератором по всем элементам:
while((username = getUserName(iterator)))
При каждом вызове функции getUserName() мы получим значение поля login текущего элемента, на который указывает итератор, и переместим итератор к следующему элементу.
Пример компиляции и работы программы:
c:\C>gcc -Wall -pedantic app.c account.c -o app & app Tomas Bob Tim c:\C>
Стоит отметить, что конкретная реализация итератора может отличаться в зависимости от требований и конкретных задач. Так, в примере выше итератор хранит данные в отдельном поле, но мы можем обойтись и без него и напрямую возвращать данные. Также мы можем возвращать указатель на данные или их копию. Но общая схема будет аналогичной - вызываем функцию, которую передаем итератор, и итератор возвращает данные и переходит к новому элементу.
При такой организации программы мы можем при необходимости обновлять структуру данных, внося некоторые изменения в код итератора, но эти обновления не затронут внешний код - он также будет вызвывать функцию, в которую будет передавать итератор. Использование итератора скорет от внешнего кода всю сложность реализации перебора объектов. Кроме того, внешнему коду доступны только к те данные, к которым он может имет доступ.
В то же время использование итератора усложняет общую организацию программы. Внешний код должен не забывать вызывать функции создания и удаления итератора.