3
\$\begingroup\$

How can I improve this code for a dynamic and re-sizable array data structure?

Array.h

#ifndef _ARRAY_H_
#define _ARRAY_H_

class Array
{
private:
    int * m_ArrayContainer;//These two variables
    int m_Size;            //work in pairs.

private:
    void SetSize(int size);     
    void AllocateMemoryOfSize(int size);
    void DeallocateMemory();        

public:
    Array();
    Array(int size);
    Array(Array & arr);
    void operator = (Array & arr);      
    void Resize(int newSize);
    int GetSize();
    void SetItem(int index, int value);
    int GetItem(int index);
    ~Array();
};

#endif

Array.cpp

#include "Array.h"
#include <iostream>

#pragma region Private Methods

void Array :: SetSize(int size)
{
    this->m_Size = size;
}
void Array :: AllocateMemoryOfSize(int size)
{
    this->m_ArrayContainer = new int[size];
    this->SetSize(size);
}
void Array :: DeallocateMemory()
{           
    if(this->GetSize() > 0)
    {
        delete [] this->m_ArrayContainer;
        this->SetSize(0);       
    }
}   
void Array :: SetItem(int index, int value)
{
    this->m_ArrayContainer[index] = value;
}
#pragma endregion

Array :: Array()
{
    //std::cout<<"Array()...\n";

    this->m_ArrayContainer = NULL;

    this->SetSize(0);
}
Array :: Array(int size)
{
    //std::cout<<"Array(int size)...\n";

    this->SetSize(0);

    this->Resize(size);
}
void Array :: Resize(int newSize)
{
    int oldSize = this->GetSize();

    for(int i=0 ; i<oldSize ; i++)
    {
        this->SetItem(i, NULL);
    }
    this->DeallocateMemory();

    this->AllocateMemoryOfSize(newSize);
    this->SetSize(newSize);
}
Array :: Array(Array & arr)
{
    //std::cout<<"Array(Array & arr)...\n";

    this->SetSize(0);

    int size = arr.GetSize();       

    this->Resize(size);

    for(int i=0 ; i<size ; i++)
    {
        this->SetItem(i, arr.GetItem(i));
    }
}
void Array :: operator = (Array & arr)
{
    //std::cout<<"operator = (Array & arr)...\n";

    this->SetSize(0);

    int size = arr.GetSize();       

    this->Resize(size);

    for(int i=0 ; i<size ; i++)
    {
        this->SetItem(i, arr.GetItem(i));
    }
}       
int Array :: GetSize()
{
    return this->m_Size;
}   
int Array :: GetItem(int index)
{
    return this->m_ArrayContainer[index];
}
Array :: ~Array()
{       
    //std::cout<<"~Array()...\n";
    this->DeallocateMemory();       
}
\$\endgroup\$
  • \$\begingroup\$ Just checking. Buy you have seen std:vector<>? \$\endgroup\$ – Martin York Jun 30 '15 at 20:30
2
\$\begingroup\$

Move Semantics

Since it is 2015 and you should be using C++14.
You should probably implement the Move Constructor and Move Assignement operators.

Stop uisng this->

This is considered bad practice in C++. If you have to use it to disambiguate identifiers then you have done a bad job of naming your identifiers (and this is a code smell).

Do You reall need a set size?

void Array :: SetSize(int size)

Seems a little obtuse. Since this is a private member and this is a private method. You are not buying yourself anything with the extra layer of indirection.

Delete works on nullptr

You are allowed to delete on nullptr. You do not need to check for empty/nullptr before calling delete. Just do it always. That makes sure your always deallocate allocated resources.

void Array :: DeallocateMemory()
{           
    if(this->GetSize() > 0)
    {
        delete [] this->m_ArrayContainer;
        this->SetSize(0);       
    }
}   

Look at operator[]

void Array :: SetItem(int index, int value)
{
    this->m_ArrayContainer[index] = value;
}
int Array :: GetItem(int index)
{
    return this->m_ArrayContainer[index];
}

Set/Get are OK. But it does not allow you to modify values in place. So it is more standard to use operator[] which will return a reference to the internally stored object and thus allow you to then modify the object in place. Also if your array at some point is expanded to hold other types. Then you are spending time copying data into and out of the Array. By providing a reference you avoid the copy operation if you don't need it.

Prefer Initializer list.

You should initialize all members in the constructor. Also when you do so. You should prefer to use the initializer list.

Array :: Array()
{
    //std::cout<<"Array()...\n";

    this->m_ArrayContainer = NULL;

    this->SetSize(0);
}

// I would have done this:
Array::Array()
    : m_ArrayContainer(new int[0])
    , m_Size(0)
{}

In this version of the constructor. You forget to initialize the m_ArrayContainer member.

Array :: Array(int size)
{
    //std::cout<<"Array(int size)...\n";

    this->SetSize(0);

    this->Resize(size);
}

This means that member has an indeterminate value. Reading from an undefined variable caused "undefined behavior". You MUST set the value before reading from it. So you should just initialize it in the constructor unless you have a very good reason.

