0

So my code is suppose to insert numbers into a dynamic array, add more capacity to the array if more is needed, remove numbers from the array and then make sure the only NULLS occur at the end of the array. It also tells the user how many numbers are in the array and what is the total size of the array. My problem is when I remove a number from the array, it sometimes prints out there is a number -33686019 in my array. This doesn't occur much, but I don't want it to occur at all.

#include <stdio.h>
#include <iostream>

int* gArray = NULL;
int gSize = 0;
int gCapacity = 0;
void Insert(int value);
void Remove(int value);
void Resize(int newCapacity);
void Print(void);


void main()
{
int input = 0;

while(input != 3)
{
    printf(">=== Dynamic Array ===\n");
    printf("What do you want to do?\n");
    printf("1. Insert\n");
    printf("2. Remove\n");
    printf("3. Quit\n");
    printf("Your choice: ");
    scanf_s("%d", &input);
    printf("\n\n");

    int value = 0;

    switch(input)
    {
    case 1:
        {
            printf("Enter a number: ");
            scanf_s("%d", &value);
            Insert(value);
            Print();
            break;
        }
    case 2:
        {
            printf("Enter number you wish to delete: ");
            scanf_s("%d", &value);
            Remove(value);
            Print();
            break;
        }
    case 3:
        {
            break;
        }
    default:
        {
            printf("Invalid selection\n");
        }
    }
}
}
void Insert(int value)
{
bool valueSet = false;

while(valueSet == false)
{
    if(gArray == NULL)
    {
        Resize(1);
        gArray[gSize] = value;
        ++gSize;
        valueSet = true;
    }
    else if(gArray[gCapacity] == NULL)
    {
        gArray[gSize] = value;
        ++gSize;
        valueSet = true;
    }
    else if(gArray[gCapacity] != NULL)
    {
        Resize((gCapacity + 1));
        gArray[gSize] = value;
        ++gSize;
        valueSet = true;
    }
}

}
void Resize(int newCapacity)
{
int* tempArray = new int[newCapacity];
std::copy(gArray, gArray+(newCapacity-1), tempArray);
gArray = new int[newCapacity];
std::copy (tempArray, tempArray+(newCapacity-1), gArray);
gCapacity = newCapacity;
}
void Remove(int value)
{
for(int i = 0; i < gCapacity; ++i)
{
    if(gArray[i] == value)
    {
        gArray[i] = NULL;
        --gSize;
    }
}
for(int i = 0; i < gCapacity; ++i)
{
    if(gArray[i] == NULL)
    {
        gArray[i] = gArray[(i + 1)];
        gArray[(i + 1)] = NULL;
    }
}
}
void Print(void)
{
printf("Array contains: ");
for(int i = 0; i < gCapacity; ++i)
{
    if(gArray[i] != NULL)
    {
        printf("%d, ", gArray[i]);
    }
}
printf("size = %d, capacity = %d\n", gSize, gCapacity);


}
5
  • 2
    Is this an assignment? std::vector is designed for this. Commented Aug 4, 2012 at 17:57
  • First of all, the concept of NULL is only suited to pointers. There is no such thing as a null int, and what you are doing is (probably) setting ints to 0. Second, is this an assignment or exercise, and is so, are you not allowed to use the C++ standard library? Commented Aug 4, 2012 at 17:59
  • 1
    Since this is c++: Whats with the manual memory management? std::vector would do a better job. Commented Aug 4, 2012 at 18:00
  • @juanchopanza std::copy is also a part of the standard library... Commented Aug 4, 2012 at 18:03
  • @IgorR. Thanks, I missed that. It was too far down. Presumably all the code could be replaced with a standard library container and an algorithm or two, which is why I was asking. Commented Aug 4, 2012 at 18:06

3 Answers 3

2

An option, since you are using the c++ standard library would be to remove all your code, and use std::list and its insert and remove methods. If you require the data to be in a dynamic array, then use std::vector and the erase remove idiom for removal.

I have to point out that, since your question is "Removing int value in dynamic array and setting it to NULL", that setting an int to NULL is essentially setting it to the value 0, since NULL tends to be a define for 0. So if your list were to contain zeroes, this setting to NULL and checking for equality with NULL would completely break the logic of your algorithm. C++11 has nullptr, an actual null type that cannot be assigned to an int, to deal with this kind of problem.

Sign up to request clarification or add additional context in comments.

Comments

1

The concrete problem is that you don't initialize the new array (resp. tempArray) in your Resize function.

When calling

int* tempArray = new int[newCapacity];

the array can contain arbitrary values. Only newCapacity-1 values are copied from the old array, so the last value is undefined. It might be 0 but haven't to be. Use

std::fill(tempArray, tempArray+newCapacity, 0);

to initialize your array with zero.

Apart from that, there are a few other problems:

  • You don't delete the old array before allocating a new one. Use delete[] gArray for that. Also tempArrayisn't deleted!
  • You don't need to copy the values twice. Just to a gArray = tempArray (after deleting the old gArray, see above)
  • You assume that newCapacity is just larger by one than gCapacity (you copy newCapacity-1 values from the old array). It would be better to copy gCapacity values instead.
  • Dynamic arrays which only grow by one are inefficient, since adding a value takes linear time (you have to copy all the old values when inserting a single one). Usually, you double the size of the array every time you run out of space, this gives constant insertion time in average.
  • NULL is normally used only for pointers. For ints it is equal to zero which means, you cannot store 0 in your array (given your requirements)
  • In production code, I'd strongly recommend using std::vector instead of any home-grown solution.

EDIT

See @StackUnderflows answer for what is probably the real cause of the error. If you run in Debug mode, some compilers will automatically initialize the array for you, which might be the ccase here.

The gArray[i]=gArray[i+1] line in your Remove function is definitely wrong on the other hand, since it accesses a value which is beyond the limits of the array.

Comments

1

The problem occurs on the last iteration in the second loop of Remove when you do gArray[i] = gArray[i + 1]. On the last iteration, gArray[i + 1] is actually one past the end of your array, so you are now in undefined behavior territory. You are assigning this undefined value to the last element gArray[i].


I suggest using std::vector<int> instead. It manipulates an array under the hood which grows/resizes for you as you add more elements.

1 Comment

I missed this one, which is most probably the real cause. There were just so many other oddities in the code ...

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.