Array Class in C++
// Swapping by three copies
template <typename T>
void swap(T& x, T& y) {
T tmp = x; x = y; y = tmp;
}
// simple exception class
class ArrayException : public exception {
const char* msg;
ArrayException(){}; // no default constructor
public:
explicit ArrayException(const char* s) throw() : msg(s) {}
const char* what() const throw() { return msg; }
};
// simple fixed-size array template
template <typename T>
class Array {
private:
static const int SPARE_CAPACITY = 16;
static const int maxSize = 1000;
int _size;
int _capacity;
T* _arrayPtr;
public:
// Constructor
explicit Array (int initSize = 0) : _size{initSize}, _capacity{initSize + SPARE_CAPCITY}
{ _arrayPtr = new T[_capacity]; }
Array(const Array& rhs) : _size{rhs.size()}, _capacity{rhs.capacity()}, _arrayPtr{nullptr}
{
_arrayPtr = new T[_capacity];
for (int k = 0; k < _size; ++k) _arrayPtr[k] = rhs.get(k);
}
Array& operator= (const Array& rhs) {
Array copy = rhs;
swap(*this, copy);
return *this;
}
~Array() { delete[] _arrayPtr; }
Array(Array&& rhs) : _size{rhs.size()}, _capacity{rhs.capacity()}, _arrayPtr{rhs._arrayPtr}
{
rhs._arrayPtr = nullptr;
rhs._size = 0;
rhs._capacity = 0;
}
Array& operator= (Array&& rhs) {
swap(_size, rhs._size);
swap(_capacity, rhs._capacity);
swap(_arrayPtr, rhs._arrayPtr);
return *this;
}
void resize(in newSize) {
if (newSize > _capacity) reserve(newSize*2);
_size = newSize;
}
void reserve(int newCapacity) {
if (newCapacity < _size) return;
T* newArray = new T[newCapacity];
for (int k = 0; k < _size; ++k) newArray[k] = _arrayPtr[k];
_capacity = newCapacity;
swap(_arrayPtr, newArray);
delete[] newArray;
}
T& operator[](int index) { return _arrayPtr[index]; }
const T& operator[](int index) const { return _arrayPtr[index]; }
bool empty() const { return size() == 0; }
int size() const { return _size; }
int capacity() const { return _capacity; }
T & get(const int);
void push_back(const T& x) {
if (_size == _capacity) reserve(2*_capacity+1);
arrayPtr[_size++] = x;
}
void pop_back() { --_size; }
const T& back() const { return arrayPtr[_size-1]; }
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() { return &_arrayPtr[0]; }
const_iterator begin() const { return &_arrayPtr[0]; }
iterator end() { return &_arrayPtr[size()]; }
const_iterator end() const { return &_arrayPtr[size()]; }
void insertByOrder(const T);
void update(const int, const T);
void remove(const T);
void display();
int linearSearch(const T);
void selectionSort();
int binarySearch(const T, const int, const int);
int findMin();
int findMax();
int countBetween(const T, const T);
T findMost();
};
Objective 1
Write an algorithm and a program that creates an array which can hold 100 integers, and initialize it where each element of the array is equal to \(2*i+1\), where \(i\) is the index of the element. Display those values on the screen. Search through the array, and count the number of elements which are between 15 and 65.
template <typename T>
void Array<T>::display() {
if (empty()) throw ArrayException("Array is empty!");
T* ptr = _arrayPtr;
do {
cout << *ptr << endl;
} while (ptr++ != _arrayPtr+size());
}
template <typename T>
int Array<T>::countBetween(const T a, const T b) {
if (empty()) throw ArrayException("Array is empty!");
T maxValue = a > b ? a : b, minValue = a < b ? a : b;
T* ptr = _arrayPtr;
int counter = 0;
do {
if (*ptr >= minValue && *ptr <= maxValue) {
counter++;
}
} while (ptr++ != _arrayPtr+size());
return counter;
}
int main(int argc, char** argv) {
try {
Array<int> A(100);
// Initialize array
for (int i = 0; i < 100; i++) {
A.push_back(2*i+1);
}
// Display array
cout << "Display values in array: " << endl;
A.display();
// Count number between 15 and 65
int a = 15, b = 65;
cout << "The number of elements between 15 and 65 is " << A.countBetween(a, b) << endl;
cin.get();
} catch (ArrayException& e) {
cout << "Array error: " << e.what() << endl;
}
}
Objective 2
Write an algorithm and a program that ask the user to type 10 integers of an array and an integer value \(v\). The program will search if the value \(v\) exists in the array and must remove the first occurrence of \(v\), shifting each following element left and adding a zero at the end of the array. The program must then write the final array.
template <typename T>
int Array<T>::linearSearch(const T val) {
if (empty()) throw ArrayException("Array is empty!");
T* ptr = _arrayPtr;
int i = 0;
do {
if (*ptr == val) {
return i;
}
++i;
} while (ptr++ != _arrayPtr+size());
return -1;
}
template <typename T>
void Array<T>::update(const int pos, const T i) {
if (empty()) throw ArrayException("Array is empty!");
_arrayPtr[pos] = i;
}
template <typename T>
void Array<T>::remove(const T val) {
if (empty()) throw ArrayException("Array is empty!");
int i = linearSearch(val);
if (i == -1) return;
else if (i = end()) update(end(), 0);
else {
T* ptr1 = _arrayPtr+i, *ptr2 = ptr1;
do {
*ptr1++ = *++ptr2;
} while (ptr1 != _arrayPtr+end());
*ptr1 = 0;
}
}
int main(int argc, char** argv) {
try {
Array<int> A(10);
// Ask for user input
int number, val, pos;
cout << "Please enter 10 integers" << endl;
for (int i = 0; i < 10; i++) {
cout << "Integer " << i+1 << ": ";
cin >> number;
A.push_back(number);
}
// Ask for number to delete
cout << "Please enter a integer to delete: ";
cin >> val;
// Check and remove number
pos = A.linearSearch(val);
if (pos != -1) {
A.remove(val);
cout << "Value is found and first occurence is deleted." << endl;
} else {
cout << "Value not found." << endl;
}
// Display array
cout << "Display array after deletion: " << endl;
A.display();
cin.get();
cin.get();
} catch (ArrayException& e) {
cout << "Array error: " << e.what() << endl;
}
return 0;
}
Objective 3: maximum and minimum values of an array
Write an algorithm and a program that determine the largest and the smallest value in an array of integers A. Next, display the value and position of the maximum and minimum. If the array contains several maxima or minima, the program will retain the position of the first maximum or minimum encountered.
template <typename T>
T& Array<T>::get(const int pos) {
if (empty()) throw ArrayException("Array is empty!");
return _arrayPtr[pos];
}
template <typename T>
int Array<T>::findMin() {
if (empty()) throw ArrayException("Array is empty!");
T* ptr = _arrayPtr, value = *ptr++;
int index, i = 1;
do {
if (*ptr < value) {
value = *ptr;
index = i;
}
++i;
} while (ptr++ != _arrayPtr+size());
return index;
}
template <typename T>
int Array<T>::findMax() {
if (empty()) throw ArrayException("Array is empty!");
T* ptr = _arrayPtr, value = *ptr++;
int index, i = 1;
do {
if (*ptr > value) {
value = *ptr;
index = i;
}
++i;
} while (ptr++ != _arrayPtr+size());
return index;
}
int main(int argc, char** argv) {
try {
Array<int> A(10);
// Initialize random seed
srand(time(NULL));
// Initialize array with random numbers
for (int i = 0; i < 10; i++) {
A.push_back(rand() % 100);
}
// Display array
cout << "Display array: " << endl;
A.display();
// Find minimum and maximum value
int minPos = A.findMin(), maxPos = A.findMax();
cout << "The minimum value is " << A.get(minPos) << " and the first occurence is in position " << minPos << endl;
cout << "The maximum value is " << A.get(maxPos) << " and the first occurence is in position " << maxPos << endl;
cin.get();
} catch (ArrayException& e) {
cout << "Array error: " << e.what() << endl;
}
}
Objective 4: insert a value into a sorted array
An array A of size \(NMAX\) contains \(N(<NMAX)\) integer values sorted in ascending order; the \((N+1)^{th}\) value is undefined. Write an algorithm and a program that inserts a given VAL value from keyboard in the array A to obtain an array of \(N+1\) sorted values.
template <typename T>
void Array<T>::insertByOrder(const T val) {
if (_size == _capacity) reserve(2*_capacity+1);
T* ptr1 = _arrayPtr, *ptr2 = ptr1+end(), *ptr3 = ptr2--;
while (*ptr1 < val && ptr1 != ptr3) ptr1++;
if (ptr1 == ptr3)
push_back(val);
else {
push_back(*ptr3);
while (ptr3 != ptr1) {
*ptr3-- = *ptr2--;
}
*ptr1 = val;
}
}
int main(int argc, char** argv) {
try {
Array<int> A(15);
// Initialize random seed
srand(time(NULL));
// Initialize array with random ascending numbers
for (int i = 0; i < 10; i++) {
A.push_back(i*10 + rand()%10);
}
// Display array
cout << "Display array: " << endl;
A.display();
// Ask for number to insert
int val;
cout << "Please enter a interger to insert: ";
cin >> val;
A.insertByOrder(val);
// Display array after insertion
cout << "Display array after insert " << val << endl;
A.display();
cin.get();
cin.get();
} catch (ArrayException& e) {
cout << "Array error: " << e.what() << endl;
}
}
Objective 5: find a value in an array
Write an algorithm and a program that search in an array of integers a \(VAL\) value entered from the keyboard by using a serial searching. Display the position of VAL if it is in the table, otherwise display a corresponding message. The POS value that is used to memorize the position of the value in the array, will have the value -1 as long as VAL was not found. Do the same but by using a binary search.
template <typename T>
void Array<T>::selectionSort() {
if (empty()) throw ArrayException("Array is empty!");
T* ptr1 = _arrayPtr, *ptr2 = ptr1, *ptr3 = _arrayPtr+size(), *ptr4, temp;
while (ptr2 != ptr3) {
ptr4 = ptr2;
ptr1 = ptr2+1;
do {
if (*ptr1 < *ptr4)
ptr4 = ptr1;
} while (ptr1++ != ptr3);
temp = *ptr2;
*ptr2++ = *ptr4;
*ptr4 = temp;
}
}
template <typename T>
int Array<T>::binarySearch(const T val, const int low, const int high) {
if (empty()) throw ArrayException("Array is empty!");
if (low > high)
return -1;
int mid = static_cast<int>((low+high)/2);
T* ptr = _arrayPtr;
if (*(ptr+mid) == val)
return mid;
if (*(ptr+mid) < val)
binarySearch(val, mid+1, high);
else
binarySearch(val, low, mid-1);
}
int main(int argc, char** argv) {
try {
Array<int> A(10);
// Initialize random seed
srand(time(NULL));
// Initialize array with random numbers
for (int i = 0; i < 10; i++)
A.push_back(rand() % 100);
// Display array
cout << "Display array: " << endl;
A.display();
// Sort array
A.selectionSort();
cout << "Display array after sorting: " << endl;
A.display();
// Ask for value to search
int val;
cout << "Please enter a interger to search: ";
cin >> val;
// Search value
int pos1, pos2;
pos1 = A.linearSearch(val);
pos2 = A.binarySearch(val, 0, A.end());
if (pos1 != -1) {
cout << "Value found by linear search in position " << pos1 << endl;
} else {
cout << "Value not found by linear search, position returns " << pos1 << endl;
}
if (pos2 != -1) {
cout << "Value found by binary search in position " << pos2 << endl;
} else {
cout << "Value not found by binary search, position returns " << pos2 << endl;
}
cin.get();
} catch (ArrayException& e) {
cout << "Array error: " << e.what() << endl;
}
}
Objective 6
Write an algorithm and a program to find the most existing element in an array of integers.
template <typename T>
T Array<T>::findMost() {
if (empty()) throw ArrayException("Array is empty!");
Array<T> valueArray(size());
Array<int> counterArray(size());
T* ptr = _arrayPtr;
valueArray.push_back(*ptr++);
counterArray.push_back(1);
int pos, counter;
do {
pos = valueArray.linearSearch(*ptr);
if (pos == -1) {
valueArray.push_back(*ptr);
counterArray.push_back(1);
}
else {
counterArray.get(pos)++;
}
} while (ptr++ != _arrayPtr+size());
pos = counterArray.findMax();
return valueArray.get(pos);
}
int main(int argc, char** argv) {
try {
Array<int> A(10);
// Initialize random seed
srand(time(NULL));
// Initialize array with random numbers
for (int i = 0; i < 10; i++)
A.push_back(rand() % 10);
// Display array
cout << "Display array: " << endl;
A.display();
// Find most existing value
cout << "The most exsiting value is " << A.findMost() << endl;
cin.get();
} catch (ArrayException & e) {
cout << "Array error: " << e.what() << endl;
}
}