|
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;
}
Do'stlaringiz bilan baham: |
