C++: библиотека программиста

 
113 
}; 
Компиляторы обожают подобные ситуации — вроде бы все выглядит вполне логично, но как-то 
выпало из спецификации языка. Это дает им возможность поразмяться и вывалить все туманные 
сообщения об ошибках, которые они приберегли на черный день. Но когда сообщения перестанут 
сыпаться, наступает ваш черед смеяться, поскольку существует простой обходной путь. 
struct Index { 
int 
x; 
int 
y; 
Index(int ex, int why) : x(ex), y(why) {} 
bool operator==(const Index& i) { return x == i.x && y == i.y; } 
}; 
class WorksFine { 
public: 
Foo& operator[](Index i); 
}; 
array[Index(17, 29)].MemberOfFoo();
// Работает 
Index
представляет собой структуру с тривиальным конструктором. Причина перегрузки оператора 
==
станет ясна позже. Выражение 
Index(17,29)
создает анонимный экземпляр, который упаковывает 
два измерения массива в один аргумент. Правда здорово? Получай, компилятор! 
Множественные перегрузки оператора [] 
Оператор 
[]
может иметь и несколько вариантов перегрузки для данного класса при условии, что 
сигнатуры остаются уникальными. Например, одна версия может получать аргумент типа 
int
, а другая 
— аргумент 
char*
, который преобразуется к 
int
функцией 
atoi()
. Скорее всего, ваша коллекция 
может индексироваться несколькими способами. 
class StringArray { 
public: 
const String& operator[](int index); 
int operator[](const String&); 
}; 
String str = array[17];
// 
Первая форма 
int index = array[String(“Hello”)]; // Вторая форма 
Первый оператор 
[]
реализует семантику массива: по целому индексу возвращается значение элемента 
с этим индексом. Второй оператор обеспечивает обратную возможность: по значению находится 
соответствующий индекс массива. В этой схеме используется пара допущений (например, уникальное 
целое, которое возвращается в качестве индекса несуществующего значения), но в целом идея вполне 
понятна. 
Виртуальный оператор [] 
Оператор 
[]
, как и любой другой оператор или функцию, можно объявить виртуальным и 
переопределить в производных классах. В некотором базовом классе определяется абстрактный 
интерфейс, а все подробности реализации предоставляются в производных классах. Такая схема 
хорошо сочетается с гомоморфными иерархиями классов, описанными в части 3. 

---

 114 
Курсоры 
В предыдущем разделе мы говорили о присваивании элементам массива. Для массива 
Foo*
все 
прекрасно работало, но попытка присвоить что-нибудь «элементу» строковой ассоциации кончается 
неудачей. 
association[String(“Hello”)] = String(“Good looking”); 
Дело в том, что левая часть не является ни левосторонним выражением (lvalue), ни классом с 
перегруженным оператором 
=
. В этом случае можно сконструировать аргумент с использованием 
интерфейса вставки в коллекцию на базе функций класса, поскольку это все-таки не настоящий 
массив, а нечто загримированное под него с помощью оператора 
[]
. Многие классы, перегружающие 
оператор 
[]
, с точки зрения семантики являются массивами, но используют хитроумные структуры 
данных для оптимизации. Давайте рассмотрим конкретный пример (разреженные массивы), а затем 
вернемся к более общим коллекциям (таким как ассоциации). 
Простой класс разреженного массива 
Разреженный массив относится к числу основных структур данных. Он представляет собой матрицу, у 
которой большинство ячеек в любой момент времени остается пустым. Возможно, вы принадлежите к 
числу счастливчиков с 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; 
} 

---