4
\$\begingroup\$

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);
*/
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Good Job! The title change helped too. For the future, we would prefer that you edit the existing question rather than post a new one, especially when you already have an up vote on the question (We don't want you to lose that up vote among other things), however, what's done is done. See the comment by @Mast in the 2nd Monitor. \$\endgroup\$
    – pacmaninbw
    Jul 13 '20 at 21:02
4
\$\begingroup\$

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 (this 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 RAW 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 needs 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 overcomplex:

    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 here here:

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

If allocted + 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 accesses.

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. That does this check. While the operator[] is normally unchecked accesses. 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;
}

Its 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 here.

https://lokiastari.com/series/

look at the section on Vector.

\$\endgroup\$
4
  • \$\begingroup\$ if(length + 1 > allocated && allocated + minAllocate <= std::numeric_limits<int16_t>::max()) Doesn't integer promotion prevent (allocated + minAllocate) from overflowing? \$\endgroup\$ Jul 13 '20 at 22:29
  • \$\begingroup\$ @DarkoNaito_09 Not if int == int16_t \$\endgroup\$ Jul 14 '20 at 0:31
  • \$\begingroup\$ And if int == uint16_t? \$\endgroup\$ Jul 14 '20 at 0:48
  • \$\begingroup\$ @DarkoNaito_09 Even if I am wrong why would you use that? If it is going to make even a person that understands all the type conversation rules sit down for twenty minutes to see if he agrees that it actually works then you have already failed in your most important task (convey the information simply and unambiguously to the reader). Mine on the other hand is guaranteed to work all the time in all situations and you don't have to think about if for 10 minutes to know that it will work. \$\endgroup\$ Jul 14 '20 at 1:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.