Thread: Have a C++ project due soon and am not sure if I'm using pointers right.

I have a spot where I'm worried that, since a silly IDE glitch won't let it run properly, perhaps as I don't have a makefile or put it in wrong package or something (new IDE/compiler).

Out: 10th September 2011 Due: 19th September 2011 at 11:59pm
In this assignment you will write a class two versions of an adjusting array. The first version will work similar to the ArrayList class in Java (or vector class in C++), while the second one will make deletion more efficient.
Part 1: Adjusting Array
Write a class AdjustArray that represents an array of integers. Initially it has a size of 1. At any time, it can be partially full, so it keeps track of its current occupied size, as well as its true size. Add the following to this class:
1. A default constructor. It initializes the array to have all 0’s.
2. An overloaded [] operator as follows: int& operator [](unsigned int i). This returns a reference to the number at index ‘i’. Returning a reference is no different than returning the value at that position, C++ takes care of actually returning a reference to it. If ‘i’ is beyond the size of the array, so be it (the program will likely crash if this case is encountered at run-time).
3. A function “push_back(int m)” that will add ‘m’ to the end of the occupied part of the array. If the array is already full, it must first double the size of the array before adding this number. Double the array by creating a new array that is twice as big, copying all the elements of this array to the new one, and the making the new array as the “current” one. Be sure to free up any memory as necessary!
4. A function “erase(unsigned int i)”. This function deletes the number at position ‘i’ by shifting everything to its right by one position to the left. Note: the size of the occupied part of the array reduces by 1. If the array’s occupancy reduces to less than 50%, make the array half as big similar to how you expanded it.
Write a main function that tests this class in all possible ways (i.e. adding elements, deleting from the middle and either ends, allowing the array to expand and contract, etc.). The main function is worth points!
Part 2: Adjusting Array with Faster Deletion
The above array does not delete an element efficiently (because of all the shifting). Make it more efficient as follows (write a separate class, do not modify the above class).
1. Add an array “deletion” of booleans that maintains whether each position in the array of number is currently occupied, i.e. “deletion[i]= true” if number at index ‘i’ has been deleted, false otherwise.
2. Modify erase so that it simply changes the above array, but does not shift anything.
3. Add a variable that stores the smallest index that has been deleted.
4. Modify the [] operator above as follows:
a. If the index ‘i’ to be accessed is before the first deleted position, return reference directly.
b. Otherwise, remove all “empty” positions to the left of this index ‘i’ by shifting elements to the left. This will move the “true” number to this position and the smallest index that has been deleted will be greater than ‘i’. Now return the reference. (If the occupancy falls below 50%, contract as before)
Your main function does not change at all, and it should work as before.
Extra Credit (5 points): Do step 4(b) in Part 2 without using an extra array. Hint: During shifting, keep track of the position which must shift, and the position it must shift to.

I have these:

AdjustArray.h:

#ifndef _ADJUSTARRAY_H_
#define _ADJUSTARRAY_H_
 
class AdjustArray
{
 
public:
       AdjustArray();
       ~AdjustArray();
       void push_back(int m);
       void erase(unsigned int i);
       int& operator[](unsigned int i);
       void setSize(unsigned int size);
       unsigned int getSize() const;
       void setFilledSize(unsigned int filledSize);
       unsigned int getFilledSize() const;
       bool isFull() const;
 
 
       private: 
                unsigned int size;
                unsigned int filledSize;
                 int *array;
                };
 
       #endif

