Массив без инициализации

Введение

Привет, хабр. Я хотел бы рассказать о забавной структуре данных под названием «Массив без инициализации».

Во многих языках программирования для корректной работы с массивом необходимо его инициализировать сразу после объявления. Будем считать, что инициализация есть присвоение всем элементам какого-либо одинакового значения. Если массив состоит из N элементов, алгоритмическая сложность этой операции — O(N). Однако, можно показать, что располагая в трое большим объемом памяти, можно обойтись инициализацией за O(1).

Алгоритм

Формализуем задачу: имея O(N) памяти, реализовать за O(1) операции инициализации, set(value, index) и get(index), где index в пределах от 1 до N; при этом, если для операции get не было соответствующего вызова set ранее, необходимо генерировать исключение.

Заведем переменную count, в которой будем хранить количество уже использованных элементов, инициализируем ее нулем. Кроме этого, объявим три массива длины N: arr, ind, cnt.
В arr будем хранить сами значения на соответствующих местах, а для ind и cnt поддерживать следующий инвариант:

• значение cnt[i] корректно, если i <= count;
  
• если cnt[i] корректно, то ind[cnt[i]] = i и arr[cnt[i]] — уже установленное значение.
  

Другими словами, в ind и cnt хранятся ссылки друг на друга, только в ind индексы соответствуют вызовам set, a cnt заполняется по-порядку.

Реализуем процедуру проверки, используется ли уже данный элемент:

bool isEmpty(int i) {	
	if (ind[i] > 0 && ind[i] <= count && cnt[ind[i]] == i) {
		// В случае, если указатели в ind и cnt установлены верно
		// и порядковый номер не превышает общее число элементов,
		// этот элемент используется.
		return 0;
	}
	return 1;
}

Теперь научимся изменять какую-нибудь ячейку:

void set(int v, int i) {
	arr[i] = v; // Устанавливаем значение
	if (isEmpty(i)) {
		// Если инициализации здесь еще не было
		ind[i] = ++count; // Увеличиваем общее количество и делаем первую ссылку
		cnt[count] = i; // Делаем вторую ссылку
	}
}

А get выглядит совсем просто:

int get(int i) {
	if (isEmpty(i)) {
		// Генерируем исключение, элемент не проинициализирован
	} else {
		return arr[i];
	}
}