C++ Reorganizing an array to fill in the gaps?

Question

I'm not sure if the word Reorganizing is the correct term, but its the only way I can describe what I'm looking for.

If I have an array of say, Cats, like so:

CAT *myCats[99];

myCats[0] = new CAT;
myCats[1] = new CAT;
myCats[2] = new CAT;
myCats[3] = new CAT;
myCats[4] = new CAT;
myCats[5] = new CAT;

At one point in time, lets say myCats[3] gets deleted:

delete myCats[3];

now I have the following:

myCats[0]
myCats[1]
myCats[2]
myCats[4]
myCats[5]

Is there an easy way to reorganize the array so that it moves 4->3 and 5->4, essentially filling in the gaps?

myCats[0]
myCats[1]
myCats[2]
myCats[3]
myCats[4]

Is the best way to accomplish this, to essentially iterate through the array and determining that if a element is empty/missing, I just need to move the next existing element into its place? How would I do this? How would I determine if the Cat element at any point in the array exists? Or is there a more simple pre-determined method for accomplishing what I need?

Sorry if the example and syntax is a little off. I'm new to C++.

UPDATE

Thanks for the quick suggestions. Looks like Vectors are the way to go. I always forget about Vectors. In the front of my mind, a Vector is just a container that holds an x, y and z value :-)

Answer 1

If you are using C++, you can much more easily accomplish this using std::vector:

std::vector<CAT*> cats;
cats.push_back(new CAT);
cats.push_back(new CAT);
cats.push_back(new CAT);

// remove the second cat
delete cats[1];
cats.erase(cats.begin() + 1);

Now the vector has two cats in it (the first and third cats that were inserted) and they are at indices zero and one.

However, in C++, there's no reason to allocate everything dynamically, so you're likely to be better off with just a vector<CAT>:

std::vector<CAT> cats;
cats.push_back(CAT());
cats.push_back(CAT());
cats.push_back(CAT());

// remove the second cat
cats.erase(cats.begin() + 1);

This way, destruction of the cats is handled automatically and you don't have to worry about managing any of the memory yourself.

If you do have to use pointers (e.g., your class is a polymorphic base class), you'd probably want to use a std::vector of smart pointers (e.g., shared_ptrs). With smart pointers, you don't have to remember to delete the objects when you are done with them--it gets done automatically. For example, the above code using shared_ptr would look like:

std::vector<std::shared_ptr<CAT> > cats;
cats.push_back(std::make_shared(new CAT));
cats.push_back(std::make_shared(new CAT));
cats.push_back(std::make_shared(new CAT));

// remove the second cat
// note we don't need to call delete; shared_ptr does that for us
cats.erase(cats.begin() + 1);

(Your standard library may not include shared_ptr in the std namespace yet; in that case, you may find it elsewhere). If you aren't familiar with shared_ptr, the Boost documentation makes for a great introduction.

Answer 2

You could assign NULL to the pointer after deleting and then check if the pointer is NULL or keep an array of bools of the same size which would indicate if that object is there or not. As for reorganizing: If order does matter, then you have to move all the elements as described. If the order does NOT matter, simply move the last element into the missing gap.

Answer 3

Is there any specific reason you can't use std::vector instead of an array? Vector is automatically sizing so you wouldn't have to worry about this.

Answer 4

as others have pointed out using std::vector would do all the reallocation for you, it is still going to be an O(n) operation though. however you may be able to do even better with another data structure. e.g. std::list would allow you remove an element from anywhere in the list in O(1).

ultimately which datastructure is most appropriate will depend on all the operations you need to support on it, their relative frequency and the performance you need from each.