AdjjustArray.cpp (I misspelled Adjust but it's too late now to fix.):

#include <iostream>
 
using namespace std;
#include "AdjustArray.h"
 
 
AdjustArray::AdjustArray()
{
                          array = new int[1];
                          setSize(1);
                          setFilledSize(0);
int i;
for (i =0; i < getSize(); i++)
{
    array[i] = 0;
}
 
}
 
AdjustArray::~AdjustArray()
{
 
}
 
 int& AdjustArray::operator[](unsigned int i)
{
 
if (i >= getSize())
{
cout <<"Invalid!";
exit(1);
 
}
 
return array[i];
 
}
 
void AdjustArray::push_back(int m)
{
 
if(isFull() == true)
{
            int newArray[getSize() * 2];
            int k;
            for (k = 0; k < getSize(); k++)
            {
                newArray[k] = array[k];
 
                }
 
                newArray[getSize()] = m;
                array = newArray;
                setSize(getSize() *2);
              //  setFilledSize(getFilledSize() + 1);
 
 
            }
 
            // this should set index getFilledSize() to m
            else
            {
                array[getFilledSize()] = m;
 
                }
 
 
setFilledSize(getFilledSize() + 1);
 
 
}
 
void AdjustArray::erase(unsigned int i)
{
 
if (i >= getFilledSize())
{
      cout <<"Cannot delete out of bounds!";
     return;
      }
 
 
           int x;
          for (x = i; x < getFilledSize(); x++)
          {
              int temp = array[x+1];
              array[x] = temp;
 
              }
 
 
              setFilledSize(getFilledSize() -1);
 
 
 
 
}
 
void AdjustArray::setSize(unsigned int size)
{
this -> size = size;
}
 
unsigned int AdjustArray::getSize() const
{
return size;
}
 
void AdjustArray::setFilledSize(unsigned int filledSize)
{
this -> filledSize = filledSize;
}
 
unsigned int AdjustArray::getFilledSize() const
{
return filledSize;
}
 
bool AdjustArray::isFull()const
{
        if (getFilledSize() == getSize())
        return true;
        return false;
 
        }
 
 
int main()
{
    return 0;
}

BetterAdjustArray.h:

#ifndef _BETTERADJUSTARRAY_H_
#define _BETTERADJUSTARRAY_H_
 
class BetterAdjustArray
{
public:
BetterAdjustArray();
~BetterAdjustArray();
int& operator[] (unsigned int i);
unsigned int getSmallestIndexDeleted() const;
void setSmallestIndexDeleted(unsigned int index);
void erase (unsigned int i);
 
private:
*bool boolArray;
unsigned int index;
// more stuff 
 
 
};
 
 
#endif

BetterAdjustArray.cpp:

 
#include "BetterAdjustArray.h"
#include <iostream>
using namespace std;
 
 
BetterAdjustArray()::BetterAdjustArray()
{
 
 
}
 
BetterAdjustArray::~BetterAdjustArray()
{
 
}
 
void BetterAdjustArray::setSmallestIndexDeleted(unsigned int index)
{
this -> index = index;
}
 
unsigned int BetterAdjustArray::getSmallestIndexDeleted() const
{
return index;
}
 
int& BetterAdjustArray:: operator[] (unsigned int i)
{
 
}
 
void BetterAdjustArray::erase(unsigned int i)
{
 
 
}
 
int main()
{
return 0;
}

When I was trying to double the size of the array, was I setting the pointer to a temporary variable that will be lost when the method or whatever ends, this making array point to nothing or am I worried about nothing?

Also, how could you change erase to modify the array without shifting?

C++ does not allow for dynamically sized arrays on the stack, you must allocate the array on the heap (a.k.a. using "new"), then you will need to delete it when you're done. Even assuming that you could have dynamically sized arrays you would still need to allocate the array on the heap because as soon as push_back() returned the stack will be reclaimed, along with the array and the pointer in your class will point to an invalid memory location.

You can't erase an element from the array without shifting.

Yes, in push_back:

int newArray[getSize() * 2];

If this was legal (it isn't because C++ doesn't allow dynamic sized arrays on the stack), the actual array would go out of scope and be reclaimed after push_back returned.

You're constructor has the correct syntax for using the new operator.

One thing is that you will need to manually delete the old referenced array in push_back, as well as in the destructor when the whole object is being reclaimed. Note: you only need to delete items allocated on the heap. Items allocated on the stack are automatically reclaimed when they go out of scope.

delete[] array; // frees the memory pointed to by array

What's the difference between heap and stack?

int* newArray;
newArray = new int[getSize() * 2];

Is that right?

For the creation of the array, yes. You still need to manage memory cleanup or you'll be left with memory leaks.

memory management - What and where are the stack and heap - Stack Overflow

Which chunk of memory do you want to keep, the one pointed to by array, or the one pointed to by newArray (note: this is before they both point to the same array)?

What do I delete?

delete[] newArray is causing weird things to happen.

Where should I put delete[] array or whatever I need?

Ok, delete[] array isn't working either.

What's the problem?

void AdjustArray::push_back(int m)
{
 
if(isFull() == true)
{
  int* newArray;
            newArray = new int[getSize() * 2];
            int k;
            for (k = 0; k < getSize(); k++)
            {
                newArray[k] = array[k];
 
                }
 
                newArray[getSize()] = m;
                delete[] array;
                array = newArray;
 
                setSize(getSize() *2);
              //  setFilledSize(getFilledSize() + 1);
 
 
            }
 
            // this should set index getFilledSize() to m
            else
            {
                array[getFilledSize()] = m;
 
                }
 
 
setFilledSize(getFilledSize() + 1);
 
 
}
 
void AdjustArray::erase(unsigned int i)
{
 
if (i >= getFilledSize())
{
      cout <<"Cannot delete out of bounds!";
     return;
      }
 
 
           int x;
          for (x = i; x < getFilledSize(); x++)
          {
              int temp = array[x+1];
              array[x] = temp;
 
              }
 
 
              setFilledSize(getFilledSize() -1);
 
	      if (getFilledSize() < static_cast<int>(getSize()/2))
		{
 
		  int *newArray;
                  newArray = new int[static_cast<int>(getSize()/2)];
                  int v;
                  setFilledSize(static_cast<int>(getSize() /2));
		  for (v= 0; v < getFilledSize(); v++)
		    {
		      newArray[v] = array[v];
		    }
delete[] array;
		  array = newArray;
 
		  setSize(getFilledSize());
 
		}
 
 
 
}

------Edit--------
I edited it above. I think this is what they wanted.

Now I need help on Part 2.

I've almost got it now, but I can't figure out some segmentation error that I'm thinking is being created, likely by an indexing error I can't see for some reason, inside the overloaded [] operator method, though there's a very small chance the error could be elsewhere.

Ignore the part about AdjustArray. That can be removed for testing.

BetterAdjustArray.cpp:

#include "BetterAdjustArray.h"
#include "AdjustArray.h"
#include <iostream>
using namespace std;
 
 
BetterAdjustArray::BetterAdjustArray()
{
  array = new int[1];
  int x;
  for ( x = 0; x < 1; x++)
    {
      array[x] = 0;
    }
  setFilledSize(0);
  setSize(1);
  boolArray = new bool[1];
 
  int y;
  for (y = 0; y < 1; y++)
    {
      boolArray[x] = true;
    }
 
}
 
BetterAdjustArray::~BetterAdjustArray()
{
 delete[] boolArray;
 delete[] array;
 cout <<"BetterAdjustArray destructor called.\n";
}
 
void BetterAdjustArray::setSmallestIndexDeleted(unsigned int index)
{
this -> index = index;
}
 
unsigned int BetterAdjustArray::getSmallestIndexDeleted() const
{
return index;
}
 
int& BetterAdjustArray:: operator[] (unsigned int i)
{
 
  if (i < getSmallestIndexDeleted())
    {
      return array[i];
    }
 
  else
    {
while (getSmallestIndexDeleted() < i)
{
 
for (int x = getSmallestIndexDeleted(); x < (getFilledSize() -1); x++)
{
int temp = array[x+1];
array[x] = temp;
 
}
  setFilledSize(getFilledSize() -1);
 boolArray[getSmallestIndexDeleted()] = false;
for (int v = getSmallestIndexDeleted()+1; v < getFilledSize(); v++)
{
if (boolArray[v] == true)
{
setSmallestIndexDeleted(v);
 cout<<"Smallest index deleted now is:" <<v <<"\n";
break;
 
}
 
}
 
 
 
}
 
 if (getFilledSize() < static_cast<int>(getSize()/2))
		{
 
		  int *newArray;
                  bool *newBoolArray;
                  newArray = new int[static_cast<int>(getSize()/2)];
                  newBoolArray = new bool[static_cast<int>(getSize()/2)];
                  int p;
		  // setFilledSize(static_cast<int>(getSize() /2));
		  for (p= 0; p < getFilledSize(); p++)
		    {
		      newArray[p] = array[p];
                      newBoolArray[p] = boolArray[p];
 
		    }
 
			 for (int w = getFilledSize(); w < static_cast<int>(getSize()/2); w++)
			   {
                             newArray[w] = 0;
                             newBoolArray[w] = true;
			   }
                  delete[] array;
		  array = newArray;
                 delete[] boolArray;
                 boolArray = newBoolArray;
 
		       setSize(static_cast<int>(getSize()/2));
 
		}
return array[i];
 
 
    }
 
 
}
 
void BetterAdjustArray::erase(unsigned int i)
{
  if (i >= getFilledSize())
    {
      cout<<"No can do. \n";
      return;
    }
 
 
 
  boolArray[i] = true;
  if (i < getSmallestIndexDeleted())
    setSmallestIndexDeleted(i);
 
 
 
}
 
 
void BetterAdjustArray::setSize(unsigned int size)
{
  this->size = size;
}
 
unsigned int BetterAdjustArray::getSize() const
{
  return size;
}
 
void BetterAdjustArray::setFilledSize(unsigned int filledSize)
{
  this->filledSize = filledSize;
}
 
unsigned int BetterAdjustArray::getFilledSize() const
{
  return filledSize;
}
 
void BetterAdjustArray::push_back(int m)
{
 
  if (isFull() == true)
    {
      int *newArray;
      bool *newBoolArray;
 
     //had forgotten to instantiate those two
     newArray = new int[getSize() * 2];
     newBoolArray = new bool[getSize() * 2];
         int k;
            for (k = 0; k < getSize(); k++)
            {
                newArray[k] = array[k];
                newBoolArray[k] = boolArray[k];
 
                }
 
	    for (int v = getSize(); v < (getSize() * 2); v++)
	      {
 
		newArray[v] = 0;
		newBoolArray[v] = true;
	      }
                newArray[getSize()] = m;
                newBoolArray[getSize()] = false;
                delete[] array;
                delete[] boolArray;
                array = newArray;
                boolArray = newBoolArray;
		setSize(getSize() * 2);
 
    }
 
  else
    {
  array[getFilledSize()] = m;
  boolArray[getFilledSize()] = false;
    }
 
 
  setFilledSize(getFilledSize() + 1);
 
 
}
 
bool BetterAdjustArray::isFull() const
{
  if (getFilledSize() == getSize())
    return true;
  return false;
}
 
void BetterAdjustArray::printArray() const
{
 cout <<"[";
  for (int m =0; m < (getFilledSize()-1) ; m++)
    {
      cout << array[m] << ",";
    }
 
  cout <<array[getFilledSize() -1];
  cout <<"] \n";
 
 
}
int main()
{
  AdjustArray arr;
  arr.push_back(222);
  arr.erase(0);
  cout <<arr[0];
  arr.push_back(11);
  cout <<arr[0] << "\n";
  arr.push_back(45);
  cout<< arr[0] << "," << arr[1] << "\n";
  arr.push_back(15);
  arr.push_back(99);
  arr.push_back(1111);
  arr.erase(2);
  arr.printArray();
 
  BetterAdjustArray barr;
  barr.push_back(91);
  barr.push_back(33);
  barr.push_back(45);
  barr.push_back(999);
  barr.push_back(15);
  barr.push_back(121);
  barr.push_back(555);
  barr.push_back(777);
  barr.push_back(888);
  barr.push_back(10000);
  barr.erase(2);
  barr.erase(5);
  barr.erase(7);
  cout <<barr[8] << "\n";
  barr.printArray();
  barr.push_back(19);
  barr.printArray();
 
}

It's saying

"Segmentation error after printing out all the AdjustArray stuff, so no problems with AdjustArray.

The problem could also be in push_back, though I'm thinking it's maybe my break statement in the overloaded [] method or an indexing error.

Please help. This is almost done and due in about exactly 2 hours! It's nearly done but I need help or I might not be able to finish it all the way in time!

Another thought would be because maybe I was supposed to set SmallestIndexDeleted() to 0 right away, but I don't think so.


Thanks.

-----Edit----
Found part of error, but still getting message.
Had forgotten to initialize some stuff. But it's still giving me the error, just in a different place.

Now it's printing:

 

[91,33,45,999,15,121,555,777,888,10000] 

Smallest index deleted now is:5

Smallest index deleted now is:7

Segmentation fault

I was trying to set smallestIndexDeleted to be bigger than i.

Maybe I should have not tried that in the for loop. Let me see if changing that makes a difference....

Better but still not working quite as expected:

[91,33,45,999,15,121,555,777,888,10000]
Smallest index deleted now is:5
Smallest index deleted now is:7

Why isn't it adding 19 to the end and instead ending the program?