rink_to_fit()vs交换技巧 [英] shrink_to_fit() vs swap trick

问题描述

我有一个游戏，其中某些游戏对象会立即全部生成，然后在它们被销毁/杀死后重新生成.游戏对象是 std :: vector 中的元素，我想最大程度地减少内存使用.我已经习惯了交换技巧，

I have a game where certain game objects spawn all at once and then despawn as they get destroyed/killed. The game objects are elements in an std::vector, and I'd like to minimize memory usage. I'm used to the swap trick,

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

但是我注意到C ++ 11中内置的 shrink_to_fit().但是，在交换技巧不变的情况下，它具有线性复杂度.交换技巧不是在各个方面都优越吗?

but I noticed the inbuilt shrink_to_fit() from C++11. However, it has linear complexity while the swap trick is constant. Isn't the swap trick superior in every way?

推荐答案

交换技巧实际上不是固定时间的.进行实际交换的成本确实为O(1)，但是还有 std :: vector 析构函数触发并清理所有分配空间的成本.如果基础对象具有非平凡的析构函数，则可能有成本Ω(n)，因为 std :: vector 需要去调用那些析构函数.对于存储在初始向量中的所有元素，调用复制构造函数也存在成本，这与Ω(n)类似.

The swap trick isn't actually constant-time. The cost of performing the actual swap is indeed O(1), but then there's the cost of the std::vector destructor firing and cleaning up all the allocated space. That can potentially have cost Ω(n) if the underlying objects have nontrivial destructors, since the std::vector needs to go and invoke those destructors. There's also the cost of invoking the copy constructors for all the elements stored in the initial vector, which is similarly Ω(n).

因此，这两种方法应该具有大致相同的复杂度，只是 shrink_to_fit 更清楚地表明了这一意图，并且可能更适合编译器优化.

As a result, both approaches should have roughly the same complexity, except that shrink_to_fit more clearly telegraphs the intention and is probably more amenable to compiler optimizations.

这篇关于rink_to_fit()vs交换技巧的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！