Removing element from dynamic array

[qwerty123456]

// SimpleList.h

#ifndef SIMPLELIST_H
#define SIMPLELIST_H

#include "EmptyListException.h"
#include "FullListException.h"
#include "InvalidIndexException.h"

template <class T>
class SimpleList {
	public:
		SimpleList();
		~SimpleList();
		T at(int index) const throw (InvalidIndexException);
		bool empty() const;
		T first() const throw (EmptyListException);
		T last() const throw (EmptyListException);
		int getNumElements() const;
		void insert(T item) throw (FullListException);
		void remove(int index) throw (InvalidIndexException, EmptyListException);
		static const int CAPACITY = 10;
	private:
		int numElements;
		T* elements;
};

#endif 

//SimpleList.cpp


#include "SimpleList.h"
#include "EmptyListException.h"
#include "FullListException.h"
#include "InvalidIndexException.h"


template<class T>
SimpleList<T>::SimpleList(){

	elements = new T[CAPACITY];
        numElements = 0;
}

template<class T>
SimpleList<T>::~SimpleList(){

	delete [] elements;
}

template<class T>
T SimpleList<T>::at(int index) const throw (InvalidIndexException){

	if(index < 0 || index >=numElements){

        	// throw InvalidIndexException

                InvalidIndexException d;

                throw d;

        }
	else{

             	return elements[index];
	}
}
template<class T>
bool SimpleList<T>::empty() const{
	return(numElements==0);

}
template<class T>
T SimpleList<T>::first() const throw (EmptyListException){

        if(numElements == 0){
		// throw EmptyListException
		EmptyListException e;
		throw e;
	}
	else{
		return elements[0];
	}
}
template<class T>
T SimpleList<T>::last() const throw (EmptyListException){

	if(numElements == 0){

        	// throw EmptyListException

                EmptyListException e;
		throw e;

 	}
	else{
                return elements[numElements-1];
	}
}
template<class T>
int SimpleList<T>::getNumElements() const{

               return numElements;

}
template<class T>
void SimpleList<T>::insert(T item) throw (FullListException){

    	if(numElements == CAPACITY){
        	// throw FullListException
               	FullListException f;
                throw f;
      	}
	else{
         	elements[numElements] = item;
	 	numElements++;
     	}             
}
template<class T>
void SimpleList<T>::remove(int index) throw (InvalidIndexException, EmptyListException){

    	if(numElements == 0){
          	// throw EmptyListException
               	EmptyListException e;
              	throw e;

       	}
	else if(index < 0 || index >= numElements){
             	// throw InvalidIndexException
        	InvalidIndexException i;
                throw i;

       	}
		
	else{              
		for(int i=index+1;i<numElements;i++){
                       elements[i-1] = elements[i];
		}              
	}
}

I have an array that is on the heap and I'm having trouble implementing the remove() function at the very bottom, especially in the case where I want to remove the last element in the array.

[jonnin]

what does it mean to remove the last one?

it means to -- num elements!

which, you didn't do for any removals, by the way. Shouldn't all of them take 1 off num elements?

is memmove better for this?

Does the order matter? If not, can you swap removed to end and decrement num elements without all the slow copy mess?

[qwerty123456]

Unfortunately order does matter because the test cases first removes one element and then checks for the new first() and last() and numElements.

I'm not sure how to work with memmove

I tried this but nothing changed. Am I going in the right directions?

template<class T>
void SimpleList<T>::remove(int index) throw (InvalidIndexException, EmptyListException){

    	if(numElements == 0){
          	// throw EmptyListException
               	EmptyListException e;
              	throw e;

       	}
	else if(index < 0 || index >= numElements){
             	// throw InvalidIndexException
        	InvalidIndexException i;
                throw i;

       	}
		
	else if(index + 1 == numElements){    //if removing last element
		numElements = numElements -1;            
	}
	
	else{
		for(int i = index + 1; i < numElements; i++){
			elements[i-1] = elements[i];
		}
		numElements = numElements - 1;	              
	}
}

[jonnin]

the copy loop part sure looks right to me. what *exactly* is it not doing correctly now?
You may have a bug, shouldn't it be 0 to numelements, eg:
else if(index + 1 == maxarraysize-1){ //if removing last element
numElements--;
}

and I am unsure about that index + 1.

the element being removed is at index? If so, then if index == maxpossiblesize, its full, and you just pop the last one off via the decrement. If not, I am more confused than usual.

memmove isn't important if you don't understand it. It would effectively replace that loop:

memmove(&(elements[z], &(elements[z-1], sizeof(element)*(numelements-i));
//the above is close. I am not 100% sure about the number of items to be moved, but its 'how many to move' so its where you are currently from the total, right?

get it working as-is and you can play with memmove later.

its claim to fame is:

Copying takes place as if an intermediate buffer were used, allowing the destination and source to overlap.

[qwerty123456]

Oh I'm so dumb. I forgot to "make clean" in the terminal before running the tests again. It totally works now. Thank you very much for your help!

Just for clarification, the test creates a list of a random length like s = ["item1", "item2", "item3"] and here numElements= 3, so if the last element was to be removed, then index would be 2 since s[2] = "item3". So I did index + 1 == numElements to see if the item being removed was the last one.

[jonnin]

OK. I was just focused on the copy area where the problem was and only half reading the rest of it.

I really like arrays (vectors) as my go-to data structure for nearly everything.
What I usually do when I have this type of problem is add a deleted field to the items, and any iteration/searching/etc would ignore deleted items. Then you don't have to shuffle the data upon delete, you just mark it. (This would add an annoyance to your code, you would have to track true size and number of active items both). If the structure gets full (thinking vectors here, and it reaches the preallocated max size) then I will kill 2 aggravations with 1 routine by allocating a new vector that is bigger than the old one and then copying all the not-deleted items from the old into the new, recovering the space lost to deleted items AND increasing its size. This may be overkill for your project. If the lists get big and you delete often, data shuffle approach becomes a performance bottleneck (even with memmove).