I have implemented a primitive ArrayList
class in C++ as part of an attempt to learn about data structures and their optimizations. It currently has:
- Constructor/destructor
- Overloaded
[]
operator bool insert()
bool remove()
short LinearSearch()
short BinarySearch()
insert
and remove
return a bool
indicating success or failure. insert
can accept a negative number to insert from the end towards the front (-2 is the 2nd to last element); by default, insert
is called with index = 1
. The search functions return a short indicating the index, or -1 if it is not found.
It uses templates to allow for multiple types of data stored, but I am currently only concerned with number and boolean data types to be stored. If you have any tips or optimizations regarding the current functions, or operators/other functions that I should consider, please tell me. Thank you for your help.
Code:
#include <cstdlib> // for calloc/malloc
namespace structures {
template<typename T> class ArrayList {
private:
T* pointer;
public:
ArrayList(unsigned short len = 10);
~ArrayList();
T& operator[](unsigned short index);
const T& operator[](unsigned short index) const;
unsigned short length;
bool insert(const T& element, short index = -1);
bool remove(unsigned short index);
short LinearSearch(const T& element) const;
short BinarySearch(const T& element) const;
};
template<typename T> ArrayList<T>::ArrayList(unsigned short len) {
length = 0;
pointer = (T*)calloc(len, sizeof(T));
}
template<typename T> ArrayList<T>::~ArrayList() {
free(pointer);
}
template<typename T> T& ArrayList<T>::operator[](const unsigned short index) {
if (index > length) throw;
return pointer[index];
}
template<typename T> const T& ArrayList<T>::operator[] (const unsigned short index) const {
if (index > length || index < 0) throw;
return pointer[index];
}
template<typename T> bool ArrayList<T>::insert(const T& element, short index) {
if (index > (short)length) return false;
if (index < 0) index = length + index + 1;
if (length == sizeof(*pointer)/sizeof(T)) {
pointer = (T*)realloc(pointer, 2 * sizeof(*pointer)/sizeof(T));
}
if (index == length || index == -1) pointer[index] = element;
else {
for (short i = length; i > index; --i) {
pointer[i] = pointer[i-1];
}
pointer[index] = element;
}
++length;
return true;
}
template<typename T> short ArrayList<T>::LinearSearch(const T& element) const {
for (short i = 0; i < length; ++i) {
if (pointer[i] == element) return i;
}
return -1;
}
template<typename T> short ArrayList<T>::BinarySearch(const T& element) const{
short left = 0;
short right = length - 1;
short middle = (length - 1) / 2;
while (true) {
if (left > right) return -1;
if (element == pointer[middle]) return middle;
if (element > pointer[middle]) left = middle + 1;
else right = middle - 1;
middle = (left + right) / 2;
}
}
template<typename T> bool ArrayList<T>::remove(unsigned short index) {
if (index > length || index < 0) return false;
for (; index < length; ++index) {
pointer[index] = pointer[index + 1];
}
--length;
return true;
};
}