STL容器分析.doc

STL容器分析
vector：
实现：vector采用一段连续的内存来存储其元素。容量不足时将自动重新分配内存，并将原数据拷入，再释放原内存。
优点：适用于随机访问和尾部插入，删除。可采用reserve()来预先分配内存，减少内存STL容器分析
vector：
实现：vector采用一段连续的内存来存储其元素。容量不足时将自动重新分配内存，并将原数据拷入，再释放原内存。
优点：适用于随机访问和尾部插入，删除。可采用reserve()来预先分配内存，减少内存分配时间消耗，以提高性能。
查找：对于查找，可排序后利用算法库的getlowerbound()进行有序插入，利用binary_search()对元素进行二分查找。可提高效率。
缺点：对于随机插入，删除，查找不适用。
常用函数：size,push_back,pop_back,swap,
at(等同下标访问)，clear,back,begin,end,
reserve,empty。头文件#include<vector>
deque：(queue类似)
实现：deque采用多块内存串连起来的方式来存储元素。
优点：内存分配操作开销较小。对首部和尾部操作时开销很低。
缺点：无法操作中间数据，查找开销很大，无法下标访问。
常用函数： size,push,pop,swap,back,front ,
empty。头文件#include<queue>
list:
实现：双向链表，每个元素独立存储。
优点：理论上，任意位置插入、删除非常快。但大量内存操作，实际性能有所降低。
缺点：不适用于查找。
常用函数： size,push_back,pop_back,swap,
back ,insert,clear,sor。头文件#include<list>.
map、set：
实现：都采用平衡树（红黑树）实现其元素在内存中的存储。平衡二叉检索树使用中序遍历算法，检索效率高于vector、deque和list等容器。检索结果升序排列。
优点：元素值不重复，内部数据有序。理论上，较高效率实现插入、删除与查找。实际有内存操作影响，有所降低。
缺点:随机访问不便。
其他：构造主要为了方便快速检索。map以键值对（key-value）形式存储。元素或value均不重复。
常用函数：insert,erase,iterator,clear,find,size.
头文件#include<set>,#include<map>
multimap、multiset：
与map、set类似，唯一区别是插入数据可重复。头文件#include<set>,#include<map>.s
unordered_map、unordered_multimap:
实现：c++11引入的散列容器。散列容器具有不稳定性：他依赖于实际所使用的散列算法。而针对不同的元素数量，不同的散列算法具有相当大的性能差异。内部数据无序。