忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 2127 | 回复: 11

[C] 用C实现一个变长数组需要记录几个数据 [复制链接]

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-04 14:25 |显示全部楼层
用C实现一个变长数组需要记录几个数据

一般的变长数组( vector )的实现,需要记录三个数据:
  • 数据空间的地址,
  • 空间大小,
  • 数组里已存在的元素个数。

最近看云风的BLOG
云风同学说
其实并不需要三个变量来维持 vector 结构,两个就够了。那个表识容量大小的变量是多余的
struct vector { int *data; int size; };

用C实现一个变长数组需要记录几个数据??




论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2017-12-04 19:38 |显示全部楼层
本帖最后由 yulihua49 于 2017-12-04 19:39 编辑
dorodaloo 发表于 2017-12-04 14:25
用C实现一个变长数组需要记录几个数据

一般的变长数组( vector )的实现,需要记录三个数据:

一般情况云风同学是对的。
特殊的,例如string,可以增加一个有效数据长度,因为他是从头连续运用的。

论坛徽章:
14
巨蟹座
日期:2013-11-19 14:09:4615-16赛季CBA联赛之青岛
日期:2016-07-05 12:36:0515-16赛季CBA联赛之广东
日期:2016-06-29 11:45:542015亚冠之全北现代
日期:2015-07-22 08:09:472015年辞旧岁徽章
日期:2015-03-03 16:54:15巨蟹座
日期:2014-12-29 08:22:29射手座
日期:2014-12-05 08:20:39狮子座
日期:2014-11-05 12:33:52寅虎
日期:2014-08-13 09:01:31巳蛇
日期:2014-06-16 16:29:52技术图书徽章
日期:2014-04-15 08:44:01天蝎座
日期:2014-03-11 13:06:45
发表于 2017-12-05 08:24 |显示全部楼层
那假如我删掉一个元素时,他是将 size 减一,还是重新分配一个 size-1 的内存然后将数据拷贝进去?
如果是后者,那效率太低了;如果是前者,我再增加一个元素时,他怎么知道不需要重新分配内存?

通过非标函数 _msize/malloc_usable_size 可以取得实际内存大小,但用户的内存可未必是依标准方式来的,有可能使用了内存池。

论坛徽章:
13
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15摩羯座
日期:2014-07-21 10:11:28
发表于 2017-12-05 09:36 |显示全部楼层
没有capacity,怎么知道int *data的界限在哪里?

论坛徽章:
0
发表于 2017-12-05 10:24 |显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽

论坛徽章:
35
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-12-05 18:58 |显示全部楼层
原帖在这里 https://blog.codingnow.com/2008/06/variable_length_array.html
说的是2倍的分配策略,这种策略下,新的size大于老的size才去触发,而且由于每次都是2倍的策略,
所以每次都会去判断空间够不够用,不需要直接与容量比较,所以就不需要容量这个参数了,所以这种
位操作是可以的。
但是实际场景是,容量到达一定大小后就不会去2倍了,比如内存到达一半,所以这个技巧就没用了

论坛徽章:
40
巨蟹座
日期:2013-10-25 10:53:0215-16赛季CBA联赛之山东
日期:2016-04-17 12:00:2815-16赛季CBA联赛之福建
日期:2016-04-12 15:21:2915-16赛季CBA联赛之辽宁
日期:2016-03-24 21:38:2715-16赛季CBA联赛之福建
日期:2016-03-18 12:13:4015-16赛季CBA联赛之佛山
日期:2016-02-05 00:55:2015-16赛季CBA联赛之佛山
日期:2016-02-04 21:11:36每日论坛发贴之星
日期:2016-01-27 06:20:00程序设计版块每日发帖之星
日期:2016-01-27 06:20:002016科比退役纪念章
日期:2016-04-23 00:51:2315-16赛季CBA联赛之新疆
日期:2016-04-25 10:55:4515-16赛季CBA联赛之天津
日期:2017-06-26 15:49:56
发表于 2017-12-06 03:27 |显示全部楼层
如果你的增长策略是固定的话,比如起始16个然后每次乘2,那么从当前元素个数就可以算出数组容量了,此时那个表示数组容量的变量是多余的,比如数组中有17个元素,那么当前容量显然是32。
不过这么做有个地方有问题,如果你的数组可以删元素的话就要多做一些事,比如当前17个,删除掉一个,你就必须把多余的空间还回去,要不然就错了。
但如果你能保证数组使用连续的内存空间的话其实也不用麻烦,因为free一段内存并不需要知道这段内存有多大,无非就是你会做一些无用的realloc,比如从17减到16再增长到17,如果你知道数组实际容量的话是不需要重新分配内存的,但如果你不知道的话就需要做一次realloc减半,再做一次realloc加倍。

目前std::vector的实现是记录了数组容量的,因为vector里可以删元素。

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-06 14:25 |显示全部楼层
回复 2# yulihua49
例如string,可以增加一个有效数据长度,因为他是从头连续运用的。

push_back函数代码
push_back 在实际编程中是非常重要的

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-12-28 13:27 |显示全部楼层
本帖最后由 dorodaloo 于 2017-12-28 13:28 编辑

回复 6# cokeboL

cokeboL老师



值得学习和能够给大家带来一定正确知识的有能力人

论坛徽章:
35
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-12-28 17:44 |显示全部楼层
猫哥这种才配称为偶像级别的存在,我的偶像是猫哥
您需要登录后才可以回帖 登录 | 注册

本版积分规则

DTCC2018购票6.8折优惠进行时

中国数据库技术大会是国内数据库及大数据领域规模最大、最受欢迎的技术交流盛会。 2018年5月10-12日,第九届中国数据库技术大会将如约而至。本届大会以“数领先机•智赢未来”为主题,设定2大主会场及20个技术专场,邀请来自国内外互联网、金融、教育等行业百余位技术专家,共同探讨Oracle、MySQL、NoSQL、大数据等领域的前瞻性热点话题与技术。
----------------------------------------
优惠时间:2018年2月13日前

报名链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP