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

　　5、标准类库（STL）

　　标准类库是一套实现了常见的结构和算法的模板，例如dynamic arrays（称为vector），set，map等等。使用STL可以节省你很多时间来写和调试那些容器。和之前谈到的一样，如果希望系统的效率最大化，你必须要注意你的STL的具体实现的细节。

　　为了能够对应于最大范围的应用，STL标准在内存分配这个领域保持了沉默。在STL容器中的每一个操作都有一定的效率保证，例如，给一个set进行插入操作只要O(log n)的时间，但是，对一个容器的内存使用没有任何保证。

　　让我们来仔细了解游戏开发中的一个非常普遍的问题：你希望保存一组对象，（我们会称其为对象列表，虽然不一定要保存在STL的列表中）通常你会要求每个对象在这个表有且仅有一个，这样你就不用担心一个偶然产生的在容器中插入一个已存在单元的操作了。STL的set忽略副本，所有的插入、删除和查询的速度都是O(log n)，这是不是就是很好的选择呢？

　　虽然在set上的大多数操作的速度都是O(log n)，但是这里面依然存在着潜在的危机。虽然容器的内存使用依赖于实现，但很多实现还是在红黑树的基础上实现的。在红黑树上，树的每一个节点都是容器的一个元素。常见的实现方法是在每一个元素被加入到树时，分配一个节点，而当每个元素被移出树时，释放一个节点。根据你插入和删除的频繁程度，在内存管理器上所花费的时间将或多或少的影响你通过使用set而获得的好处。

　　另外一个解决方案是使用vector来存储元素，vector保证在容器的末端添加元素有很高的效率。这表示实际上vector只在很偶然的情况下才重新分配内存，也就是说，当满的时候扩容一倍。当使用vector来保存一个不同元素列表的时候，你首先要检查元素是否已经存在，如果没有，那么加入。而对整个vector检查一遍需要花费O(n)的时间，但是但实际牵涉到的部分应该比较少，这是因为vector的每个元素都在内存中连续存放，所以检查整个vector实际上是一个易于cache的操作。检查整个set将造成cache不命中，这是因为在红黑树上分别存放的元素可能散布在内存的各个角落。同时，我们也注意到set必须额外维护一组标记以设置整个树。如果你要保存的是对象的指针，set可能要花费vector所要花费的内存的3到4倍。