将一个向量的内容移动到另一个向量中

Question

So I have a vector:

vector<Enemy*> enemies;

这个向量保存了游戏中动态创建的敌人。

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

这个问题在于即使敌人已经被删除，向量仍然不断增长，这会拖慢我的游戏速度。

基本上我想将向量的内容移动到一个新的向量中，但只移动实际持有敌人的元素。

我读到有一个叫做 "std::move" 的东西，但我不确定如何正确实现它，或者它是否成功移动包含敌人的元素，而不仅仅是整个向量。

非常感谢您提供关于结构化代码实现的任何帮助。

- Nick

---

看起来在你的设计中，“enemies” 向量存储了已经被删除的敌人的指针。 - Edgar Rokjān

如果您需要添加和删除很多元素，请考虑使用std::deque或std::list。此外，存储Enemy对象而不是Enemy*对象。不要使用手动动态内存分配。 - Konrad Rudolph

使用vector<Enemy>或vector<shared_ptr<Enemy>>可以解决许多问题。 - M.M

@Nick，确实如此。更糟糕的是，这是未定义的行为。您需要了解delete的实际作用。但是，如果您在这里没有使用指针（和适当的数据结构；请参见上文），那么您首先就不会遇到这个问题。 - Konrad Rudolph

这只是一个简单的2D游戏。敌人基本上只存在于屏幕上，如果它们被玩家击中或移出屏幕，则应将其删除并从向量中移除。这就是我遇到的问题。 - Nick

Answer 1

这是一份完整的处理生成和消除敌人的工作流程，注意其中没有涉及到指针。

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.

另外一件事：使用C++11标准库中提供的随机库实现函数random_float_between_0_and_1。不要使用std::rand或对整数随机数进行模运算，它们效果不佳（即它们不是真正均匀分布的，会产生偏斜结果）。

- Konrad Rudolph

---

我有点困惑。你提供的代码是两个函数吗？第一个函数是随机生成敌人，第二个函数是删除敌人。这是否意味着 vector<Enemy*> enemies; 也需要修改？我应该传入什么参数到despawn函数中？ - Nick

@Nick 你的敌人在哪里生成和消失？我的函数只是那段代码的占位符。相关部分是我函数内部的代码（为了避免混淆，我会从答案中删除这些函数！）。关于容器，是的，你需要将其更改为 std::vector<Enemy> enemies;。 - Konrad Rudolph

我认为这些对于我的实现来说有点超纲了。我只是个初学者，这一切对我来说都有点难以承受。我理解你添加的第一个函数，它基本上是生成敌人的一种方式（与我在问题中提出的向量版本略有改动），更让我困惑的是第二个函数。我想我明白它是像一个范围循环，遍历向量，但是"which"之后我具体添加了什么呢？ - Nick

@Nick 我的代码比你的简单得多：只需比较间接寻址（指针或其他方式）或代码行数即可。问题在于你没有告诉我们如何确定要杀死/移除哪个敌人，所以我不得不猜测。 - Konrad Rudolph

@Nick 很难确定你的问题，which 将是要删除的元素，enemies.erase(it); 将从向量中删除该对象。这意味着你的向量需要是敌人对象的向量，而不是敌人指针的向量。请注意，消失代码可以简化为 enemies.erase(enemies.begin()+whicheverElementYouWantToD‌​elete)。 - George

Answer 2

这个问题在于即使敌人已经被删除，向量仍然不断增长...

本质上，我想将向量的内容移动到一个新的向量中...

对我来说，一个更简单的方法似乎是从原始向量中删除已删除对象的指针，而不是制作副本。

指向不存在的已删除对象和指向现有对象的指针之间没有区别。因此，您必须跟踪必须从向量中删除的元素。最简单的解决方案是在删除后立即删除该元素。使用智能指针会变得更加容易，因为删除指针也会自动删除对象。

std::move 对此问题无济于事。

您可能希望考虑根本不使用手动动态分配。您可以将 Enemy 对象存储在向量中。

当敌人要被删除时，我调用类析构函数，然后删除。

delete 表达式调用析构函数。自己调用它也会产生未定义的行为。

- eerorika

---

你能否使用我提供的代码，给我一个删除向量指针的例子？ 如果我正在动态创建敌人，为什么您认为我根本不应该使用动态分配？ - Nick

“你可能想要考虑完全不使用动态分配。” — 这是本世纪的轻描淡写之语：在这里不要使用动态分配。 - Konrad Rudolph

那么我该怎么办呢？现在我需要的是建议。 - Nick

@Nick，你看过std::vector的API了吗？它有一个erase成员函数。我并没有说你不应该使用动态分配，我是说你应该考虑不使用动态分配。你的示例没有展示出需要动态分配的必要性。你在问题正文中也没有解释使用动态分配的原因。使用动态分配和指针比直接存储对象更复杂，我猜这就是你错误销毁对象的原因。我扩展了我的建议，并说明如何继续进行。 - eerorika

@KonradRudolph 向量使用动态分配。实际上，当对象数量在运行时不受限制时，动态分配和递归自动分配是唯一的选择。 - M.M

@M.M 重点是要避免手动动态分配。我因疏忽错过了“动态”这个词，但我在问题下面的评论中提到了这一点。 - Konrad Rudolph

Answer 3

首先，我建议您不要使用像std::vector这样的数据结构，如果您想删除一个随机位置上的单个元素。此操作的复杂度是线性的，取决于删除元素后的元素数量。
据我所知，您有许多敌人在2D屏幕上并排移动，与一个或多个玩家一起。如果敌人被玩家击中或跑出屏幕，它将被删除。您只需循环遍历敌人列表以满足这些条件。
在这种情况下，我建议您使用std::map来管理创建的敌人对象。
假设您的敌人类具有检查删除条件的函数，例如：

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

那么这里有一个使用 std::map 管理敌人对象的类：
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]);
  }
}

您可以按照以下方式使用此类： 在main.cpp中

EnemyManager& enemyManager = EnemyManager::Instance();

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

有两个重要的函数：createEnemy控制着创建新 Enemy 对象的方式，checkEnemy验证对象并在需要时删除它们，enemyList_ 的大小不会永远增加 :)
我相信通过这种方法，删除敌人不会再减慢您的程序。
这种方法的一个缺点是创建的对象数量可能会受到 2^(8*sizeof(enemyIndex_)) 的限制。

- NewbieDev

---

你正确地认为使用向量删除敌人需要线性时间。然而，你的checkEnemy函数也具有线性运行时间，并且还有更大的开销——我保证，无论敌人数量多少，它都会比我的答案中的方法慢得多。 - Konrad Rudolph

checkEnemy 可能比您的方法慢，但我认为不会差太多。我的方法基于 Enemy 对象通过 new 分配空间并通过 delete 释放空间这一事实构建。如果我们直接将 Enemy 对象存储在容器中，您的方法更加简洁，也相当不错 :) - NewbieDev