我可以使用什么数据结构来释放连续内存中的内存？

Question

我想随着时间的推移模拟种群，并保留仍然活着的个体的家谱（我不需要保留关于死血统的数据）。世代是离散的且不重叠的。为简单起见，我们假设生殖是无性的，并且每个人只有一个父母。这是一个类Individual

class Individual
{
public:
   size_t nbChildren;
   const Individual* parent;

   Individual(const Individual& parent);
};

在我的Population类中，我将为当前后代和当前父母（当前父母为上一代的后代）提供一个向量。

class Population
{
private:
  std::vector<Individual*> currentOffsprings;
  std::vector<Individual*> currentParents;

public:
  addIndividual(const Individual& parent) // Is called from some other module
  {
      Individual* offspring = new Individual(parent);
      currentOffsprings.push_back(offspring);
  }

  void pruneDeadLineages() // At the end of each generation, get rid of ancestors that did not leave any offsprings today
  {
    // Collect the current parents that have not left any children in the current generation of offsprings
    std::queue<Individual*> individualsWithoutChildren; // FIFO structure
    for (auto& currentParent : currentParents)
    {
      if (currentParent->nbChildren() == 0)
      {
        individualsWithoutChildren.push(currentParent);
      }
    }

    // loop through the FIFO to get rid of all individuals in the tree that don't have offspring in this generation
    while (individualsWithoutChildren.size() != 0)
    {
      auto ind = individualsWithoutChildren.pop_front();
      if (ind->nbChildren == 0)
      {
        ind->parent.nbChildren--;
        if (ind->parent.nbChildren == 0)
        {
          individualsWithoutChildren.push(ind->parent);
        }
        delete ind;
      }
    }
  }

  void newGeneration() // Announce the beginning of a new generation from some other module
  {
    currentParents.swap(currentOffsprings); // Set offsprings as parents
    currentOffsprings.resize(0);            // Get rid of pointers to parents (now grand parents)
  }

  void doStuff() // Some time consuming function that will run each generation
  {
    for (auto ind : currentOffspings)
    {
      foo(ind);
    }
  }
};

[假设我的代码的最慢部分将在doStuff方法中循环遍历各个个体，我想在内存中保持各个个体的连续性，因此

  std::vector<Individual*> currentOffsprings;
  std::vector<Individual*> currentParents;

将成为

  std::vector<Individual> currentOffsprings;
  std::vector<Individual> currentParents;

现在的问题是，我不想为那些在这一代没有留下任何后代的祖先消耗内存。换句话说，我不想保留每一代人口中每一代个体的总长度。我以为可以实现不执行任何操作的Individual的析构函数，以免祖父母代的Individuals在currentOffsprings.resize(0);的void Population::newGeneration()行处被杀死。然后在void Population::pruneDeadLineages()中，我将使用方法Individual::destructor()明确删除个人，而不是使用delete或Individual::~Individual()。

傻吗？它是内存安全的（或导致分段错误或内存泄漏）吗？我还有什么其他选择：1）确保一代人的记忆是连续的； 2）对于没有留下任何后代的祖先，我可以在连续的记忆范围内释放记忆？

Answer 1

我不太明白为什么您需要将Individual连续存储在内存中。

由于您必须删除其中一些并在每一代中添加其他，所以您必须对整个Individual进行重新分配，以使其在内存中保持连续。

但是无论如何，我不会质疑你想做什么。

---

我认为最简单的方法是让std::vector为您完成任务。不需要指针。

[下一代，将后代从currentOffsprings移到currentParents，然后将clear()移到currentOffsprings。然后，对于当前代中没有任何子代的每个父代，您可以使用erase()中的std::vector来删除它们，然后让std::vector保持其元素连续。

这样，您将满足两个需求（保持Individual在内存中连续并摆脱无用的血统），而无需使用析构函数做怪异的事情，...

但是当您有两个std::vector时，可以确保将currentOffsprings连续存储在内存中，对于currentParents同样。但是绝对不能保证两个std::vector彼此相邻（但是我想您已经意识到了这一点，并且这不是您想要的）。

_{让我知道我是否误解了您的实际问题}