C++STL堆栈与FORWARD_LIST
问题说明
我有一个用例,其中我需要以不特定的顺序存储一定数量的uint16_t变量(尽管变量的实际类型并不相关)。我已决定求助于STL来寻找最符合我需要的容器。
容器中的对象可以从容器中取出以供使用,然后放回容器中。在某种程度上,机械师可能只有一盒螺丝刀,而不是把螺丝刀放在口袋里。容器不需要对存储的对象执行任何分类,取出什么并不重要-唯一的要求是知道容器中是否还有任何东西。
我的眼睛转向std::stack
和std::forward_list
。它们都提供O(1)插入(只需更改前端元素)和O(1)弹出操作(同样,仅更改前端元素并返回前一个前端)。问题是--我不知道它们在概念上有什么不同。
我知道std::stack
是一个仅包装实际STL容器(默认情况下为std::deque
)的适配器,因此它可能会有一些意外的开销,具体取决于包装的容器。
我倾向于使用std::forward_list
,但我正在寻求同事的意见。如果你对这件事有什么想法,请与我们分享。
正确答案
TLDR: 如果只需要添加/删除最后一个元素,请使用向量或堆栈。这是最快的选项,并且开销最低。
长版本:查找链表和动态数组的比较,例如:vector vs. list in STL
大部分讨论都是关于std::List,但Forward_List也适用同样的原则
关于管理费用和运营的简短说明
矢量数据结构:
- 1个动态分配的数组
- 1个整数,表示使用的元素数
- 1个整数,表示可用元素的数量(预分配的大小)
(脚注:实际上不是计数器,而是指针。让我们不用担心那个)。
将元素追加到向量的末尾:
- 检查是否有可用的空间。如果不是,则重新分配当前大小两倍的数组。由于向量增长到其大小的两倍(指数增长),因此这种情况非常罕见,并且不会对性能产生太大影响。
- 将元素复制到数组中的索引
- 递增计数器
从向量的末尾删除元素:
- 减少计数器。就是这样(除非你有析构函数)
内存开销: 指针和计数器为24字节。8字节,用于数组的动态分配。最差情况为50%未使用的元素。
转发列表数据结构:
- 1指向第一个元素的指针
- 1指向最后一个元素的指针
- 在每个元素中,有一个指向下一个元素的指针
正向列表插入:
- 动态分配新元素(昂贵)
- 设置指针(廉价)
删除第一个元素:
- 将指针从第一个元素更改为第二个元素
- 释放元素(开销)
动态分配的计算开销比向量使用的任何计算开销都高得多。
内存开销:
- 基本结构中两个指针的16个字节
- 每个元素8字节用于动态分配,8字节用于指向下一个元素的指针,6字节填充,因为分配器只能处理8字节的倍数
每使用2个字节的有效负载,与向量中2取2的最坏情况相比,有22个字节的开销!
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /reply/detail/tancck
-
YouTube API 不能在 iOS (iPhone/iPad) 工作,但在桌面浏览器工作正常?
it1352 07-30 -
iPhone,一张图像叠加到另一张图像上以创建要保存的新图像?(水印)
it1352 07-17 -
保持在后台运行的 iPhone 应用程序完全可操作
it1352 07-25 -
在android同时打开手电筒和前置摄像头
it1352 09-28 -
使用 iPhone 进行移动设备管理
it1352 07-23 -
扫描 NFC 标签时是否可以启动应用程序?
it1352 08-02 -
使用c++17更新时出现G++编译器警告
it1352 06-18 -
Android微调工具-删除当前选择
it1352 06-20 -
Reaction本机IOS Safari没办法打开页面,因为该地址在有效登录后无效
it1352 06-07 -
复制文件夹/文件而不修改属性?
it1352 07-15