Increasing the size of an already dynamically allocated array (check please)

[bmos31]

I think I'm there, but I'm not sure if the insert() is correctly doubling the dynamically allocated memory. In an attempt in my insert() I tried to:
1 double the allocated memory (not sure if that was accomplished)
2 copy original values to the newArray
3 free original space
4 reassign pointer to original

The only thing I had to do with this program was to modify the insert() function to double the dynamic memory, which hopefully I did correctly, but I'm not sure. The rest of the program shouldn't need any modifications. Any tips would be great...Thanks!

P.S. please ignore cout statements in my member functions, I just used them to keep track of where I was at

#include <iostream>
#include <cassert>
#include <new>
using namespace std;
typedef int ElementType;

class List
{
 public:
   List(int maxSize = 1024);
   ~List();
   List(const List & origList);
   const List & operator=(const List & rightHandSide);
   bool empty() const;
   void insert(ElementType item, int pos);
   void erase(int pos);
   void display(ostream & out) const;
  
 private:
   int mySize;                // current size of list
   int myCapacity;            // capacity of array
   ElementType * myArray;     // pointer to dynamic array

};
ostream & operator<< (ostream & out, const List & aList);

//--- Definition of class constructor
List::List(int maxSize)
: mySize(0), myCapacity(maxSize)
{
   myArray = new(nothrow) ElementType[maxSize];
   assert(myArray != 0);
   cout << "CONSTRUCTOR\n";
}

//--- Definition of class destructor
List::~List()
{
    cout << "DESTRUCTOR\n";
    delete [] myArray;
}

//--- Definition of copy constructor
List::List(const List & origList)
: mySize(origList.mySize), myCapacity(origList.myCapacity)
{
  //--- Get new array for copy
   myArray = new(nothrow) ElementType[myCapacity];

   if (myArray != 0)                 // check if memory available
      //--- Copy origList's elements into this new array
      for(int i = 0; i < mySize; i++)
         myArray[i] = origList.myArray[i];
   else
   {
      cerr << "*** Inadequate memory to allocate storage for list ***\n";
      exit(1);
   }
   cout << "COPY CONSTRUCTOR\n";
}

//--- Definition of assignment operator
const List & List::operator=(const List & rightHandSide)
{
   if (this != &rightHandSide)  // check that not self-assignment
   {
      //-- Allocate a new array if necessary
      if (myCapacity != rightHandSide.myCapacity) 
      {
         delete[] myArray;
         myCapacity = rightHandSide.myCapacity;
         myArray = new(nothrow) ElementType[myCapacity];

         if (myArray == 0)      // check if memory available
         {
            cerr << "*Inadequate memory to allocate stack ***\n";
            exit(1);
         }
      }
      //--- Copy rightHandSide's list elements into this new array
      mySize = rightHandSide.mySize;
      for(int i = 0; i < mySize; i++)
         myArray[i] = rightHandSide.myArray[i];
   }
   return *this;
}

//--- Definition of empty()
bool List::empty() const
{
   return mySize == 0;
}

//--- Definition of display()
void List::display(ostream & out) const
{
   for (int i = 0; i < mySize; i++)
     out << myArray[i] << "  ";
}

//--- Definition of output operator
ostream & operator<< (ostream & out, const List & aList)
{
   aList.display(out);
   return out;
}
void List::insert(ElementType item, int pos)
{
   if (mySize == myCapacity)
   {
        cout << "im here at INSERT" << endl;
        ElementType * newArray;
        
        newArray = new(nothrow) ElementType[myCapacity * 2];
            for(int i = 0; i < myCapacity; i++)
            newArray[i] = myArray[i];
            myCapacity *= 2;
            
            delete [] myArray;
            myArray = newArray;
   }
   if (pos < 0 || pos > mySize)
   {
        cout << "INSERT" << endl;
      cerr << "*** Illegal location to insert -- " << pos 
           << ".  List unchanged. ***\n";
      return;
   }

    // First shift array elements right to make room for item

    cout << "INSERT" << endl;
    for(int i = mySize; i > pos; i--)
      myArray[i] = myArray[i - 1];

    // Now insert item at position pos and increase list size  
    myArray[pos] = item;
    mySize++;
}


//--- Definition of erase()
void List::erase(int pos)
{
   if (mySize == 0)
   {
      cerr << "*** List is empty ***\n";
      return;
   }
  if (pos < 0 || pos >= mySize)
   {
      cerr << "Illegal location to delete -- " << pos
           << ".  List unchanged. ***\n";
      return;
   }

   // Shift array elements left to close the gap
   for(int i = pos; i < mySize; i++)
       myArray[i] = myArray[i + 1];

   // Decrease list size
    mySize--;
}


int main()
{
    int listLimit;
    cout << "Enter max number of list elements: ";
    cin >> listLimit;
    
    List list1(listLimit);
    
    for(int i = 0, n = 0; i < listLimit; i++, n++)
    {
        list1.insert(n,i);
    }
    cout << "number of elements: " << listLimit << endl;
    cout << "elements: " << list1 << "\n\n";
    
    int extra;
    cout << "Enter a(n) extra element(s) and I will double the dynamic array size: ";
    cin >> extra;
    //GOOD TO HERE
    list1.insert(10000,listLimit);
    list1.insert(400, listLimit);
    cout << "List1 " << list1 << endl;
    
    system("pause");
    return 0;
}

[StuXYZ]

Well first off, this is good. Insert functions correctly, i.e. does indeed double the memory. It also copies (as far as I have tested) and sorts everything out.

However, there is a subtle bug in erase that may hurt. You can get a memory violation.
In your shift of moving elements down from the higher part of the array:

for(int i=pos;i<mySize;i++)
  myArray[i]=myArray[i+1];

However, you are going to access memory that is outside of the allocated memory, e.g. i+1 == mySize. That is very unlikely to cause problems with a simple type like int, but for something like a real class that is going to cause problems.

So change the code to

for(int i=pos+1;i<mySize;i++)
  myArray[i-1]=myArray[i];

Why does operator= return a const List& surely you don't want a const return type ?

insert should be void insert(const elementType&,const int); , consider if elementType is an expensive to copy object.

You have no check for maxSize==0 or maxSize<0 (since you are using an int not a unsigned int.)

Give that you are dealing with List etc, that is part of the std namespace, would it be better not to use "using namespace std;" and instead use the using std;:cout; etc or just put std::cout in your code ?

Finally, you understand that there are several improvements that are possible. (a) it is insert and copy in the loop, so to improve the situation when you resize. (b) allow the memory block that is active to be in the middle of the allocated array. [this on average talks 1/3 off insert time, (random insert).] -- you use a start/end position and then shift the block up/down when it hits the beginning / end ( or as is more common to wrap it round).

[bmos31]

great, thank for the suggestions, they're very helpful!