我可以使用哪种数据结构来释放连续内存中的内存?

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就不会在void Population::newGeneration()的currentOffsprings.resize(0);线上被杀.然后在void Population::pruneDeadLineages()中，我会用方法Individual::destructor()而不是使用delete或Individual::~Individual()来明确删除个人。

傻吗？它是否是内存安全的(或导致分段错误或内存泄漏(？我还有什么其他选择来1(确保当代个体在记忆中是连续的，2(我可以在这个连续的记忆中释放没有留下任何后代的祖先的记忆？

Answer 1

我真的不明白为什么你需要将Individual连续存储在内存中。

由于您必须删除其中一些并在每一代时添加其他内容，因此您必须对整堆Individual执行重新分配，以使它们在内存中保持连续。

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

---

我认为最简单的方法是让std::vector为你做这些事情。不需要指针。

在每一代，你把后代从currentOffsprings移动到currentParents，你清除((currentOffsprings。
然后，对于当前一代中没有任何子级的每个父级，您只需使用 erase(( fromstd::vector来删除它们，从而让std::vector负责保持其元素连续。

好于100个单词，例如：

void Population::newGeneration()
{
currentParents.swap(currentOffsprings);
currentOffsprings.clear();
}
void Population::pruneDeadLineages()
{
currentParents.erase(std::remove_if(currentParents.begin(), currentParents.end(), [](const Individual & ind){return ind.nbChildren == 0;}), currentParents.end());
}

当然，它假设父母和后代在Population中被定义为：

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

注：当std::remove_if移动容器末尾要删除的元素时，要保留的元素将保持连续，因此在执行擦除时不会重新分配。

这样，您的两个要求(在内存中保持Individual连续并摆脱死谱系(将被填充，而不会对析构函数做奇怪的事情,...

但是由于您有两个std::vector，因此可以确保currentOffsprings连续存储在内存中，currentParents也是如此。
但是这两个std::vector绝对不能保证彼此相邻(但我想你已经意识到了这一点，这不是你想要的(。

_{如果我误解了您的实际问题，请告诉我}