Setting old items to NULL has no meaning.

You are holiding integers. Setting these value to NULL has no meaning. NULL is used to represent pointers. If you had used the correct value for NULL which is nullptr the compiler would have given you an error. The reason this works is that the NULL macros will auto convert to an integer of value 0.

void Array :: Resize(int newSize)
{
    int oldSize = this->GetSize();

    for(int i=0 ; i<oldSize ; i++)
    {
        this->SetItem(i, NULL);
    }
    this->DeallocateMemory();

    this->AllocateMemoryOfSize(newSize);
    this->SetSize(newSize);
}

Also when re-sizeing. You should NEVER deallocate first. If the allocation of new memory fails then your object is in an invalid state and there is no way to repair the damage.

Also don't you want to copy the data from the original array into the new array! This is generally what a resize does. If you are not copying the values into the new data storage area then this should probably be called Realloc.

The processes should be:

  1) Allocate new space.
     If this fails throw an exception.
  2) Copy the data from the old data storage to the new data storage.
     If this fails (it should not fail for integers but can fail for other types).
     First deallocate storage from step (1) then throw an exception.
  3) Swap the data arrays (swaps are exception safe).
  4) Deallocate the space of the original storage area.

Copy Constructor.

Normally you pass the thing being copied by const&. You normally don't need to modify the source so to make sure you don't accidentally change something you pass as a constant this makes sure the compiler picks up an accidental changes.

Again your forgot to set all the memebers to an initial state.

Array :: Array(Array & arr)
{
    //std::cout<<"Array(Array & arr)...\n";

    this->SetSize(0);

    int size = arr.GetSize();       

    this->Resize(size);

    for(int i=0 ; i<size ; i++)
    {
        this->SetItem(i, arr.GetItem(i));
    }
}

That for() loop can be written in several better ways.

Copy and Swap Idiom

Here you destroy the old data before you know that a copy will work. Thus potentially leaving your object in an invalid state. Look up the copy and swap idiom. It is a safe affective way to perform an assignment.

void Array :: operator = (Array & arr)
{
    //std::cout<<"operator = (Array & arr)...\n";

    this->SetSize(0);

    int size = arr.GetSize();       

    this->Resize(size);

    for(int i=0 ; i<size ; i++)
    {
        this->SetItem(i, arr.GetItem(i));
    }
}       

Const Correctness

If a method is retrieving data but not altering the object. Then you should mark the function is const. Thus if you pass the object as a const object you can still call methods that are marked const.

int GetSize();

// This method does not change the state of the object.
// It should thus be declared const.

int GetSize() const;

All the points above in a simple example:

class Array
{
private:
    int  Size;
    int* data;

public:
    Array(int size = 0)        // Have a default value and this works
        : size(size)           // as a normal and default constructor.
        , data(new int[size])
    {}
    ~Array()
    {
        delete [] data;
    }
    Array(Array const& copy)    // Copy constructor
        : size(copy.size)
        , data(new int[size])
    {
        std::copy(copy.data, copy.data + size, data);
    }
    Array& operator=(Array const& copy) // Assignment operator
    {
        Arr tmp(copy);         // Make your copy (do it safely into a temp variable). If it fails this variable is not affected.
        tmp.swap(*this);       // Now swap the temp and this variable so
        return *this;          // this is now a copy of the input.
    }                          // temp variable destoryed here. Thus releasing
                               // the original value.
    // The easiest way to move.
    // Is to just swap the current object with the
    // object you are moving. This way the src object
    // is guaranteed to be in a valid state (so its destructor will work)
    Arr(Arr&& move)            noexcept // Move constructor.
        : size(0)
        , data(nullptr)
    {
        move.swap(*this);
    }
    Arr& operator(Arr&& move)  noexcept // Move assignment.
    {
        move.swap(*this);
        return *this;
    }
    void swap(Arr& other)      noexcept // swap (is no exception)
    {
        std::swap(data, other.data);
        std::swap(size, other.size);
    }
    void resize(int newSize)
    {
        Arr tmp(newSize);
        std::copy(data, data + std::min(size, newSize), tmp.data);
        tmp.swap(*this);
    }
    int getSize() const                    {return size;}
    int&       operator[](int index)       {return data[index];}
    int const& operator[](int index) const {return data[index];}
};
void swap(Arr& lhs, Arr& rhs)
{
    lhs.swap(rhs);
}
\$\endgroup\$
3
\$\begingroup\$

You have a couple of memory leaks.

First, the DeallocateMemory() will only delete the object's memory block if the size is greater than 0:

void Array :: DeallocateMemory()
{           
    if(this->GetSize() > 0)  // GetSize() will return zero at this point
    {
        delete [] this->m_ArrayContainer;
        this->SetSize(0);       
    }
}   

However, in C++ it's legal to allocate a memory block with 0 size. (See the Q&A C++ new int[0] -- will it allocate memory? on Stack Overflow for more information.) When you allocate memory, you actually get two things: the memory that you asked for, and some data that the C++ runtime uses to keep track of that memory block.

