C++标准类库应用细节分析

C++编程语言已经推出就受到了广大开发人员的青睐。其功能的强大性使其在开发领域中占据着重要的地位。我们在这里介绍的C++标准类库就是其中一个比较基础的应用技术。

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

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

让我们来仔细了解游戏开发中的一个非常普遍的问题：你希望保存一组对象，（我们会称其为对象列表，虽然不一定要保存在C++标准类库的列表中）通常你会要求每个对象在这个表有且仅有一个，这样你就不用担心一个偶然产生的在容器中插入一个已存在单元的操作了。C++标准类库的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倍。

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

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

for(Collection::iterator it = Collection.begin(); 


it != Collection.end(); ++it) 

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

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

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