arrayIn order to initialize an array, you need to pass over all its cells and put there a zero, as the default initial value. That process takes O(n) time, whereas n = array_size.

However, we can tweak this tedious process and know whether the array has a garbage in it or not, without the need to first go all over its cells.

The pay off is saving a lot of time in reaching for the cells, but we have to trade off between time and place(i.e. physical memory).

Initializing in O(1)

The method calls for allocating 2 extra memory spaces alongside the original array, to save the cells that we already put value in them:

Untitled

array: This is the main data-structure that we read from and write to.
sideArray: we save in it indexes of the cells in ‘array’ that we written to.
stackArray: verify that the content of ‘sideArray’ isn’t garbage.

How does it WORK??!

suppose we put value in cell index in array :
array[index] = value
then we update sideArray and stackArray like this:
sideArray[index] = top
stackArray[top] = index
top = top + 1

Therefore, we can guarantee that each cell with an index which satisfy: index > top contains garbage value.
On the other hand, if the index satisfy: index <= top we make the following check:
(stackArray[sideArray[index]] == index) is true?

IS true: then array[index] has a real value that we are interested in reading
NOT ture: then array[index] has a garbage value

Implementation in C++

/*
 * array.h
 *
 *  Created on: 2 April 2015
 *      Author: bassam
 */

#ifndef ARRAY_H_
#define ARRAY_H_

#include <stdio.h>;
#include <stdlib.h>;
#include <iostream>;
/***************************************************************/
template<typename T>;
class Array {
private:
	int size;
	T* data;
	int top;
	T* stackArray;
	T* sideArray;
	const T GARBAGE = T();
	bool is_garbage(int index);
public:
	Array(int size);
	~Array();
	T operator[](const int index) const;
	T&amp;amp; operator[](const int index);
	void print() const;
};
/***************************************************************/
/*constructor*/
template<typename T>;
Array&amp;lt;T&amp;gt;::Array(int s) : size(s), top(0) {
	data = new T[size];
	stackArray = new T[size];
	sideArray = new T[size];
}
/***************************************************************/
/*destructor*/
template<typename T>
Array&amp;lt;T&amp;gt;::~Array() {
	delete data;
	delete stackArray;
	delete sideArray;
}
/***************************************************************/
template<typename T>
T Array&amp;lt;T&amp;gt;::operator[](const int index) const {
	if(index &amp;gt; top) {
		return GARBAGE;
	} else if(stackArray[sideArray[index]] == index) {
		return data[index];
	}
	return GARBAGE;
}
/***************************************************************/
template<typename T>
T&amp;amp; Array&amp;lt;T&amp;gt;::operator[](const int index) {
	sideArray[index] = top;
	stackArray[top] = index;
	top++;
	return (data[index]);
}
/***************************************************************/
template<typename T>
void Array&amp;lt;T&amp;gt;::print() const {
	for(int i = size; i &amp;gt;= 0; --i) {
		std::cout &amp;lt;&amp;lt; &amp;quot;data[&amp;quot; &amp;lt;&amp;lt; i &amp;lt;&amp;lt; &amp;quot;] = &amp;quot;&amp;lt;&amp;lt; data[i] &amp;lt;&amp;lt;
	&amp;quot;		, sideArray[&amp;quot; &amp;lt;&amp;lt; i &amp;lt;&amp;lt; &amp;quot;] = &amp;quot; &amp;lt;&amp;lt; sideArray[i] &amp;lt;&amp;lt;
              "		, stackArray[&amp;quot; &amp;lt;&amp;lt; i &amp;lt;&amp;lt; &amp;quot;] = &amp;quot;&amp;lt;&amp;lt; stackArray[i]&amp;lt;&amp;lt; &amp;quot;\n&amp;quot;;
	}
}
#endif /* ARRAY_H_ */

Driver code – main()

/*
 * main.cpp
 *
 *  Created on: 2 April 2015
 *      Author: bassam
 */

#include &amp;quot;array.h&amp;quot;
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
int main() {
	Array<int> array = Array&amp;lt;int&amp;gt;(10);
	array.print();
	/*initialize:*/
	array[2] = 22;
	array[1] = 13;
	std::cout << "---------------------------------------\n";
	array.print();
	return 0;
}

Output

out

Advertisements