Arrays instead of vectors

[Bullet Pulse]

I've usually used vectors in the past to store pointers to objects, but I want to know how to do this with an array.

So, say that I wanted an array of Battleships for a game, and they are destroyed in a random order.

Code: Select all

const int MAX_BATTLESHIPS = 100;
Battleship *battleships[MAX_BATTLESHIPS];

//Sample function to add a ship to the array
void AddShip()
{
   battleships[FindEmptyIndex()] = new Battleship;
}

void RemoveShip(int index)
{
   delete battleships[index];
   battleships[index] = 0;
}

int FindEmptyIndex()
{
   for (int i = 0; i < MAX_BATTLESHIPS; i++)
      if (!battleships[i]) return i;
}

Is this the way to do it?

[X Abstract X]

I haven't had to do this but just by looking at it, it looks like the way I would go about doing it. Not that it's necessary but I would use unsigned ints where appropriate and add a bounds check inside the RemoveShip() function.

[Amarant]

There is no 'THE' way to do it.
Here's something else you could do if the order of the BattleShips in the array is not important:

Code: Select all

const int MAX_AMT_OF_BATTLESHIPS = 100;
Battleship *battleships[MAX_AMT_OF_BATTLESHIPS];

int battleship_count = 0;

//Sample function to add a ship to the array
void AddShip()
{
    if(battleship_count == MAX_AMT_OF_BATTLESHIPS)
        handleError();
    battleships[battleship_count] = new Battleship;
    battleship_count++;
}

void RemoveShip(int index)
{
    delete battleships[index];
    battleship_count--;
    battleships[index] = battleships[battleship_count];
}

So when you remove a battleship the last battleship in the array will take it's place and the array will be 'shortened'.

[Bullet Pulse]

There is no 'THE' way to do it.

I just mean an efficient way to do it

[Amarant]

I guessed correctly then

The example I've given will be more efficient especially for large full arrays. Since the add and remove functions don't change in performance with the size of the array. Your example will increasingly get slower if you use larger and fuller arrays.

For this particular example however, it probably will not be noticeable.

[XianForce]

That looks fine, but here are a few suggestions:

Code: Select all

const int MAX_BATTLESHIPS = 100;
Battleship *battleships[MAX_BATTLESHIPS];

//Sample function to add a ship to the array
void AddShip()
{
   //You need to check if there actually IS an empty index!
   unsigned int emptyIndex = FindEmptyIndex();

   if(emptyIndex > 0)
   {
      battleships[FindEmptyIndex()] = new Battleship;
   }
}

void RemoveShip(int index)
{
   //check to make sure you don't go outside of the bounds!
   if(index > 0 && index < MAX_BATTLESHIPS)
   {
      //Also, check to make sure the battleship is not already NULL!
      if(battleships[index])
      {
         delete battleships[index];
         battleships[index] = 0;
      }
   }
}

int FindEmptyIndex()
{
   //The only problem with this, is when it DOESN'T find an empty index, no value is returned...
   for (int i = 0; i < MAX_BATTLESHIPS; i++)
      if (!battleships[i]) return i;

   return -1;
}

So I think that should probably work.

[XianForce]

There is no 'THE' way to do it.
Here's something else you could do if the order of the BattleShips in the array is not important:

Code: Select all

const int MAX_AMT_OF_BATTLESHIPS = 100;
Battleship *battleships[MAX_AMT_OF_BATTLESHIPS];

int battleship_count = 0;

//Sample function to add a ship to the array
void AddShip()
{
    if(battleship_count == MAX_AMT_OF_BATTLESHIPS)
        handleError();
    battleships[battleship_count] = new Battleship;
    battleship_count++;
}

void RemoveShip(int index)
{
    delete battleships[index];
    battleship_count--;
    battleships[index] = battleships[battleship_count];
}

So when you remove a battleship the last battleship in the array will take it's place and the array will be 'shortened'.

One thing... Won't this just make it so TWO elements in the array have the same value?, I think you need to do something like:

Code: Select all

void RemoveShip(int index)
{
delete battleships[index];
battleship_count--;
battleships[index] = battleships[battleship_count];
battleships[battleship_count = NULL;
}

Right?

Oh and because your incrementing battleship_count for each ship you add, you'll have an 'off by one error' won't you? Because battleship_count is how many battleships you have, but the last battleship in the array would be battleship_count - 1, wouldn't it?

[Bullet Pulse]

That looks fine, but here are a few suggestions:
...
So I think that should probably work.

Thanks!

EDIT: Shouldn't it be:

Code: Select all

if (emptyIndex >= 0)
{
      battleships[FindEmptyIndex()] = new Battleship;
}

[Amarant]

...

One thing... Won't this just make it so TWO elements in the array have the same value?, I think you need to do something like:

Code: Select all

void RemoveShip(int index)
{
delete battleships[index];
battleship_count--;
battleships[index] = battleships[battleship_count];
battleships[battleship_count = NULL;
}

Right?

Oh and because your incrementing battleship_count for each ship you add, you'll have an 'off by one error' won't you? Because battleship_count is how many battleships you have, but the last battleship in the array would be battleship_count - 1, wouldn't it?

Hmmm, I do think my version was correct. Let me think it through.

When you call RemoveShip battleship_count will equal the amount of elements in the array.
So if you use that count as an index, it will point to exactly one position after the last element.
If you then decrement that count, it will point exactly to the last element.
Using it now as an index will get you the last element.
Then assign that last element to the position in the array you've just emptied.
This will indeed result in there being two identical pointers in the array.
But remember that the battleship_count was decremented.
So the next time you will use the add function it will simply be overwritten.

I intentionally named the variable battleship_count, indicating that it is the count of battleships in the array.
If I would have wanted to store the highest index in the array I would have chosen another name for the variable.

[XianForce]

That looks fine, but here are a few suggestions:
...
So I think that should probably work.

Thanks!

EDIT: Shouldn't it be:

Code: Select all

if (emptyIndex >= 0)
{
      battleships[FindEmptyIndex()] = new Battleship;
}

Ooops, actually I meant to do:

Code: Select all

battleships[emptyIndex] = new Battleship();

Just a safety thing in case FindEmptyIndex() returns something different.

[Bullet Pulse]

That looks fine, but here are a few suggestions:
Ooops, actually I meant to do:

Code: Select all

battleships[emptyIndex] = new Battleship();

Just a safety thing in case FindEmptyIndex() returns something different.

I know that's what you meant

[XianForce]

Hmmm, I do think my version was correct. Let me think it through.

When you call RemoveShip battleship_count will equal the amount of elements in the array.
So if you use that count as an index, it will point to exactly one position after the last element.
If you then decrement that count, it will point exactly to the last element.
Using it now as an index will get you the last element.
Then assign that last element to the position in the array you've just emptied.
This will indeed result in there being two identical pointers in the array.
But remember that the battleship_count was decremented.
So the next time you will use the add function it will simply be overwritten.

I intentionally named the variable battleship_count, indicating that it is the count of battleships in the array.
If I would have wanted to store the highest index in the array I would have chosen another name for the variable.

Yeah I didn't even think about the decrement haha.

[avansc]

hey, kinda just read half assed, so sorry if this is a duplicate answer.

you are spending a lot of time finding an open slot, another way would be to always have your ships ordered.
in other words have a count of how many objects you have resident, then if you add one you just add it to the back of the array and increment the residency counter.

when you delete something, from position x, you know you have to move all the aft memory one object size up, in this case just the 4 or 8 bytes of the pointer, and also remember to decrement the counter.this way your adding is O(1), you'll occur some over head in the memmove, but it should be a lot cheaper than trying to find open locations.