c++ - STL 与结构中的速度问题

Question

最近我看到了 C 和 C++ 之间的一些速度差异，有时很难说在一种情况下哪一个更快。

我知道 STL 自推出以来已经简化了很多，但它是否以速度/内存成本简化了一些东西？

例如，有多种方法可以使用带有指针的结构来定义堆栈/队列/二叉树/图等。不过，这些实现有点复杂。另一种方法是简单地使用来自 STL 的向量，该向量具有使用模板随意增加和减小大小的能力。还为地图、队列等实现了许多模板。

我的问题是，您认为哪种实现在时间和内存复杂性方面更有效，为什么？

Answer 1

C++ 标准库经过多年的开发、性能调整和调试，随着编译器优化的改进，您可以从标准容器中获得非常好的开箱即用性能。可能最大的性能瓶颈是去堆获取内存，在某些情况下可以减少，例如reserve向量。

如果您正在编写 C++，只需根据您的软件需求使用所有可用的容器和算法。然后，如果您有性能问题，您可以分析您的代码（很可能瓶颈仍然不是标准库）。

Answer 2

这里的关键当然是，如果您使用“侵入式”解决方案，也就是说，您将链表的链接存储在每个节点内，而不是拥有一个单独的节点结构，该结构包含指向其他位置的指针/引用，该位置包含数据本身，会有一些性能影响[并且可以在两个方向上起作用-不一定侵入式解决方案总是最好的]。

人们弄错的典型情况是，他们比较将分配的对象存储在某种容器中，然后将其与将对象副本存储在容器中的解决方案进行比较。如果该容器需要通过重新分配来“增长”，那么它将导致性能问题。但这只是“如果要存储的东西的选择错误”或“这种类型的对象存储的容器类型错误”。

在大多数情况下，你如何做某事（例如它是一棵树还是一个向量）的实现是你获得 100 倍改进的地方。为这种类型的存储编写特定的东西会给你 5-20% 的改进，这取决于原始代码的好坏和优化代码的编写好坏。现在，假设它不是游戏中渲染循环的内部细节的一部分，也不是 OS 内核中的调度程序或内存分配代码，那么 5% 是不值得拥有的，而对于绝大多数代码，20% 的改进可能是[对于系统功能的一部分-如果您将内容存储在容器中，希望您可以用它做更多的事情，而不仅仅是简单地存储它并在容器内容上来回工作，对吗？]

在花时间优化代码之前，应该对代码花费时间的地方进行一些体面的分析。然后你可以攻击使它变得更好。第一步是查看“这里的算法的行为是什么？” 当我们可以使用更快的不同方法时，我们是否花费 O(2^n) 对某些东西进行排序？当列表、堆栈或队列可能是更好的选择时，我们是否会花时间从大型数组中插入/删除内容？当我们可以写入较少数量的大块时，我们是否正在将小块数据写入磁盘？

这类问题将为您带来 5、10、100 倍的改进，从而带来真正的不同。当然，剃掉 5% 的东西是值得的。有时减少 0.5% 的折扣是值得的，如果它能让你的游戏以 200 fps 而不是 100 fps 运行，因为正是这 0.5% 的折扣让你超过了帧切换率。但总的来说，如果它至少没有将速度提高一倍，您可能应该将时间花在其他地方。