最近发现虽然一直在使用STL，但从来没有好好的去了解对比过，所以决定系统的学习与归纳下STL相关知识。

关键字： vector,list,map,set,unordered_map,unordered_set

Vector

Vector在内存上的分布是采用一段连续内存来存储，进行插入操作时如果内存不足则会malloc申请一块新的内存并将当前数据memcpy复制到新内存中并free释放原内存。但是在有些实现中通过一些算法来分析申请新内存并舍弃旧内存的效率，当效率底下时会通过使用链表连接两块内存来存储数据，当然这部分对外是不透明的，外部使用时只会看到Vector是一整块内存空间。
对Vector进行插入删除操作时尾部操作效率最高，头部操作效率最低，效率取决于要挪动的元素数量。
由于Vector使用数组方式存储数据，所以其下标方式查找效率为O(1)，未排序搜索时间复杂度为O(n)，排序后可以利用各种查找算法进行查找，效率可与set/map相比。

List

List是一个双向链表，节点之间互相独立，所以在插入上效率较高，任何位置插入都极快，但是因此在插入删除时会频繁申请和释放内存，产生内存碎片。
由于List是一个链表，所以其查找方式只能从头结点开始遍历，时间复杂度为O(n)。

Map、Set

这两个在内存中都是通过平衡树（红黑树）做的数据存储，所以实际上查找时间复杂度为O(nlogn)，插入删除效率也较高。

Unordered Map、Unordered Set

这两个是C++11中引入的散列容器，所以其在内存中的数据分布取决于散列算法，不同散列算法的效率和散列冲突也决定容器的效率。散列的理论查找时间复杂度为O(1)，实际查找速度取决于散列算法的复杂程度和冲突情况，同样，插入和删除的理论时间复杂度也为O(1)。

版权属于：一名宅。

本文链接：https://zhaiyiming.com/archives/stl-type-diff-overview.html

转载时须注明出处及本声明