Linux系统编程之C++游戏程序优化

　　Set的删除操作消耗时间O(log n)，看起来是很快，如果你不考虑可能对free()的调用的话。Vector的删除操作消耗O(n)，这是因为从被删除的那个元素开始到结尾处的元素，每一个元素都要被拷贝到前一个位置上。如果元素都只是指针的话，那么这个拷贝将可以依靠一个简单的memcpy()来完成，而这个函数是相当快的。（这也是为什么通常都把对象的指针储存在STL的容器中的一个原因，而不是储存对象本身。如果你直接保存了对象本身，将会在很多操作中造成许多额外的构造函数的调用，例如删除等）。

　　set和map通常来说麻烦大于有用，如果你还没有意识到这一点的话，考虑遍历一个容器的代价，例如：

　　如果Collection是vector，那么++it就是一个指针自增。但是当Collection是一个set或者是一个map的话，++it包括了访问红黑树上的下一个节点。这个操作相当复杂而且很容易造成cache不命中，因为树的节点几乎遍布内存的各处。

　　当然，如果你要在容器中保存大量的元素，并且进行许多的成员请求，那么set的O(log n)的效率完全可以抵消那些内存方面的消耗。近似的，如果你偶尔才使用容器，那么这里的效率差别就非常的小。你应该做一些效率评估以了解多大的n会使set变得更快。也许你会惊奇的发现在游戏的大多数典型应用下vector的所有效率都比set要高。

　　这还不是STL内存使用的全部。一定要了解当你使用clear方法时，容器是否真的释放掉了它的内存。如果没有，就可能产生内存碎片。比如，如果你开始游戏的时候建立了一个空的vector，在游戏过程中增加元素，然后在游戏restart时调用clear，这时vector未必释放它的全部内存。这个空的vector，可能依然占据了堆中的内存，并使其变成碎片。如果你真的需要这样来实现游戏的话，对这个问题有两种解法。一是你可以在创建vector时调用reserve()，为你可能需要的最大数量的元素保留足够的空间。如果这不可行的话，你可以强迫vector完全释放内存：