Chinaunix首页 | 论坛 | 博客
  • 博客访问: 5567812
  • 博文数量: 1310
  • 博客积分: 12961
  • 博客等级: 上将
  • 技术积分: 15646
  • 用 户 组: 普通用户
  • 注册时间: 2009-01-09 11:25
个人简介

偷得浮生半桶水(半日闲), 好记性不如抄下来(烂笔头). 信息爆炸的时代, 学习是一项持续的工作.

文章分类

全部博文(1310)

文章存档

2020年(92)

2019年(193)

2018年(81)

2017年(80)

2016年(70)

2015年(52)

2014年(41)

2013年(51)

2012年(85)

2011年(45)

2010年(231)

2009年(287)

分类: Windows平台

2019-07-02 18:43:39

队列性容器 vector list deque

vector 线性顺序, 大小自动扩展. 创建vector后, 会自动在内存中分配一个连续的内存空间, 因此支持 [] 操作, 随机存取.   但是在增减时会造成内存拷贝, 效率较低, 所以vector仅设计成后端进行push/pop操作. vecotor一般在创建时就指定其空间大小.

list为双向链表, 内存空间可以不连续, 通过指针进行数据访问, 所以他的随机访问没有效率, 没有[]操作. 但是他支持任意位置上的增删.

deque是优化的对序列两端元素进行push/pop操作的容器,  支持比较快速的[]随机访问 (采用的是多个连续的存储块). 效率介于 list / vector 之间. 


关联容器 set/multiset   map/multimap. 默认升序排序
    都是非线性的数结构(平衡检索二叉树--红黑树)
    set元素是唯一的, 按照顺序培训的.   multiset 不要求唯一.
    map元素为kv键值对关系, 键不可重复且排序. multimap的键在容器中可以不唯一.

map/set 插入删除比vector快(因为vector是顺序存储, map/set是链式存储),  比list慢(因为list为线性的, map/set为二叉树). 而且map/set是排序的,插/删操作需要重新排序动作.

map/set的检索(检索复杂度Log(N))比vector慢, 比list((检索复杂度为容量大小)快(因为list需要逐个顺序检索).





阅读(99) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~