C++ Array Based Data Structure

Arrays add items very quickly, linear time, O(n), if sorted and constant time, O(1), if unsorted, and binary searches are very fast, O(log(n)). Removing items is also very fast (linear if sorted, constant time if unsorted). See array vs. binary search tree.

Written in C++ using templates.

#include <time.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <ctime>
using namespace std;

#define DEFAULT_SIZE 1000

template <typename TData> void Sort(TData ** const parray, const unsigned int size)
{
	if (size >= 2)
	{
		if (size <= 30) // insertion sort
		{
			for (unsigned int i = 1; i < size; i++)
			{
				TData *temp = parray[i];
				unsigned int j = i;
				while (j > 0 && (*temp) < (*parray[j - 1]))
				{
					parray[j] = parray[j - 1];
					j--;
				}
				parray[j] = temp;
			}
		}
		else // quick sort
		{
			TData *pivot = parray[size / 2];
			TData **left = parray;
			TData **right = parray + size - 1;
			while (true)
			{
				while ((left <= right) && **left < *pivot) left++;
				while ((left <= right) && **right > *pivot) right--;
				if (left > right) break;
				TData *temp = *left;
				*left++ = *right;
				*right-- = temp;
			}
			Sort(parray, right - parray + 1);
			Sort(left, parray + size - left);
		}
	}
}

template <class TData> class ArrayDataMembers
{
public:
	TData **items;
	unsigned int length, max;
	bool sorted;
	ArrayDataMembers() : max(DEFAULT_SIZE), length(0), sorted(false)
	{
		items = new TData*[max];
		for (int i = 0; i < max; items[i++] = nullptr);
	}
	ArrayDataMembers(unsigned int arraySize) : max(arraySize), length(0), sorted(false)
	{
		if (max == 0)
			max = DEFAULT_SIZE;
		items = new TData*[max];
		for (int i = 0; i < max; items[i++] = nullptr);
	}
	~ArrayDataMembers()
	{
		DeleteLength();
		if (items)
		{
			delete[]items;
			items = nullptr; // clean up the memory
		}
	}
	void DeleteLength()
	{
		if (items)
		{
			for (int i = 0; i < length; i++)
			{
				delete items[i];
				items[i] = nullptr; // clean up the memory
			}
		}
		length = 0;
		sorted = false;
	}
};

template <class TData> class Array
{
private:
	ArrayDataMembers<TData> *dm;
public:
	Array();
	Array(unsigned int arraySize);
	Array(const Array<TData> &obj);
	~Array();
	const Array<TData> &operator=(const Array<TData> &obj);
	unsigned int Length() const;
	bool IsSorted() const;
	void MakeUnsorted();
	void Add(const TData &data);
	const TData *operator[](const unsigned int index);
	bool RemoveValue(const TData &data);
	bool RemoveIndex(const unsigned int index);
	void Clear();
	unsigned int GetIndexOf(const TData &data); // returns Length() when data not found
};

template <class TData> Array<TData>::Array(const Array<TData> &obj) : dm(new ArrayDataMembers<TData>(1))
{
	this->operator=(obj);
}

template <class TData> const Array<TData> &Array<TData>::operator=(const Array<TData> &obj)
{
	if (this != &obj)
	{
		Clear();
		dm->max = obj.dm->max;
		dm->length = obj.dm->length;
		dm->sorted = obj.dm->sorted;
		if (dm->items)
			delete[]dm->items;
		dm->items = new TData*[dm->max];
		int i;
		for (i = 0; i < dm->length; i++)
		{
			dm->items[i] = new TData;
			*(dm->items[i]) = *(obj.dm->items[i]);
		}
		for (; i < dm->max; dm->items[i++] = nullptr);
	}
	return (*this);
}

template <class TData> Array<TData>::Array() : dm(new ArrayDataMembers<TData>())
{
}

template <class TData> Array<TData>::Array(unsigned int arraySize) : dm(new ArrayDataMembers<TData>(arraySize))
{
}

template <class TData> Array<TData>::~Array()
{
	delete dm;
}

template <class TData> bool Array<TData>::IsSorted() const
{
	return dm->sorted;
}

