C++ Dynamic Array Class Testing

Question

I'm creating a basic Dynamic Array class in C++, and I'd like to know if there are any bugs/memory leaks I haven't noticed yet.

dyn_arr.h :

#ifndef DYN_ARR_H_INCLUDED
#define DYN_ARR_H_INCLUDED

template <class T>

class DynArr
{
    public:
        DynArr(uint16_t startSize = 0);
        ~DynArr();

        T& operator[](uint16_t);
        const T& operator[](uint16_t) const;

        T& getLast() {return elements[length - 1];}
        const T& getLast() const {return elements[length - 1];}

        T& append(const T&);
        T& insert(const T&, uint16_t);

        bool kickoutLast();
        bool remove(uint16_t);

        uint16_t getLength() const {return length;}
        uint16_t getAllocated() const {return allocated;}

    private:
        static const uint8_t minAllocate;

        uint16_t allocated;
        uint16_t length;

        T* elements;

        void copyElements(T*, T*);
        void transfer(T*);
};


#include "dyn_arr.cpp"

#endif // DYN_ARR_H_INCLUDED

dyn_arr.cpp :

template <class T>
const uint8_t DynArr<T>::minAllocate = 4;

template <class T>
DynArr<T>::DynArr(uint16_t startSize):
    allocated(0), length(0)
{
    do
    {
        allocated += minAllocate;
    }while(allocated < startSize);

    elements = new T[allocated];
}

template <class T>
DynArr<T>::~DynArr()
{
    if(length > 0) delete [] elements;
}

template <class T>
T& DynArr<T>::append(const T& t)
{
    if(length + 1 > allocated && allocated + minAllocate <= std::numeric_limits<int16_t>::max())
    {
        transfer(new T[allocated += minAllocate]);
    }

    return elements[length++] = t;
}

template <class T>
bool DynArr<T>::kickoutLast()
{
    if(length - 1 > 0)
    {
        --length;

        if(allocated - length == minAllocate)
        {
            transfer(new T[allocated -= minAllocate]);
        }

        return true;
    } else if(length - 1 == 0)
    {
        delete [] elements;

        length = allocated = 0;

        return true;
    } else
    {
        return false;
    }
}

template <class T>
T& DynArr<T>::operator[](uint16_t i)
{
    if(i < length)
        return elements[i];
    else return elements[length - 1];
}

template <class T>
const T& DynArr<T>::operator[](uint16_t i) const
{
    if(i < length)
        return elements[i];
    else return elements[length - 1];
}

template <class T>
T& DynArr<T>::insert(const T& t, uint16_t in)
{
    if(length + 1 > allocated && allocated + minAllocate <= std::numeric_limits<int16_t>::max())
    {
        transfer(new T[allocated += minAllocate]);
    }

    for(uint16_t i = length; i > in; --i)
    {
        elements[i] = elements[i - 1];
    }

    ++length;

    return elements[in] = t;
}

template <class T>
bool DynArr<T>::remove(uint16_t rm)
{
    if(length - 1 > 0)
    {
        --length;

        for(uint16_t i = rm; i < length; ++i)
        {
            elements[i] = elements[i + 1];
        }

        if(allocated - length == minAllocate)
        {
            transfer(new T[allocated -= minAllocate]);
        }

        return true;
    } else if(length - 1 == 0)
    {
        delete [] elements;

        length = allocated = 0;

        return true;
    } else
    {
        return false;
    }
}

template <class T>
void DynArr<T>::copyElements(T* e1, T* e2)
{
    for(uint16_t i = 0; i < length; ++i)
    {
        e1[i] = e2[i];
    }
}

template <class T>
void DynArr<T>::transfer(T* newE)
{
    copyElements(newE, elements);

    delete[] elements;
    elements = newE;
}

code example:

#include <iostream>
#include <iomanip>
#include <thread>
#include <chrono>
#include "dyn_arr.h"

using namespace std;

template <class T>
void printArrInf(const DynArr<T>& arr, uint16_t i);

template <class T>
void printArr(const DynArr<T>& arr)
{
    for(uint16_t i = 0; i < arr.getLength(); ++i)
        cout << arr.getAllocated() << ", " << arr.getLength() << " : " << arr[i] << '\n';

    cout << '\n';
}

int main()
{
    DynArr<int> arr;

    arr.append(1);
    arr.append(2);
    arr.append(3);
    arr.append(4);

    printArr(arr);

    arr.insert(9, 1);
    arr.remove(0);

    arr.kickoutLast();

    printArr(arr);


    return 0;
}