If you have a sequence of code like:

Array a(0);
a.Resize(1);

the constructor will allocate a 0-sized block of memory and the extra data for the C++ runtime. When Resize() calls DeallocateMemory(), it'll see that your data block is 0-sized, won't invoke delete[], and leak that memory when AllocateMemoryOfSize() overwrites the object's m_ArrayContainer pointer:

void Array :: AllocateMemoryOfSize(int size)
{
    this->m_ArrayContainer = new int[size]; // Memory leak!
    this->SetSize(size);
}

Second, in your assignment operator, the first thing you do is to set the size of this to zero:

void Array :: operator = (Array & arr)
{
    this->SetSize(0);
    int size = arr.GetSize();       
    this->Resize(size);
    /// [stuff elided].
}       

Next, you call Resize with the size of the other object:

void Array :: Resize(int newSize)
{
    int oldSize = this->GetSize();

    for(int i=0 ; i<oldSize ; i++)
    {
        this->SetItem(i, NULL);
    }
    this->DeallocateMemory();

    this->AllocateMemoryOfSize(newSize);
    this->SetSize(newSize);
}

Note that the for-loop at the start doesn't actually do anything because the size of this has been set to zero by the time you get here. Even if it didn't, it would be unnecessary because the intent is to delete[] that memory soon afterwards, and once it has been returned to the heap, the contents of memory are irrelevant.

Then you call DeallocateMemory(), which won't delete any memory because the size field in this has already been set to zero. Finally, you call AllocateMemoryOfSize() which unconditionally overwrites the pointer to the array, leaking memory the same way as in my first point above.

To fix these bugs, I would:

  1. Check if m_ArrayContainer is a null pointer to decide if I need to delete[] it.

    void Array :: DeallocateMemory()
    {           
        if(this->m_ArrayContainer != NULL)
        {
            delete [] this->m_ArrayContainer;
            this->m_ArrayContainer = NULL;
            this->SetSize(0);       
        }
    }   
    
  2. Don't zero out the memory in this just before deleting it; your Resize() method then becomes:

    void Array :: Resize(int newSize)
    {
        this->DeallocateMemory();
    
        this->AllocateMemoryOfSize(newSize);
        this->SetSize(newSize);
    }
    
  3. Don't set the size field independently of the allocation or deallocation of memory. You have calls to SetSize() in several places in your code: remove all except the ones in AllocateMemoryOfSize() and DeallocateMemory().

    In the context of your assignment operator, this becomes:

    void Array :: operator = (Array & arr)
    {
        int size = arr.GetSize();       
    
        this->Resize(size);
    
        for(int i=0 ; i<size ; i++)
        {
            this->SetItem(i, arr.GetItem(i));
        }
    }
    

Note that there are still other ways that this class could fail, for example if an exception is thrown during allocation. I recommend reading about exception guarantees: in a nutshell, do the memory allocation and copying of the other instance into temporary memory first, then if that succeeds, free up the resources in this instance and assign the temporary values to them. Scott Meyers covers it well in his book, Effective C++.


Speaking of the assignment operator, it's customary to have it return a reference to this:

Array &Array::operator= (Array & arr)
{
    // [rest of the assignment operator elided]
    return *this;
}

This will allow you to chain together assignments like:

Array a, b, c;
// ... stuff ...
a = b = c;
\$\endgroup\$
  • \$\begingroup\$ AllocateMemory() works in pair with DeallocateMemory(). Whenever the use needs to allocate some memory, he would first clean the previous memory using DeallocateMemory() and then call AllocateMemory(). If I equip AllocateMemory() with all the functionalities, there is actually no point having a DeallocateMemory(). Right? At best what we can do is to call DeallocateMemory() in the beginning of AllocateMemory(). To me that is redundant. What do you say? \$\endgroup\$ – user3804 Jun 28 '15 at 10:11
  • \$\begingroup\$ @BROY Updated my answer. \$\endgroup\$ – Niall C. Jun 28 '15 at 14:47
  • \$\begingroup\$ 1 generates memory access violation error. \$\endgroup\$ – user3804 Mar 24 '17 at 23:38
1
\$\begingroup\$

A couple of comments:

  1. I would add more comments to exactly specify what each of your functions does. For example, I would think that calling Resize would just copy existing elements over, but it deletes existing items.
  2. There is a bug with GetItem and SetItem - if I call with an index that is too large, then we will encounter an exception. You should change that function to say that it can throw an exception, or at least handle index better.
  3. You can also change SetItem, because it is a resizable array, to copy existing elements over, and reallocate the internal array to have a size equal to the input index, and then just set value there.
  4. You include <iostream> but have all uses of it commented out.
  5. Is #pragma region Private Methods for debugging purposes?
\$\endgroup\$
  • \$\begingroup\$ #pragma is for visual separation of code regions. \$\endgroup\$ – user3804 Jun 28 '15 at 9:33

Your Answer

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