PROWAREtech
C++: Array Based Data Structure
An O(1) to O(n) 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). And arrays use less memory than node based data structures. 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 qisort(TData ** const parray, const unsigned int size)
{
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])) // overload < operator in class
{
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++; // overload < operator in class
while ((left <= right) && **right > *pivot) right--; // overload > operator in class
if (left > right) break;
TData *temp = *left;
*left++ = *right;
*right-- = temp;
}
qisort(parray, right - parray + 1);
qisort(left, parray + size - left);
}
}
template <class TData> class ArrayDataMembers
{
public:
TData **items;
unsigned int length, max;
bool sorted;
ArrayDataMembers();
ArrayDataMembers(unsigned int arraySize);
~ArrayDataMembers();
void DeleteLength();
};
template <class TData> class Array
{
private:
ArrayDataMembers<TData> *dm;
public:
Array();
Array(unsigned int arraySize);
Array(const Array<TData> &obj); // copy constructor
~Array();
const Array<TData> &operator=(const Array<TData> &obj); // assignment operator
unsigned int Length() const;
bool IsSorted() const;
void StopSorting();
void Add(TData *data); // used for adding data that is created with new operator, will be deleted by this array data structure
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();
void Reverse(); // this reverses the array and makes the data unsorted
void Sort();
unsigned int GetIndexOf(const TData *data); // returns Length() when data not found; note: this sorts the array to perform a binary search
};
template <class TData> ArrayDataMembers<TData>::ArrayDataMembers()
{
max = DEFAULT_SIZE;
length = 0;
sorted = false;
items = new TData*[max];
for (unsigned int i = 0; i < max; items[i++] = nullptr);
}
template <class TData> ArrayDataMembers<TData>::ArrayDataMembers(unsigned int arraySize)
{
max = arraySize;
length = 0;
sorted = false;
if (max == 0)
max = DEFAULT_SIZE;
items = new TData*[max];
for (unsigned int i = 0; i < max; items[i++] = nullptr);
}
template <class TData> ArrayDataMembers<TData>::~ArrayDataMembers()
{
DeleteLength();
if (items)
{
delete[]items;
items = nullptr; // clean up the memory
}
}
template <class TData> void ArrayDataMembers<TData>::DeleteLength()
{
if (items)
{
for (unsigned int i = 0; i < length; i++)
{
delete items[i];
items[i] = nullptr; // clean up the memory
}
}
length = 0;
sorted = false;
}
template <class TData> Array<TData>::Array(const Array<TData> &obj) // copy constructor
{
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];
unsigned 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;
}
// stop sorting array's new data; use this when adding large amounts of data
// all at once to the array because an unsorted array adds data very fast
template <class TData> void Array<TData>::StopSorting()
{
dm->sorted = false;
}
template <class TData> unsigned int Array<TData>::Length() const
{
return dm->length;
}
// adding data to it is much slower when having to maintain a sorted array
// so try to add most of the data before the array gets sorted
// sorting a large, unsorted array all at once is very fast
template <class TData> void Array<TData>::Add(TData *data)
{
if (dm->length == dm->max) // then increase size of array
{
dm->max <<= 1;
TData **newArray = new TData*[dm->max];
unsigned int i;
for (i = 0; i < dm->length; i++)
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++] = data;
if (dm->sorted) // if sorted then move the new data to its place in the sorted array
{
TData *temp;
unsigned int count;
// reversed bubblesort with break statement when data is sorted
// nothing is faster than bubblesort when the first element in an array is out-of-place
// so reverse it to sort an item that is added to the end of an array
// notice: the outerloop that causes the bubbling is not needed (perhaps it's no longer "bubblesort")
for (count = dm->length - 1; count > 0; count--)
{
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;
}
}
}
// this is used for variables that are on the stack (local)
template <class TData> void Array<TData>::Add(const TData &data)
{
TData *p = new TData;
*p = data; // overload the = operator for data
Add(p);
}
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() or Sort() to force a sort of the data, use Reverse() to reverse 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 (unsigned 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> void Array<TData>::Clear()
{
dm->DeleteLength();
}
// NOTE: this array could be modified to work in reverse and keep the data sorted
template <class TData> void Array<TData>::Reverse()
{
dm->sorted = false;
unsigned int i = 0, j = dm->length - 1;
while (i < j)
{
TData *temp = dm->items[i];
dm->items[i] = dm->items[j];
dm->items[j] = temp;
i++;
j--;
}
}
template <class TData> void Array<TData>::Sort()
{
qisort(dm->items, dm->length);
dm->sorted = true;
}
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();
int first = 0, last = dm->length - 1, middle;
while (first <= last)
{
middle = (first + last) / 2;
if (*(dm->items[middle]) == *data) // overload == operator in class
return middle;
if (*(dm->items[middle]) < *data) // overload < operator in class
first = middle + 1;
else
last = middle - 1;
}
return dm->length;
}
class Person
{
private:
string firstname, lastname;
public:
Person() {};
Person(const char *first, const char *last)
{
firstname = first;
lastname = last;
}
string FirstName() const { return firstname; }
string LastName() const { return lastname; }
// overload these operators to make it compatible with the algorithms used
bool operator<(const Person &obj) const
{
if (this->lastname == obj.lastname)
return this->firstname < obj.firstname;
return this->lastname < obj.lastname;
}
bool operator>(const Person &obj) const
{
if (this->lastname == obj.lastname)
return this->firstname > obj.firstname;
return this->lastname > obj.lastname;
}
bool operator==(const Person &obj) const
{
return (this->lastname == obj.lastname && this->firstname == obj.firstname);
}
const Person &operator=(const Person &obj)
{
if (this != &obj)
{
this->firstname = obj.firstname;
this->lastname = obj.lastname;
}
return (*this);
}
};
int main()
{
{
Array<int> a(3);
int n = time(0);
srand(n);
for (unsigned int i = 0; i < 20; i++)
{
n = rand();
a.Add(n);
}
Array<int> a2 = a;
for (unsigned 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 (unsigned int i = 0; i < a2.Length(); i++)
cout << *a2[i] << endl;
}
cout << endl;
a2.Reverse();
for (unsigned int i = 0; i < a2.Length(); i++)
cout << *a2[i] << endl;
}
{
Array<string> a(3);
string s;
for (unsigned int i = 0; i < 20; i++)
{
char c[4] = { 0,0,0,0 };
c[0] = (char)(rand() % 26) + 97;
c[1] = (char)(rand() % 26) + 97;
c[2] = (char)(rand() % 26) + 97;
s = c;
a.Add(s);
}
for (unsigned 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 (unsigned int i = 0; i < a.Length(); i++)
cout << *a[i] << endl;
}
}
{
Array<Person> people(3);
people.Add(new Person("Vince", "Young")); // these will be deleted by the array's deconstructor
people.Add(new Person("Xavier", "Taylor"));
people.Add(new Person("John", "Williams"));
people.Add(new Person("Angela", "Taylor"));
people.Add(new Person("Sam", "Smith"));
people.Add(new Person("Julie", "Simms"));
people.Add(new Person("Susie", "Williams"));
people.Add(new Person("John", "Brown"));
for (unsigned int i = 0; i < people.Length(); i++)
cout << people[i]->LastName() << ", " << people[i]->FirstName() << endl;
Person person("Xavier", "Taylor");
unsigned int j = people.GetIndexOf(&person); // this will sort array
if (j < people.Length())
cout << endl << "FOUND: " << people[j]->LastName() << ", " << people[j]->FirstName() << endl << endl;
for (unsigned int i = 0; i < people.Length(); i++)
cout << people[i]->LastName() << ", " << people[i]->FirstName() << endl;
cout << endl;
people.Reverse();
for (unsigned int i = 0; i < people.Length(); i++)
cout << people[i]->LastName() << ", " << people[i]->FirstName() << endl;
}
return 0;
}
Coding Video
Comment
