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

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

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

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

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

Итак, вторая попытка. Наша основная цель - чтобы операторная функция 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[lndex(17, 29)] = new Foo; Добавляет индекс

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

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

Операторы преобразования и оператор ->

Осталось добавить еще пару штрихов. Во-первых, оператор [] в правой части операции присваивания работает уже не так, как было написано, поскольку он возвращает ArrayCursor, а не Foo* или Foo*&. Но причин для беспокойства нет, потому что Foo*() в случае необходимости автоматически преобразует ArrayCursor к Foo*. Вторая проблема заключается в том, что оператор [] не может использоваться слева от оператора ->; на помощь приходит operator-> ()!

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)

Инициировать исключение

else

return node->contents;

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

array[Index(17, 29)]->MemberOfFoo(); Тоже работает

Ну вот, теперь можно расслабиться. Для клиентского объекта наш массив ничем не отличается от обычного. Это означает, что вы можете программировать для простой семантики массива и отдельно выбрать внутреннюю реализацию структур данных даже на поздней стадии проекта.

Что-то знакомое

Взгляните еще раз на класс ArrayCursor. Он представляет собой объект, который косвенно ссылается на Foo, имеет операторную функцию operator Foo*() и перегруженный оператор ->, позволяющий обращаться к членам Foo через курсор. Выглядит знакомо? Так и должно быть. Курсоры на самом деле представляют собой следующее поколение умных указателей. Все, что говорилось об умных указателях в трех последних главах, легко распространяется и на курсоры. И наоборот, изучение «курсорологии» помогает расширить некоторые концепции умных указателей. Перегружая оператор = для умного указателя, вы сумеете избежать многих неприятных проблем. Например, вспомните концепцию кэширующего указателя, который в последний момент считывал объект с диска в операторе ->. Подобная перегрузка оператора присваивания нередко очищает программу и избавляет код от ненужных технических деталей. Другой полезный прием - привязка умного указателя к некоторой структуре данных (подобно тому, как ArrayCursor привязывался к классу SparseArray). Такое гармоничное объединение идей проектирования является хорошим признаком - мы приближаемся к неуловимой высшей истине C++. Чем более передовыми идиомами вы пользуетесь, тем больше возникает сходства.

Итераторы

Итак, мы можем работать с любым отдельным элементом коллекции. Как насчет того, чтобы перебрать все элементы? Тупой перебор в цикле for не поможет:

for (int i = 0; i < ... чего?

При выбранной реализации разреженного массива измерения не имеют верхней границы. Впрочем, даже если бы она и была, хотелось бы вам перебирать 1 000 000 000 всевозможных индексов в поисках