[原]解析STL中典型的内存分配

winston

1 vector
在C++中使用vector应该是非常频繁的，但是你是否知道vector在计算内存分配是如何么？

     在c++中vector是非常类似数组，但是他比数组更加灵活，这就表现在他的大小是可以自动分配的，就是当你的数据量增大的时候，自动的为你分配空间，当你的分配的大小不够的时候，他就会在分配的内存后边增加2倍大小的空间，
vector增加的空间是连续的，因此这个就涉及到了，当你在后边的空间不够的时候，那么计算机就会把你的数据copy一份空间更大的地方来给你分配足够的空间，这，就给计算机带来了不必要的性能损失。
    因此，在设计程勋的时候，如果频繁的增加空间，插入数据的时候，，你就应该考虑其他容器，比如Deque 容器，


2 deque
   deque 和vector一样都是标准模板库中的内容，deque 是双端队列，在接口上和vector 非常相似，在许多操作的地方可以直接替换。假如读者已经能够有效地使用vector容器，下面提供deque的成员函数和操作，进行对比参考。
因为Deque使用的是非连续的内存空间，有效的利用了内存空间，如果想知道 vector和deque比较的话，
请查看这篇文章http://www.cnblogs.com/me115/archive/2010/10/15/1852432.html  我在这里不做过多解释。

3 stack queue 及其他

stack和queue  ，这个应该大家都知道堆栈和队列，这两个都不提供iterator操作。但是均可以作为list和deque的底层操作。

list ，双向链表，就是我们常说的环状的双向量表。list不是连续的内存空间，但是提供了iterator，环状的list在查找的等相当方便。。环状的list只需要一个标记，就可以完全的表示整个的list刻意的在环状的list尾端加一个空白节点，表示stl的前毕后开的区间。

slist也不是连续的内存空间。slist比list好用的空间更少。因为是单向的，因此有一些操作操作的速度更加快速。他无法提供向回的查找。因此slist使用insert和earse是相当不明智，因为他要重头查找。浪费时间了。

set set提供的是有排序的集合。自动排序。它属于红黑树的数据结构。

map，map在我们的程序是经常使用的，它提供了排序的功能和键值对的操作，通过key和value来查找。提供iterator.  推荐大家使用map

今天总结这些 更多文章，欢迎访问：http://blog.csdn.net/wallwind


作者：wallwind 发表于2012-3-23 2:26:24 原文链接