Remove an element from a dynamic array

Question

for one of my assignments I have to create a class that creates a dynamic array and has methods to add or remove a number from the array, I figured out how to do the add method and it works fine but I cannot figure out how to remove an element and make the size of the array decrease by one.

#include <iostream>
using namespace std;

class IntegerDynamicArray
{
    public:
        IntegerDynamicArray()
        {
            currentSize = 0;
            maxSize = 10;
            dynamicArray = new int[maxSize];
        }

        int add(int x);
        bool remove(int x);
    private:
        int* dynamicArray;
        int currentSize;
        int maxSize;
};

int IntegerDynamicArray::add(int x)
{
    if (currentSize == maxSize)
    {
        maxSize = maxSize * 2;
        int* tempArray = new int[maxSize];
        for (int i = 0; i < currentSize; i++)
        {
            tempArray[i] = dynamicArray[i];
        }
        tempArray[currentSize] = x;
        currentSize++;
        dynamicArray = tempArray;
    }
    else
    {
        dynamicArray[currentSize] = x;
        currentSize++;
    }
    return currentSize;
}

bool IntegerDynamicArray::remove(int x)
{
    for (int i = 0; i < currentSize; i++)
    {
        if (dynamicArray[i] == x)
        {
            //TODO need to delete the number and move all numbers "back" by one
            return true;
        }
    }
    return false;
}

int main()
{
    IntegerDynamicArray intDynArray;
    while (1)
    {
        char input;
        cout << "Enter A for add or R for remove: ";
        cin >> input;
        if (input == 'A')
        {
            cout << "Enter number to add: ";
            int x;
            cin >> x;
            cout << intDynArray.add(x) << endl;
        }
        else if (input == 'R')
        {
            cout << "Enter number to remove: ";
            int x;
            cin >> x;
            cout << intDynArray.remove(x) << endl;
        }
    }
}

Solution 1

The add function leaks memory because you did not deallocate dynamicArray before assigning it to the new block of memory. You should also provide a destructor. Use delete[] rather than delete since you are allocating an array. The conditional within remove does not appear to be correct. I would think that x indicates the element to remove, but you are searching for an element with value == x. I would think that you would first validate that x is a valid index (less than current size), and then use x to loop from that element to the end copying all of the elements forward. Then zero initialize between currentSize and max size. That would be one way to do it. This look like homework, so I will only provide guidance and not the code. Try it. Based on what you wrote so far, I think that you can figure that out.

Update: It is true that if you add a destructor that handling copy construction and assignment (somehow) is critical.

If you really want to remove occurrences of a value rather than the element, then I suggest you do it similarly to how the remove algorithm does it. Essentially you would start at the beginning, loop and copy forward over the matched values. Since you aren't dealing with iterators you'd have to get creative and adjust your current size but the example there on cplusplus.com should be invaluable in helping you write your function. Although technically you don't have to zero initialize those "removed" slots, I think that it is a good idea so that you don't get confused while debugging. Stale data in those unused slots doesn't help but it could get confusing while looking at the data in a debugger.

Solution 2

If you want to remove the first occurrence only you can do something like that. I didn't test the code but it should be fine.

bool IntegerDynamicArray::remove(int x)
{
    for (int i = 0; i < currentSize; i++)
    {
        if (dynamicArray[i] == x)
        {   
            for ( ; i < currentSize - 1; i++) 
            {
                // Assign the next element to current location.             
                dynamicArray[i] = dynamicArray[i + 1];                  
            }

            // Remove the last element as it has been moved to previous index.
            dynamicArray[currentSize - 1] = 0;
            currentSize = currentSize - 1;

            return true;
        } 
    }
    return false;
}

You can also write a function that removes all occurrences of the value or as @shawn1874 suggested you can remove the item with the given index.

Solution 3

This ought to do it:

bool IntegerDynamicArray::remove(int x)
{
    for (int i = 0; i < currentSize; i++)
    {
        if (dynamicArray[i] == x)
        {
            int *newArray = new int[currentSize-1];
            std::copy(dynamicArray, dynamicArray+i, newArray);
            std::copy(dynamicArray+i+1, dynamicArray+currentSize, newArray+i);
            delete[] dynamicArray;
            dynamicArray = newArray;
            --currentSize;
            return true; 
        }
    }       
    return false;
}

Comments

[Birkan Cilingir]

+1 for pointing out memory leaks and requirement for a destructor.

[Mooing Duck]

forgot copy constructor and copy assignment, and I don't think the conditional in the remove is wrong, I think it's merely a weird design. Also, zero initialization is unnecessary.