Итератор абстрактного массива

Перейдем к простому примеру на основе нашего разреженного массива. Классы массива и курсора взяты из предыдущего обсуждения без изменений за исключением того, что класс массива теперь также возвращает итератор лишь для непустых ячеек. Универсальный шаблон итератора не используется, поскольку функция Next() возвращает как индекс, так и объект с этим индексом, а это требует нестандартного интерфейса к Next(). Классы курсора и разреженного массива остались в прежнем виде. Я не утверждаю, что это хороший разреженный массив - однако он обладает достаточно простым дизайном, который не будет нам мешать при обсуждении итераторов.

// SparseArray.h

class ArrayCursor;

class SparseArray {

friend class ArrayCursor;

private:

struct Node {

Index index;

Foo* content;

Node* next;

Node(Index i, Foo* c, Node* n) : index(i), content(c), next(n) {}

};

Node* cells;

public:

class Iterator {

private:

Node* next;

public:

Iterator(Node* first) : next(first) {}

bool More() { return next != NULL; ]

Foo* Next(Index& index)

{

Foo* object = next->content;

index = next->index;

next = next->next;

return object;

}

};

Iterator* NonEmpty() { return new SparseArray::Iterator(cells); }

SparseArray() : cells(NULL) {}

ArrayCursor operator[](Index i);

};

class ArrayCursor {

friend class SparseArray;

private:

SparseArray& array;

Index index;

SparseArray::Node* node;

ArrayCursor(SparseArray& arr, Index i)

: array(arr), index(i), node(NULL) {}

ArrayCursor(SparseArray& arr, SparseArray::Node* n)

: array(arr), node(n), index(n->index) {}

public:

ArrayCursor& operator=(Foo* foo);

operator Foo*() { return node != NULL ? node->content : NULL; }

Foo* operator->()

{

if (node == NULL)

throw nil_error;

else

return node->current;

}

};

Пожалуй, я бы не рискнул показывать эту программу потенциальному работодателю как

доказательство глубоких познаний в С++, но она проста, быстра и справляется со своей задачей. Ниже перечислены некоторые изменения, которые можно было бы внести в коммерческий вариант:

Инкапсулируйте SparseArray::Iterator, превратив его в абстрактный базовый класс, а

затем верните производный класс из скрытой реализации NonEmpty() (эта идея также хорошо

подходит для классов массива и курсора, поэтому мы разовьем ее в части 3).

Предоставьте дополнительные итераторы, которые включают как пустые, так и непустые

ячейки.

Гарантируйте определенный порядок перебора ячеек.

Возвращайте из Next() курсор, а не указатель, чтобы клиенты могли изменять содержимое

ячейки во время перебора. Если это будет сделано, индекс может храниться в курсоре, поэтому отпадает необходимость возвращать его в виде отдельного ссылочного аргумента Next().