template <class TData> void Array<TData>::MakeUnsorted()
{
	dm->sorted = false;
}

template <class TData> unsigned int Array<TData>::Length() const
{
	return dm->length;
}

template <class TData> void Array<TData>::Add(const TData &data)
{
	if (dm->length == dm->max) // then increase size of array
	{
		dm->max <<= 1;
		TData **newArray = new TData*[dm->max];
		int i;
		for (i = 0; i < dm->length; newArray[i++] = dm->items[i]);
		for (; i < dm->max; newArray[i++] = nullptr);
		for (i = 0; i < dm->length; dm->items[i++] = nullptr);
		delete[]dm->items;
		dm->items = newArray;
	}
	dm->items[dm->length] = new TData;
	*(dm->items[dm->length++]) = data;
	if (dm->sorted)
	{
		TData *temp;
		unsigned int count;
		for (count = dm->length - 1; count > 0; count--) // reversed bubblesort with break statement
		{
			if (*(dm->items[count]) < *(dm->items[count - 1]))
			{
				temp = dm->items[count];
				dm->items[count] = dm->items[count - 1];
				dm->items[count - 1] = temp;
			}
			else
				break;
		}
	}
}

template <class TData> const TData *Array<TData>::operator[](const unsigned int index)
{
	// do not sort the data because it is possible to loop through the unsorted data
	// use GetIndexOf() to force a sort of the data
	// make sure to use Length() to know the size of the array so as not to exceed the bounds of the array of items
	return dm->items[index];
}

template <class TData> bool Array<TData>::RemoveValue(const TData &data)
{
	return RemoveIndex(GetIndexOf(data)); // just use the functions already available that can perform this action
}

template <class TData> bool Array<TData>::RemoveIndex(const unsigned int index)
{
	if (index < dm->length)
	{
		delete dm->items[index];
		dm->length--;
		if (dm->sorted)
		{
			for (int i = index; i < dm->length; i++)
				dm->items[i] = dm->items[i + 1];
		}
		else
			dm->items[index] = dm->items[dm->length];
		dm->items[dm->length] = nullptr; // clean up the memory
		return true;
	}
	return false;
}

template <class TData> unsigned int Array<TData>::GetIndexOf(const TData &data)
{
	// this procedure uses binary search so array must be sorted
	if (!dm->sorted)
	{
		Sort(dm->items, dm->length);
		dm->sorted = true;
	}
	int first = 0, last = dm->length - 1, middle;
	while (first <= last)
	{
		middle = (first + last) / 2;
		if (*(dm->items[middle]) == data)
			return middle;
		if (data > *(dm->items[middle]))
			first = middle + 1;
		else
			last = middle - 1;
	}
	return dm->length;
}

template <class TData> void Array<TData>::Clear()
{
	dm->DeleteLength();
}

int main()
{
	{
		Array<int> a(3);
		int n = time(0);
		srand(n);
		for (int i = 0; i < 20; i++)
		{
			n = rand();
			a.Add(n);
		}
		Array<int> a2 = a;
		for (int i = 0; i < a2.Length(); i++)
			cout << *a2[i] << endl;
		unsigned int idx = a2.GetIndexOf(n);
		if (idx < a2.Length())
		{
			cout << "FOUND: " << *a2[idx] << endl;
			cout << "REMOVING: " << n << endl;
			while (a2.RemoveValue(n));
			for (int i = 0; i < a2.Length(); i++)
				cout << *a2[i] << endl;
		}
	}
	{
		Array<string> a(3);
		string s;
		for (int i = 0; i < 20; i++)
		{
			char c[4] = { 0,0,0,0 };
			c[0] = c[1] = c[2] = (char)(rand() % 26) + 97;
			s = c;
			a.Add(s);
		}
		for (int i = 0; i < a.Length(); i++)
			cout << *a[i] << endl;
		unsigned int idx = a.GetIndexOf(s);
		if (idx < a.Length())
		{
			cout << "FOUND: " << s << endl;
			cout << "REMOVING: " << s << endl;
			while (a.RemoveValue(s));
			for (int i = 0; i < a.Length(); i++)
				cout << *a[i] << endl;
		}
	}
	return 0;
}