Курсоры и разреженные массивы

Итак, вторая попытка. Наша основная цель - чтобы операторная функция operator[] возвращала нечто, обладающее следующими свойствами:

1. Оно должно преобразовываться к типу содержимого массива.

2. Оно может использоваться в левой части операции присваивания для изменения содержимого соответствующей ячейки.

Это «нечто» представляет собой особый класс, который называется курсором (cursor). Ниже показан уже знакомый разреженный массив с курсором в операторной функции operator[]:

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:

SparseArray() : cells(NULL) {}

ArrayCursor operator[](Index i);

};

class ArrayCursor {

friend class SparseArray;

private:

SparseArray& array; // Обратный указатель на массив-владелец

Index index; // Элемент, представленный курсором

SparseArray::Node* node; // Если существует индекс, отличный от NULL

// Конструкторы объявлены закрытыми, поэтому пользоваться ими

// может только SparseArray. Первый конструктор используется, когда

// индекс еще не существует, а второй - когда индекс уже присутствует

// в массиве.

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);

};

ArrayCursor& ArrayCursor::operator=(Foo* foo) {

if (node == NULL) { // Индекс не существует

node = new SparseArray::Node(index, foo, array.cells);

array.cells = node;

}

else

// Индекс уже существует, изменить значение элемента

node->content = foo;

return *this;

}

ArrayCursor SparseArray::operator[](Index i)

{

SparseArray::Node* n = cells;

while (n != NULL)

if (n->index = i)

return ArrayCursor(*this, n); // Существует

else

n = n->next;

return ArrayCursor(*this, i); // Еще не существует

}

Ого! Что же происходит в этом хитроумном коде? Все волшебство заключено в двух операторных функциях, SparseArray::operator[]() и ArrayCursor::operator=(). SparseArray::

operator[]() возвращает ArrayCursor независимо от того, существует индекс или нет (об этом

ArrayCursor узнает по тому, какой конструктор был выбран). ArrayCursor::operator=(Foo*)

делает одно из двух: если индекс уже существует, элемент изменяется, а если не существует - он динамически добавляется в массив. В этом проявляется вся суть курсорности (курсоризма?): перегруженный оператор = выполняет присваивание не для самого курсора, а для структуры данных, от которой происходит курсор. Теперь присваивание работает независимо от того, существует индекс или нет.

array[Index(17, 29)] = new Foo; // Добавляет индекс

array[Index(17, 29)] = new Foo; // Изменяет значение с заданным индексом

Неплохо для часовой работенки, не правда ли? Наш массив работает совсем как настоящий. Почти.