STL学习笔记(3)- STL容器和使用场景

STL的容器主要分为两类,一类是序列式容器,包括vectordequelist等;一类是关联式容器,包括setmultisetmapmultimap。下面主要对容器进行一下说明

容器 vector deque list set multiset map multimap
经典内部结构 内存连续的空间 多个内存连续的空间 双向链表 二叉树 二叉树 二叉树 二叉树
元素 Value Value Value Value Value Key-Value Key-Value
元素可重复 Key不能重复
元素的搜寻速度 非常慢 对Key快 对Key快
元素插入 尾插 头部和尾部 任何位置插入
  • vector 插入时从尾部插入,删除时不删除存储空间,如果插入元素时超过预留的空间大小会以2倍的方式扩容后进行数据拷贝并存储。数据读取速度较快,元素尾插速度较快,中间插入或者删除速度非常慢。使用场合,如软件的操作历史等。
  • deque 支持头部和尾部插入,尾部的插入/删除速度快,同vector一样,中间插入或者删除速度慢。使用场合,排队等场合。
  • vector和deque比较
    (1) vector.at()deque.at() 效率高。
    (2) 如果有大量释放操作 vector 的花费时间更少。
    (3) deque 支持头部的快速插入和移除
  • set 内部实现使用 红黑树,元素插入速度慢,查找速度非常快,因为采用红黑树的结构查找时对数据进行了减支,不允许数据重复。而当数据插入时,需要进行二叉树的平衡和排序的问题,因此插入比较慢。应用场合:对数据有排序的要求,比如游戏个人得分排行等。
  • map 实现同样采用红黑树,使用 Key-Value键值对的形式。适用场合:大数据量的时候,使用ID查找用户等。

You May Also Like

About the Author: admin

喜欢编程、爱游戏,更爱生活。

发表评论

电子邮件地址不会被公开。