顺序容器初探(上)

一个容器就是一些特定类型对象的集合

顺序容器的数据结构

array:

如下图所示 数组是一个大小固定的数据结构,支持高效的随机访问,时间复杂度为O(1),但是插入与删除等操作比较低效,时间复杂度为O(n),需要做大量的数据搬移工作。因此该容器支持快速随机访问,不支持添加或删除元素。

forward_list:

下图为一个单链表,与数组相反,它并不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用,链表的特点为随机访问复杂度高,时间复杂度为O(n),但是插入与删除操作比较高效,时间复杂度为O(1)。

因此只支持单向顺序访问,在链表任何位置进行插入删除操作都很快。

 

 

 

 

list:

下图为一个双向链表,与单向链表类似,只是在每个节点多了一个前驱指针,所以该链表支持双向遍历。

因此该容器支持双向顺序访问,在链表任何位置进行插入删除操作都很快。

 

deque:

下图为单向队列的数据结构,队列跟栈一样,也是一种抽象的数据结构。它具有先进先出的特性,支持在队尾插入元素,在队头删除元素。deque为双向队列的顺序容器,顾名思义,双向队列的不同之处在于队头也是队尾,队尾也是队头。

因此deque这种容器支持快速随机访问,在头尾位置插入/删除速度很快。

 

vector:

vector其实也是一个数组结构,只不过经过对数组内存空间的管理,使得vector成为了一个动态的数组结构。

因此vector为可变大小数组,支持快速随机访问,在尾部之外的位置插入或删除元素可能很慢。

string:

与vector类似的容器,但专门用来保存字符。随机访问快。在尾部插入删除速度快。

容器选择原则

  1. 除非有很好的理由使用其他容器,否则应使用vector。

  2. 如果程序有很多小元素,且空间额外开销很重要,则不要使用链表。因为链表每个节点都会至少有一个后继指针,因此会占用很多额外空间。

  3. 如果程序要求随机访问元素,则使用数组(vector)或队列(deque)。string也支持随机访问,但是该容器专门用于保存字符,array则是因为该数组为固定大小数组。

  4. 如果程序要求在容器的中间插入或删除元素,应使用链表。

  5. 如果程序要求在容器的头尾插入或删除元素,但不在中间插入,则使用队列。

  6. 如果程序要求只有在读取输入时需要在容器中插入元素,随后需要随机访问元素,则

    • 首先确定真的需要中间插入元素,当处理输入数据时,通常可以很容易的在vector容器末追加数据,再调用标准库中的sort函数来对容器中的元素进行重排,以避免中间插入操作

    • 如果必须在中间位置插入元素,则在输入阶段考虑list,一旦输入完成,将list中的数据拷贝到另一个vector中。

容器操作

构造函数  
C c; 默认构造函数,构造空容器(array)
C c1(c2); 构造 c2 的拷贝 c1
C c(b,e); 构造 c ,将迭代器 b 和 e指定的范围内的元素拷贝到c
C c{a,b,c,…} 列表初始化c

 

赋值与swap  
c1=c2; 将 c1 中的元素替换为 c2 中的元素
c1=(a,b,c…); 将 c1 中的元素替换为列表中元素(除array)
a.swap(b); 交换 a 和 b 的元素,swap通常比c2从c1拷贝元素快得多
swap(a,b); 与 a.swap 等价
assign操作 不适用于关联容器和array
seq.assign(b,e); 将 seq 中的元素替换为迭代器 b 和 e 所表示的范围中的元素。迭代器 b 和 e 不能指向seq中的元素
seq.assign(i1); 将seq中的元素替换为初始化列表 i1 中的元素
seq.assign(n,t); 将 seq 中的元素替换为 n 个值为 t 的元素
大小  
c.size(); c中元素的数目(不支持forward_list)
c.max_size(); c可保存的最大元素数目
c.empty(); 若c中存储了元素,返回 false,否则返回 true

 

 

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

【博弈论】组合游戏及SG函数浅析

2021-3-17 20:21:00

经验教程

Elasticsearch 聚合

2021-3-17 20:45:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索