Курсоры

В предыдущем разделе мы говорили о присваивании элементам массива. Для массива Foo* все прекрасно работало, но попытка присвоить что-нибудь элементу строковой ассоциации кончается неудачей.

association[String( He11o )] = String( Good looking );

Дело в том, что левая часть не является ни левосторонним выражением (lvalue), ни классом с перегруженным оператором =. В этом случае можно сконструировать аргумент с использованием интерфейса вставки в коллекцию на базе функций класса, поскольку это все-таки не настоящий массив, а нечто загримированное под него с помощью оператора []. Многие классы, перегружающие оператор [], с точки зрения семантики являются массивами, но используют хитроумные структуры данных для оптимизации. Давайте рассмотрим конкретный пример (разреженные массивы), а затем вернемся к более общим коллекциям (таким как ассоциации).

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

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

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

class SparseArray { private:

struct Node {

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

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

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

Node(lndex 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[](lndex i)

Simp1eSparseArray::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 сообщениями об ошибках. Можно было бы создать интерфейс на базе функций, но тогда у клиента нарушится иллюзия того, что он имеет дело с нормальным, честным массивом. Существует ли способ использовать оператор [] в левой части операции присваивания для индексов, которых еще нет? Оказывается, существует, но для этой цели нам потребуется новая идиома - курсор.

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

Итак, вторая попытка. Наша основная цель - чтобы операторная функция 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-> ()!