shrink_to_fit()vs swap技巧

Question

我有一个游戏,某些游戏对象一次性产生,然后在它们被摧毁/杀死时消失.游戏对象是一个元素std::vector,我想最小化内存使用.我习惯了交换技巧,

std::vector<gameObject>(gameObjectVector.begin(), gameObjectVector.end()).swap(gameObjectVector);

但我注意到了shrink_to_fit()C++ 11 的内置版本.但是,它具有线性复杂性,而交换技巧是不变的.交换技巧在各方面都不是优越的吗？

Answer 1

交换技巧实际上不是恒定时间.执行实际交换的成本确实是O(1),但是然后是std::vector析构函数触发和清理所有分配空间的成本.如果底层对象具有非平凡的析构函数,则可能会花费Ω(n),因为std::vector需要去调用那些析构函数.还有为初始向量中存储的所有元素调用复制构造函数的成本,类似于Ω(n).

因此,两种方法应该具有大致相同的复杂性,除了shrink_to_fit更清楚地表达意图并且可能更适合编译器优化.

Answer 2

在 isocpp.org 上也有推荐的已接受答案是错误的。

shrink_to_fit是非约束性要求。我个人认为 ISO 将其保留为非投标是愚蠢的（没有对发生的事情提供一些更有力的保证），因为它令人困惑，但也许他们有很好的理由（tm）。