随着时间的推移，我的程序变慢了，我不知道为什么。内存泄漏？

Question

我正在开发一个用作非常简单的投票系统的程序，它从文件中读取数字，将文件中的数字转换为 unsigned int 类型。

以下是 txt 文件中数据的示例：

1 34 2 50 23 12
1 30 5 17
5
30 2 3 22
23 45

每行是一个人的投票，每行的数字是该人的候选人偏好，左边是第一偏好，右边是最后偏好。

一旦从文件中读取了所有数据，它就会进入一个无限循环，每一轮（迭代）它都会计算剩余的候选人（即淘汰得票最少的候选人）。当找到获得多数票的候选人时，程序以代码 0 退出。

我的问题是使用 g++ 编译器，大约在 40 左右时程序开始变慢，我假设这是因为内存泄漏，但我不知道它可能在程序中的哪个位置漏水了。

This is what I get when debugging the program through Deleaker.

注：谢谢大家的帮助。然而，尽管我不想这样做，但由于某些原因，我需要在此处编辑 posted 代码。我不会删除 post 以防有人能以某种方式在答案中找到用处。希望您理解，谢谢。

Answer 1

这里是我的一些猜测，但是从算法的时间复杂度上来说，

while (p != vote_collection.end())  {
    //...
    if (p->spent()) {
        p = vote_collection.erase(p);
    }
 }

是有问题的，因为 vote_collection 是一个向量。假设 N 是容器的大小，即投票数。当 p->spent() 为真时（这在以后的迭代中更有可能发生），那么您将要擦除 p。从向量中删除一个元素在最坏的情况下具有 N 的线性时间复杂度（在开始时删除时，您可能会在从头到尾迭代向量时这样做。）因为这将发生在许多他投票，这个循环在 N 中具有二次时间复杂度。如果输入变量可能很大，您总是想尝试避免二次复杂性。

出现这种情况的原因是矢量将元素连续存储在内存中。当您擦除一个元素时，擦除后的所有其他元素都必须移动一个元素以缩小间隙。这需要在擦除元素接近开头时移动几乎整个向量。

您可以简单地将所有已花费的选票留在向量中，并确保 ranked_candidates 跳过已花费的选票，而不是使用当前方法。

随着时间的推移，我的程序变慢了，我不知道为什么。内存泄漏？

My program is slowing down over time and i have no idea why. Memory leak?

c++

performance

memory-leaks