c++11标准模板库(STL) - 容器

2018-07-09 17:10:44

下面只是对 STL 的容器做个汇总和简单对比介绍,在实际项目中可以很清晰的知道该选择哪个容器。详细用法请参考 Containers - C++ Reference

array 是大小固定的容器,不能放大和收缩,效率接近于常规数组,0长度的 array 是合法的,只是不能解引用(front,back,data),array 在内存里是连续存储的,所以可以通过指针偏移来访问。


vector 是大小可变的容器,读取效率接近于常规数组,在内存里也是连续存储的,所以可以通过指针偏移来访问。vector 从末尾插入移除数据效率很高,但是从中间插入或者移除数据将非常缓慢。


list 是双向链表,每个元素都会有两个指针,一个指向前面元素,一个指向后面元素。

forward_list 是单向链表,每个元素都包含一个指针指向下一个元素。相较于 list 它的优点是些许的节约资源。缺点是只能往前迭代,不能往后。  

相较于其他,优点是可以在任意处高效率地插入或移除,list 也可以对内部数据进行排序。缺点是不能直接访问元素,只能通过迭代器遍历访问,所以元素个数不允许太多。


queue 是容器适配器,也就是一个类内部封装了另一个容器,实现了 FIFO 先进先出。

stack 是容器适配器,也就是一个类内部封装了另一个容器,实现了 LIFO 后进先出。  

deque 双端queue,功能类似 vector,但是在中间插入删除非常高效,也可以通过 [] 直接访问,但是内部实现比 vector 复杂的多,也不一定是连续存储元素。当元素很多时,在中间插入元素或删除元素,vector内存要重新分配,而deque不需要,效率非常高。


set 集合不允许出现重复值,不可以修改,可以通过值快速的查找,内部通过二叉树查找,有序,遍历速度快。

multiset 集合允许出现重复值,不可以修改,可以通过值快速的查找,内部通过二叉树查找,有序,遍历速度快。

unordered_set 内部通过 hash bucket 实现,单个访问速度快,遍历速度慢且无序,不允许出现重复值。

unordered_multiset 内部通过 hash bucket 实现,单个访问速度快,遍历速度慢且无序,允许出现重复值。


map 一个 key 对应一个值,有序,内部通过二叉树实现。

multimap  一个 key 对应多个值,有序,内部通过二叉树实现。

unordered_map  一个 key 对应一个值,无序,内部通过 hash bucket 实现,单个访问速度更快,遍历慢。

unordered_multimap  一个 key 对应多个值,无序,内部通过 hash bucket 实现,单个访问速度更快,遍历慢。




©著作权归作者所有
收藏
推荐阅读
简介
天降大任于斯人也,必先苦其心志。