Простой класс разреженного массива

Разреженный массив относится к числу основных структур данных. Он представляет собой матрицу, у которой большинство ячеек в любой момент времени остается пустым. Возможно, вы принадлежите к числу счастливчиков с 256 гигабайтами памяти на компьютере, но большинству из нас просто не хватит места для хранения всех ячеек матрицы 1000х1000х1000. Да и не хочется выделять память под миллиард ячеек, если в любой момент из них используется не более 1000. Несомненно, в вашем мозгу всплывают различные структуры данных, знакомые по начальному курсу программирования в колледже: связанные списки, бинарные деревья, хеш-таблицы и все прочее, что упоминает Кнут. На самом деле не так уж важно, какая структура данных лучше подойдет для низкоуровневой реализации.

Прежде всего необходимо понять, как же использовать эти низкоуровневые средства и одновременно создать для клиентских объектов впечатление, что они имеют дело с самым обычным массивом? В следующей реализации «методом грубой силы» для хранения данных используются связанные списки. Структура Index уже встречалась нам выше.

class SparseArray {

private:

struct Node {

Index index; // Индекс массива

Foo* content; // Содержимое массива по данному индексу

Node* next; // Следующий элемент списка

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

};

Node* cells; // Связанный список элементов

public:

SparseArray() : cells(NULL) {}

Foo* operator[](Index i);

};

inline Foo* SparseArray::operator[](Index i)

{

SimpleSparseArray::Node* n = cells;

while (n != NULL) {

if (n->index == i) // Использует перегруженный оператор ==

return n->content;

n = n->next;

}

return NULL;

}

Foo* foo = array[Index(17, 29)]; // Работает

С чтением массива проблем нет. Если индекс существует, возвращается содержимое массива по данному индексу. Если индекс в массиве отсутствует, значение NULL полностью соответствует идее предварительной инициализации массива значениями NULL. Минутку, но как добавить в массив новую ячейку или изменить уже существующую? Значение, возвращаемое операторной функцией operator[], не является ни левосторонним выражением (lvalue), ни классом с перегруженным оператором = и по нему нельзя выполнить присваивание.

array[Index(31, 37)] = foo; // Не работает

Ваш компилятор не спит ночами и ждет, когда же у него появится такая замечательная возможность забить поток сеrr сообщениями об ошибках. Можно было бы создать интерфейс на базе функций, но тогда у клиента нарушится иллюзия того, что он имеет дело с нормальным, честным массивом.

Существует ли способ использовать оператор [] в левой части операции присваивания для индексов, которых еще нет? Оказывается, существует, но для этой цели нам потребуется новая идиома - курсор.