Partial ArrayList implementation in C++

Question

I've implemented a C++ version of Java ArrayList. It doesn't contain all the functionalities such as AddAll and iterators and such, but I still would appreciate criticism to my code correctness, style and flow and such

template <typename T>
class ArrayList
{
    public:
        ArrayList();
        ~ArrayList();
        ArrayList(const ArrayList<T>& other);
        ArrayList<T>& operator= (const ArrayList<T>& other);

        void add(const T& item); //Add item to end of array
        void add(const T& item, int index);
        void remove(const T& item); //Remove ALL occurrences of item from array
        void remove(int index);

        T& get(int index);
        void set(int index, const T& item);

    private:
        T* arr;
        int allocatedSize;
        int actualSize;
        const int INCREMENT = 10;
};

template<typename T>
ArrayList<T>::ArrayList()
{
    arr = new T[INCREMENT];
    allocatedSize = INCREMENT;
    actualSize = 0;
}

template<typename T>
ArrayList<T>::~ArrayList()
{
    delete[] arr;
}

template<typename T>
ArrayList<T>::ArrayList(const ArrayList<T>& other)
{
    arr = new T[other.allocatedSize];
    allocatedSize = other.allocatedSize;
    actualSize = other.actualSize;

    for(int i = 0; i<other.actualSize; i++)
        arr[i] = other.arr[i];
}

template<typename T>
ArrayList<T>& ArrayList<T>::operator= (const ArrayList<T>& other)
{
    delete[] arr;
    arr = new T[other.allocatedSize];
    allocatedSize = other.allocatedSize;
    actualSize = other.actualSize;

    for(int i = 0; i<other.actualSize; i++)
        arr[i] = other.arr[i];

    return *this;
}

//Add item to end of array
template<typename T>
void ArrayList<T>::add(const T& item)
{
    if(actualSize < allocatedSize)
    {
        actualSize++;
        arr[actualSize-1] = item;
    }
    else
    {
        allocatedSize += INCREMENT;

        T*cpy = new T[allocatedSize];

        for(int i=0; i<actualSize; i++)
            cpy[i] = arr[i];

        actualSize++;
        cpy[actualSize-1] = item;

        delete[] arr;
        arr = cpy;
    }
}

template<typename T>
void ArrayList<T>::add(const T& item, int index)
{
    if(index < actualSize - 1)
        return;

    allocatedSize = (actualSize < allocatedSize) ? allocatedSize : allocatedSize + INCREMENT;

    T*cpy = new T[allocatedSize];

    for(int i=0; i<index; i++)
        cpy[i] = arr[i];

    cpy[index] = item;

    for(int i = index; i<actualSize; i++)
        cpy[i+1] = arr[i];

    actualSize++;
    delete[] arr;
    arr = cpy;
}

//Remove ALL occurrences of item from array
template<typename T>
void ArrayList<T>::remove(const T& item)
{
    if(actualSize <= 0)
        return;

    T*cpy = new T[allocatedSize];
    T*cpyStart = cpy;
    T*arrStart = arr;

    for(int i = 0; i<actualSize; i++)
    {
        if(arr[i] != item)
        {
            *cpy = *arr;
            cpy++;
        }

        arr++;
    }

    cpy = cpyStart;
    arr = arrStart;

    delete[] arr;
    arr = cpy;
}

template<typename T>
void ArrayList<T>::remove(int index)
{
    if(index > actualSize - 1)
        return;

    for(int i = 0; i<actualSize; i++)
    {
        if(i>=index)
            arr[i] = arr[i+1];
    }
}

template<typename T>
T& ArrayList<T>::get(int index)
{
    return arr[index];
}

template<typename T>
void ArrayList<T>::set(int index, const T& item)
{
    if(index > actualSize - 1)
        return;

    arr[index] = item;
}

Answer 1

Preface

A lot of C++ programmers hate Java being translated to C++. The reason is not that either C++ or Java is bad, the reason is that they are very opposite in nature. Java doesn't make the programmer to worry about performance, safety and memory allocations. It does checks to ensure safety. C++ almost always offers more degree of control, thus providing opportunities to write more optimized code. Despite that, C++ has encapsulation as well, but it keeps it to the minimum required. It provides encapsulation only when it's free (e.g. compile time, or no overhead). It always tries to hold following:

don't pay for what you don't use

Your code

There are several problems in your code.

You got very close to strong exception safety. Unfortunately, you've missed one step of the copy and swap idiom. Namely the swap, so even if the deletion throws nothing bad will happen to the data in the container. I recommend this answer to enrich knowledge about C++ exception safety.

Your container new[]s everything. So there is a problem: if T is not default constructible, it is not possible to use your container. Some people use term lazy construction, but I prefer the following wording: you should not construct on memory allocation, you should retrieve uninitialized buffer, and then construct when needed. To do so you will need to call operator new. Use only non array version, since array version has very limited use.

Container copies every element on adding. C++11 introduced template parameter packs. With the feature you can write following code:

template <typename T>
template <typename ... Args>
void ArrayList<T>::emplace(Args... args)
{
    if (allocatedSize == actualSize)
    {
        //handle buffer resizing
    }

    new (copy + actualSize) T(args...);
    std::swap(copy, arr);
    ++actualSize;
    delete[] copy;
}

It will handle any constructor that T might have. It will also issue compile time error if there is no matching constructor to input arguments. The new expression used is called placement new. It constructs an element in the pointed to location specified.

Your container grows linearly. Often this is not enough. It will resize buffer too many times which will incur great overhead. Usual implementations increase the size exponentially. VC++ uses growth factor of 2 (probably as many others). Despite that, the article mentions how to get optimal growth factor.

You don't overload operator[]. I know that the code is meant to be ArrayList, but honestly it is not C++ without operator overloading. On top of that, usually container manipulations are not checked in C++. Your remove operation just does nothing on getting out of bounds. Surprising. std::vector uses special at function to perform checks and throw.

C++ programmers use std::size_t defined in <cstddef> when referring to the size of the objects in memory. The type has specific semantic: it is big enough to index all the elements in the memory. It is unsigned, which will suggest that users shouldn't pass negative values to the add and remove.

What is missing

Aside from iterators, here is the list:

1. std::initalizer_list constructor

2. resize

3. reserve

4. range add (based on iterators)

5. range erase (based on iterators)

6. Non resizing add on position (add should be amortized constant)

7. Move constructor

8. Move assignment operator (with point 7 and your already written code, you will fully implement rule of 5).

9. Placement add (using placement new)

10. Moving add

11. iterator based remove, add, constructor.

12. Move elements on buffer resizing if move is noexcept or no copy constructor is provided.

The way it should be

C++ has standard std::vector templated container. It mirrors the concepts of the ArrayList (contigious buffer, resizing, index based access). On top of that, it uses everything C++ has to offer. I recommend you to think about this: "When in Rome, do what Romans do".