In spring, when woods are getting green,
I'll try and tell You what I mean.
L.Carroll. Through the looking glass.

Проблема собственно в том, что ради такой простой структуры нечего и сыр-бор разводить. Если нам нужен просто массив, можно просто взять его шаблон из STL или MFC. Клянусь, это будет замечательное решение, у Вас будет огромный набор возможностей, да к тому же реализованных компактно и эффективно (в меру); если у Вас нет отклонений в психике, и Вы не порываетесь ежедневно вставить ассемблерный код в прогу на VB, этого будет достаточно. Увы, иногда нужно больше.

Ну, положим, Вам необходимо работать с геологической картой. Размер 1000х1000. Пять слоев. Если решать в лоб, то только для хранения и обработки геологических условий нужно иметь пять миллионов элементов. Совершенно ясно, всем и каждому, что создавать карту на основе простого массива абсолютно недопустимо. По видимому, объект карты должен хранить информацию только в ключевых точках, а значения между ними вычислять; при необходимости записи в карту следует проверять - есть ли такая точка во внутренней структуре, и если есть - записывать в нее, а если нет - создавать ее.

Наша карта сильно стала похожа на разреженный массив. Отличие в том, что в классическом разреженном массиве между "ключевыми" элементами хранятся нули, а у нас там лежит (как будто) значение предыдущего элемента. Процессы чтения и записи существенно различаются; в предыдущем шаге мы могли работать со ссылкой, читать и записывать ее. Сейчас операция чтения возвращает нам какую-то неопознанную... или неучтенную... шняжку новогоднюю, толку в нее писать никакого, она все равно свежевычисленная. Операция записи пишет. Вещи абсолютно разные, ничего общего. Авторитетные специалисты пишут: "никакого толку от оператора [], ... возможности разделить чтение и запись нет... надо писать на BASIC... на бумажечке".

Они не правы.

Выход есть. Нужно взять новогоднюю шняжку, опознать и учесть ее. Потом перегрузить у ней операторы operator[](), operator->() и оператор приведения типа к элементу массива. Вы узнаете ее? Да это сэр Хьюго Баскервиль собственной персоной, он же Умный Указатель, он же Курсор, он же Proxy-объект! Вот черт, кто бы знал... Далее его именуем Курсором за сходство с аналогом из баз данных.

Так теперь перед кодом давайте самое важное вычленим:

1. Массив возвращает в операторе operator[] курсор.
2. Курсор имеет перегруженный оператор присваивания operator=(), что позволяет нам грамотно обрабатывать вставки и записи в массив.
3. Курсор может неявно преобразовываться к значению элемента массива, что позволяет нам грамотно читать из массива.
4. Курсор имеет перегруженный оператор operator->(), что позволяет нам читать и ... и в общем все, что нужно; смотри предыдущие шаги.

Теперь мы имеем семантический массив. Внутри может быть что угодно, но снаружи он совершенно неотличим, вообще. Элджер справедливо замечает: "внутреннюю реализацию Вы можете сменить даже на последних стадиях разработки". Я справедливо замечаю: "и ни одна ..... не до......". (Вообще это нам сержант Прищепкин говорил по поводу начищенности пряжки, но и здесь вполне подходит).

Еще по коду: Я написал для примера код, имитирующий базу данных наподобие SQL, потом засунул базу в класс такого массива и все такое... но получилось около 300 строк, и наглядность совсем пропала. Так что беру попроще - связанный список.

class CThat {int a;};

class CCursor;
class CArray;
class CNode;

class CNode {
public:
	int index;
	CThat* that;
	CNode* next;   
	CNode (int _index, CThat* _that, CNode* _next):
		index(_index), that(_that), next(_next){};
};

class CCursor {
public:
	CArray* array;
	int index;
	CNode* node;
	CCursor(CArray* _array, int _index):
		array(_array), index(_index), node (NULL){};
	CCursor(CArray* _array, CNode* _node):
		array(_array), index (_node->index), node (_node){};
	CCursor& operator=(CThat* _that);
	operator CThat*();
	CThat* operator->();
};

class CArray {
public:
	CNode* cells;  
	CArray():cells(NULL){};
	CCursor operator[](int i);
};

CCursor CArray::operator[](int _index)
{
	CNode* pNode = cells;
	while (pNode!=NULL)
	{
		if (pNode->index ==_index)
		{
			return CCursor(this, pNode);
		}
		else pNode=pNode->next;
	}
	return CCursor( this, _index);
}

CCursor& CCursor::operator=(CThat* _that)
{
	if (node==NULL)
	{
		node = new CNode (index, _that, array->cells);
		array->cells = node;
	} else {
		node->that = _that;
	}
	return *this;
};

CCursor::operator CThat*()
{
	return node!=NULL ? node->that : NULL;
};

CThat* CCursor::operator->()
{
	if (node == NULL) {throw 1;}
	return node->that;
}