/*
    arr.append(1);
    arr.append(2);
    arr.append(3);

    //arr.insert(9, 1) = 10;

    for(uint16_t i = 0; i < arr.getLength(); ++i)
        printArrInf(arr, i);

    cout << '\n';

    arr.append(4);
    arr.append(5);

    for(uint16_t i = 0; i < arr.getLength(); ++i)
        printArrInf(arr, i);

    cout << '\n';

    arr.kickoutLast();

    for(uint16_t i = 0; i < arr.getLength(); ++i)
        printArrInf(arr, i);

    cout << '\n';

    arr.append(9);

    for(uint16_t i = 0; i < arr.getLength(); ++i)
        printArrInf(arr, i);
*/

Answer 1

Overview

Currently the code is broken as it does not implement the rule of three.

You can make vast improvements to the efficiency by learning how to use placement new and manually calling the destructor for members of the container. This will remove the need to force initialization on all members.

A nice addition would be support for move semantics. Both for the container itself but also for putting elements into the container.

Your sizing algorithm makes you re-size after every four elements (or minAllocation size). But this basically means that you are forced to resize all the time (resizing is proportional to the number of elements). The standard container simply doubles the allocated space when it needs more, which makes allocations logarithmic compared to the number of elements (there is an argument for 1.5 rather than 2 as it allows for better memory re-use, but the standard implementations have abandoned this in preference for 2).

Code Review

That's quite unique.

#ifndef DYN_ARR_H_INCLUDED
#define DYN_ARR_H_INCLUDED

But I would still add a namespace to it.
I would also put your code in a namespace.

---

Why the empty line?

template <class T>

class DynArr

---

You have the basic constructors.

        DynArr(uint16_t startSize = 0);
        ~DynArr();

But you have a raw pointer but don't implement the rule of three/five.
The compiler generates a default copy constructor and copy assignment operators. These are not good for row pointers as they simply do a shallow copy.

---

You have the copy additions operations.

        T& append(const T&);
        T& insert(const T&, uint16_t);

But you want to add the move equivalents:

        T& append(T&&);                     // Notice the &&
        T& insert(T&&, uint16_t);           // Binds R-Value references

---

No idea what this does:

        bool kickoutLast();

Maybe a more standard name would be better.

---

If you separate the template methods into a different file they normally go into the *.tpp file (not *.cpp) file.

#include "dyn_arr.cpp"

Lots of build tools will try and automatically build all the *.cpp file so making it a *.tpp file helps to distinguish this is really part of the header file.

Note: All the template methods defined outside the class need to be declared "inline". This tells the compiler that it is likely to see multiple definitions of the functions.

---

Is this really different for different types of T?

template <class T>
const uint8_t DynArr<T>::minAllocate = 4;

---

This is over-complex:

    do
    {
        allocated += minAllocate;
    }while(allocated < startSize);

I would simplify to:

    allocated = *(startSize / minAllocate) + 1) * minAllocate;

---

This is your biggest issue.

    elements = new T[allocated];

Here allocated means the amount of space I have available to use for type T. While length means the amount of space I have used up.

This both allocates the space and initializes all the objects (calls their constructor). If the type T is expensive to create this could be an issue. Also, why are you paying to construct objects you may never use?

There is also the problem that you now require T to have a default (no argument) constructor. Not all types have a zero argument constructor.

You will need to learn about placement new and manually calling the destructor to make this work correctly.

---

Don't bother with the check.

    if(length > 0) delete [] elements;

Always delete the elements. If it is null then that is OK.

---

Subtle bug here:

    if(length + 1 > allocated && allocated + minAllocate <= std::numeric_limits<int16_t>::max())

If allocated + minAllocated is greater than max then it will probably be truncated and therefore very small and thus not trigger this if statement.

You should subtract allocated from max and see if there is enough room left to allocate what you need.

 if(length + 1 > allocated && 
    (std::numeric_limits<int16_t>::max() - allocated) >= minAllocate)

---

This is a checked access:

template <class T>
T& DynArr<T>::operator[](uint16_t i)
{
    if(i < length)
        return elements[i];
    else return elements[length - 1];
}

Normally if you want a checked access, you use at() method, which does this check - while the operator[] is normally unchecked. The point is not to make an experienced developer pay a cost just because a beginner would need to.

 for(int loop = 0; loop < a.getLength(); ++loop)
    a[loop] += 5;   // Why do I need a check here.
                    // I have already guranteede that loop is smaller
                    // than the length so that extra test is wasteful
 }


 a.at(13) += 15;    // Sure test needed here I have not checked
                    // a3 is in the correct bounds.

---

Subtle error here:

template <class T>
void DynArr<T>::transfer(T* newE)
{
    copyElements(newE, elements);

    delete[] elements;   // If any T has a destructor that throws
                         // (yes rare) then your object now
                         // leaves element pointing at an invalid
                         // pointer and you leaked `newE`.
    elements = newE;
}

It's simple to fix:

 {
     copyElements(newE, elements);
     std::swap(elements, newE);
     delete newE;                    // Even if this throws
                                     // Your object is still good.
                                     // and you don't leak anything.
 }

Plug for my stuff

I wrote a series of articles on how to create a vector-like class.

look at the section on Vector.