Moving the contents of one vector to another

Question

So I have a vector:

vector<Enemy*> enemies;

This vector hold enemies, which are created dynamically throughout the game.

if(rand() % 1000 > 998)
{
Enemy * enemy = new Enemy(num_of_enemies);
        enemies.push_back(enemy);
}

The problem with this being is that the vector is ever growing even if the enemy has been deleted, which is slowing down my game.

Essentially I want to move the contents of the vector to a new one, but only the elements that actually hold an enemy.

I read that there was something called std::move but I'm not really sure how to implement it properly, or if it will successfully move the elements that contain enemies, and not just the whole vector.

Any help with code implementation of structuring would be greatly appreciated.

Answer 1

First of all, I suggest you shouldn't use a data structure like std::vector if you want to remove a single element in a random position. The complexity of this operation is linear on the number of elements after the deleted element.
As I understand, you have a number of enemies moving around a 2D screen side by side with one (or many) player(s). If an enemy is hit by a player or goes out of the screen, it will be deleted. You just loop over the list of enemies to see these conditions fulfilled.
In this case, I recommend you to use std::map to manage your created enemy objects.
Suppose that your Enemy class has a function to check deletion conditions, e.g:

bool Enemy::willbeDeleted() /* if true then will be deleted */

then here is a class using std::map to manage your enemy objects:
EnemyManager.hpp

#include <map>
class EnemyManager {
public:
  /*
   * Get the Enemy Manager
   */
  static EnemyManager& Instance();

  /*!
   *  Delete the instance of EnemyManager
   */
  static void deleteInstance();

public:
  /* Create an enemy object */
  void createEnemy();

  /* Check all enemy objects and delete any fulfulling condition */
  void checkEnemy();

  virtual ~EnemyManager();

private:
  /* Make sure we can not call EnemyManager constructor directly */
  EnemyManager();
  EnemyManager(const EnemyManager& objManager);

  /* Instance of EnemyManager */
  static EnemyManager* enemyManager;

private:
  /* List of current enemy objects */
  std::map<int, A*> enemyList_;

  /* Identity of already-create object, it increases on creating a new object */
  int enemyIndex_;
};

EnemyManager.cpp

#include "EnemyManager.hpp"
#include <vector>

EnemyManager* EnemyManager::enemyManager = 0;

EnemyManager& EnemyManager::Instance()
{
  if (0 == enemyManager)
  {
    enemyManager = new EnemyManager();
  }

  return *enemyManager;
}
void EnemyManager::deleteInstance()
{
  if (0 != enemyManager) delete enemyManager;
}

EnemyManager::EnemyManager() : enemyList_(), enemyIndex_(0)
{}

EnemyManager::~EnemyManager() {
 /* Nothing todo */
}

void EnemyManager::createEnemy()
{
  enemyList_[enemyIndex_] = new Enemy();
  ++enemyIndex_;
}

void EnemyManager::checkEnemy()
{
  std::map<int, A*>::const_iterator itb = enemyList_.begin(),
                                ite = enemyList_.end(), it;
  // Vector containing id of enemy object to delete
  std::vector<int> enemyToDelete;
  for (it = itb; it != ite; ++it)
    if ((it->second)->willbeDeleted())
        enemyToDelete.push_back(it->first);

  // Delete enemies and remove them from map
  for (std::size_t idx = 0; idx < enemyToDelete.size(); ++idx)
  {
    delete enemyList_[enemyToDelete[idx]];
    enemyList_.erase(enemyToDelete[idx]);
  }
}

you can use this class as follow : in main.cpp

EnemyManager& enemyManager = EnemyManager::Instance();

if(rand() % 1000 > 998)
{
/* Create new enemy */
enemyManager.createEnemy();
}
/* Check all enemies */
enemyManager.checkEnemy();

There are two important functions: createEnemy controls the way to create a new Enemy object, checkEnemy verifies objects and deletes them if needed and the size of enemyList_ won't increase forever :)
I believe with this approach, deleting enemies won't slow down your program anymore.
One of a drawback of this approach is that the number of created objects can be limited by 2^(8*sizeof(enemyIndex_))

Answer 2

Here’s a complete workflow of how to handle spawning and despawning enemies. Note that there are no pointers at all involved.

1. Spawning an enemy:

   if (if random_float_between_0_and_1() < 0.002)
       enemies.push_back(Enemy{arguments});
   

2. Despawning enemies; according to your comment below, should look something like this:

   auto last_iter = std::remove_if(enemies.begin(), enemies.end(), is_dead);
   enemies.erase(last_iter, enemies.end());
   

   Here, is_dead is a function that takes an Enemy const& and determines whether it collided with a player or the screen bounds:

   bool is_dead(Enemy const& enemy) {
       return outside_screen_area(enemy) or near_player(enemy);
   }
   

   The functions outside_screen_area and near_player should be straightforward for you to implement.

   To understand how the code above works, consult the documentations of std::remove and std::vector::erase.

Another thing: implement the function random_float_between_0_and_1 in terms of the standard library random library that ships with C++11. Don’t use std::rand or modulo operations on integer random numbers, they work badly (i.e. they’re not truly uniformly distributed and will give skewed results).

Answer 3

The problem with this being is that the vector is ever growing even if the enemy has been deleted ...

Essentially I want to move the contents of the vector to a new one ...

It seems to me that a simpler approach would be to remove the pointers to deleted objects from the original vector instead of making a copy.

There is no difference between a pointer to a deleted object that no longer exists and a pointer to an existing object. Therefore you must keep track of the elements that must be removed from the vector. The simplest solution is to remove the element immediately after it has been deleted. This becomes much easier with smart pointers since removing the pointer also deletes the object automatically.

std::move won't help you with this problem.

You may want to consider not using manual dynamic allocation at all. You can instead store Enemy objects in the vector.

When the enemy is to be deleted I call the class destructor, and than [sic] I delete

delete expression calls the destructor. Calling it yourself also will have undefined behaviour.