Primitive ArrayList Implementation

Question

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;
    };
}

Answer 1

   pointer = (T*)calloc(len, sizeof(T));

Say what? I’m used to getting people to stop using “naked new”, but this is C memory management! Why would you do that? You are not initialing any of the T objects you allocated room for. That may work for ints and other primitive types, but in general you are looking at a boom when you subsequently access an element.

unsigned short

Why use this for the size type? At the very least, abstract it as a member type, normally called size_type. The usual default type for this is std::size_t but there is a movement to switch to signed types for new containers.

   if (index > length) throw;

Throw what? This will crash since throw by itself is only allowed when there is a current exception being handled.

Your insert and remove take (signed) shorts, which conflicts with your use of unsigned for indexes. Besides not being able to represent all the values, you will have problems comparing them, which is exactly what you do in the first line.

To provide for the negative number indexing feature, either use the same approach as Eric Neibler (end - 5 rather than -5) or use the signed type for your length, as suggested earlier.

---

Your insert is re-allocating memory, which is not what I’m expecting. You are implementing a vector class, not an array class (which is fixed length). So why? What’s wrong with std::vector?

---

LinearSearch, BinarySearch: Don’t write these members. Instead, allow std::find etc. (as well as all other algorithms) to work with your container.

---

You re-allocate upon inserting, but not when deleting. But you don’t keep track of how much slack space you have.