Dynamic Memory

[mikeCC]

Hello,

I had an assignment for school that asked me to write the implementation file for a dynamic sequence class. The assignment came with a test file that lets you know how much of the implementation file you wrote correctly by running several tests.

Every test checked out except for the one which tests the resize function. The test fails at the point where the array is filled, and expected not to automatically resize because the capacity is sufficient. I'm having trouble figuring out where I went wrong, I tried messing around with the capacity but the array still seems to need to resize even though it shouldn't.

Here is the part of the test code that checks the function, as well as the two functions I implemented which are accessed by this test; resize() and attach(), I would appreciate any help:

// 

	void sequence:: attach(const value_type& entry)
	//library used: algorithm
	{
		
			if(used==capacity)
			{
				resize(used+1);
			}
			
			{

		if(!is_item())
		{
			
			value_type* new_array;
			new_array=new value_type[capacity];					
			copy(data, data+used, new_array);	// adds the elements of the original array into the new array
			new_array[used]=entry;				//insertss the entry at the beginning of the new array
			delete[] data;
			data=new_array;
			current_index=used;
			used++;
			
		}
		else 
		{
			value_type* new_array;
			new_array=new value_type[capacity];
			copy(data, data+ current_index+1, new_array);	// adds the elements of the original array up to the point where the new entry comes in into the new array
			new_array[current_index+1]=entry;					//insertss the entry at the current index of the new array
			copy(data+current_index+1, data + used, new_array+ current_index+ 2);	// adds the elements of the original array from the current index up until into the new array
			delete[] data;
			current_index+=1;
			data=new_array;
			used++;
		}
			}
	}



	void sequence:: resize(size_type new_capacity)
	// library facilities used: algorithm
	{

		value_type *larger_array;

		if(new_capacity== capacity)
		{
			return; //the array is already the right size
		}
		if (new_capacity<used)
		{
			new_capacity=used;// can't allocate less than we are using
		}

		larger_array= new value_type [new_capacity];
		copy(data, data+used, larger_array);
		delete[] data;
		data= larger_array;
		capacity= new_capacity;
	}





**************************************************************************
// int test4( )
//   Performs some tests of resize.
//   Returns POINTS[4] if the tests are passed. Otherwise returns 0.
// **************************************************************************
int test4( )
{
    sequence test;
    size_t i;
    char bytes[sizeof(sequence)];
    char newbytes[sizeof(sequence)];
    size_t mismatches;

    cout << "I will now resize a sequence to a larger capacity, and then\n";
    cout << "attach that many items. The sequence should NOT need to\n";
    cout << "resize itself under this situation." << endl;
    test.resize(2*test.DEFAULT_CAPACITY);
    test.attach(0);
    memcpy(bytes, (char *) &test, sizeof(sequence));
   
    // At this point, I should be able to insert 2*DEFAULT_CAPACITY-1
    // more items without calling resize again. Therefore, at most 1 byte
    // of the object will change (the least significant byte of used).

    for (i = 1; i < 2*test.DEFAULT_CAPACITY; i++)
        test.attach(i);
    test.start( );
    memcpy(newbytes, (char *) &test, sizeof(sequence));
     
    for (i = 0; i < 2*test.DEFAULT_CAPACITY; i++)
    {
        if (test.current( ) != i)
        {
            cout << "    sequence does not contain correct items." << endl;
            return 0;
        }
        test.advance( );
    }
    test.start( );
     
    mismatches = 0;
    for (i = 0; i < sizeof(sequence); i++)
        if (bytes[i] != newbytes[i])
            mismatches++;
    if (mismatches > 1)
    {
        cout << "    sequence was resized when it should not be." << endl;
        return 0;
    }
    else
        cout << "    Test passed." << endl;
     
    cout << "Now I will call resize(1) for the sequence, but the actual\n";
    cout << "sequence should not change because the sequence already has \n";
    cout << test.DEFAULT_CAPACITY*2 << " items." << endl;
    memcpy(bytes, (char *) &test, sizeof(sequence));
    test.resize(1);
    mismatches = 0;
    for (i = 0; i < sizeof(sequence); i++)
        if (bytes[i] != newbytes[i])
            mismatches++;
    if (mismatches > 0)
    {
        cout << "    sequence was resized when it should not be." << endl;
        return 0;
    }
    else
        cout << "    Test passed." << endl;

    // All tests passed
    cout << "All tests of this fourth function have been passed." << endl;    
    return POINTS[4];
}

[ne555]

memcpy(bytes, (char *) &test, sizeof(sequence)); ¿what do you think that you are doing?

[mikeCC]

That's not part of my code, that is part of the test code.

The test code begins after line 70. This is code that we were given to test our implementation. I didn't write anything after line 70, maybe the test code has some error but I have a hard time understanding all of it.

Sorry if it was unclear.

[ne555]

			value_type* new_array;
			new_array=new value_type[capacity];  //¿why creating a new one?
			copy(data, data+used, new_array);	
			new_array[used]=entry;
			delete[] data;
			data=new_array;
			current_index=used;
			used++;

attach in any case will allocate another chunk of memory.
The test checks whether the all data in the object is the same. As you are changing the pointer, it will not pass.
Actually I don't like the test, as used, current_index, and other members are counted too. And the pointer may go back to what it was.

If your array has the capacity to hold another element, just put it in

if( size<capacity ){
  //move the others if you need to
  data[ index ] = value; //insert the element
  //adjust size
  //...
}

[mikeCC]

Thanks for getting back to me.

The part of your explanation that I"m not understanding is when you say that attach would allocate memory in any case. So in that sense if the dynamic array that my iterator is moving through has an initial set capacity of 30 and currently holds 5 items, then adding another item would still require allocating new memory?

I thought that once you set the size you allocate enough memory for that set amount of inputs to be held by the array and the only purpose of the resize function is if you exceed that capacity.

In my class, the default constructor sets the capacity as a static constant whose value is 30.

Let me know if I'm misunderstanding something.

[ne555]

I thought that once you set the size you allocate enough memory for that set amount of inputs to be held by the array and the only purpose of the resize function is if you exceed that capacity.

That is how is supposed to work.
What I'm saying is that you made a mistake in the attach() method.
Without considering the size, you are doing this

//allocate memory (the same capacity)
//copy the used elements to the new allocation
//deallocate
//update the pointer 

and that's why is failing the test.
(all paths have new_array = new value_type[ something ];

[mikeCC]

I understand what you mean now.

Thanks for the help.