我正在为学校做一项作业，模拟学生排队和注册处打开多个窗口的情况。我们必须计算平均值、中位数、最长等待时间等统计数据，以便在模拟结束时显示。
有人建议我创建另一个双向链表，当学生在窗口“完成”时将他们放入其中，以便计算这些统计数据。
在循环/程序运行时只跟踪那些东西(中位数除外)不是更有效吗？然后对于中位数，我可以创建一个学生等待时间的数组，并在学生队列通过后对整个数组进行排序。
或者在学生在窗口完成后为他们做另一个双向链表然后只用它来计算最后的统计数据是否更有效/更好的做法？
最佳答案
这里有两个性能方面的考虑；
哪种容器类型最适合您的情况？
我将把您选择的链表与 vector 进行比较，这是我对该场景的建议；
您正在谈论存储多个条目，然后在某个时间点对它们进行迭代以计算一些统计数据，在考虑迭代时，使用任何类型的链表都会立即成为一个问题。链表的问题在于内存是不连续的，因此当您迭代项目时，缓存未命中率要高得多，请参阅 what every programmer should know about memory以获得非常详细的解释，但简而言之；如果内存尚未加载到缓存中，那么您将不得不等待它加载，这会花费大量时间，并且对于算法级优化来说是一个轻松的胜利。另一方面， vector 是连续的，因此迭代它们可以保证产生尽可能低的缓存未命中率，但这当然是以插入为代价的。
对于您希望在数据集之间进行大量插入、删除或移动条目的场景，链表要好得多，因为它们只是交换一些指针并继续，例如AAA CCC BBB 的字母顺序列表，先添加 AAA，然后添加 CCC，需要插入 BBB，它应该在 CCC 之前。 vector 处理插入特别糟糕，通常必须将插入点和末尾之间的所有数据移动一个位置，如果你总是在 vector 的开头插入，那么你每次都必须移动元素!尽管如此;您没有声明需要排序数据，所以我假设这不会成为问题。
除了移动数据外，由于 vector guaranteeing连续内存，当它们到达当前分配的末尾时，它们必须重新分配并将整个内容复制到新分配。如果您事先知道会有多少条目，那么您可以通过使用 reserve(n) 来避免这个问题，它将分配足够的内存来存储 n 条目，如果失败vector 将在您每次传递当前 n 时重新分配，但是假设您的实现使用 smarter reallocation strategy不仅仅是将当前大小加倍，此成本会随着更大的重新分配而降低。
惰性或急切求值
你问的问题是你是否应该在每次进入时评估你的统计数据，或者在最后，或者第三个值得考虑的选项；只有当它被要求时!这是对evaluation strategies的考虑.在您的情况下，我绝对会推荐真正或部分懒惰的评估，除非您需要平均值/中值的总计，否则没有必要为每个新条目计算它们，只有在需要时才计算它。每当计算平均数据时，只需将 bool 存储为 true，并在每次插入或从数据集中删除时设置为 false。
关于c++ - 从队列创建双向链表查找中位数与使用数组的效率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29332006/